TD 2 : Types
Les entiers selon Peano
Définition
On définit le type entier tel qu'il est défini en mathématiques, à savoir à partir d'un élément formel Zero, et d'un «constructeur» que l'on notera Succ (comme successeur). En entier est donc soit Zero, soit l'étiquette Succ collée devant un entier déjà construit. La définition du type est la suivante:
type entier =   Zero 
              | Succ of entier;;
Essayez ensuite
let zero = Zero;;
let un = Succ zero;;
let deux = Succ un;;
let trois = Succ deux;;
Conversion
Créez les fonctions entier_of_int et int_of_entier. Essayez-les.
Opérations
Redécouvrons ce qu'est l'addition... Définissez la fonction plus, qui correspond au symbole +, mais avec cette fonction ce que l'on note usuellement a+b s'écrira plus a b... avec a et b qui sont des entiers.
Aide 1: La définition de Peano est a+0 = a et a+Succ(b) = Succ(a+b).
Aide 2: On vous écrit la structure de la fonction, car il faut faire intervenir du matching afin de traiter les differentes formes possibles de a et de b.
let rec plus = 
  function op1 -> 
  function op2 ->
    match (op1,op2) with
       (a,Zero) -> ...
     | ...      -> ... ;;
Essayez :
let a = entier_of_int 32;;
let b = entier_of_int 68;;
let c = plus a b;;
int_of_entier c;;
Faites à la main, sur une feuille, la ré-écriture de plus deux trois.
Faites de même la multiplication... Vérifiez expérimentalement que Succ Zero est bien l'élément neutre de la multiplcation, à gauche comme à droite.
Calcul formel sur les polynômes (si vous avez le temps)
Définition
On definit les types suivants pour représenter les polynômes.
type monome = Monome of float * int;;
type polynome =   Nul
                | Poly of monome * polynome;;
      
Est-ce que toutes les valeurs du type polynome correspondent à un polynôme, au sens mathématique du terme ?
Conversion
Rappel : "toto"^"titi" vaut "tototiti" en caml.
Definisser une fonction string_of_monome puis une fonction string_of_polynome. Vous éviterez autant que possible les 0*X^1 et autres lourdeurs.
Construction
En préambule, notez l'utilisation du mot when dans les filtres, illustrée par l'exemple suivant.
let signe_of_int =
  function 
      0          -> "nul"
    | a when a>0 -> "positif"
    | _          -> "negatif";;
signe_of_int   1 ;;
signe_of_int   0 ;;
signe_of_int (-1);;
      
Définissez une fonction poly qui ajoute un monôme à un polynome que l'on supposera canonique, et renvoie un polynôme canonique. Un polynôme canonique est tel que les degrés sont rangés du plus grand au plus petit, avec tous les monomes de degrés différents. Dans la suite, on utilisera cette fonction pour construire des polynômes, afin de n'avoir que des polynômes canoniques dans nos calculs.
Opérations
Définissez les fonctions polynome_plus, polynome_derive, et polynome_fois, en vous inspirant de la logique utilisée pour le type entier.