Premiers pas en Caml

Exercice 1

  Écrire la fonction factorielle.

Solution 1

Voici une première solution:

let rec factorielle n =
  if n = 0 then 1 else  n * factorielle(n-1);;
factorielle : int -> int = <fun>
factorielle 4;;
- : int = 24

En voici une seconde qui use de filtrage:

let rec factorielle = function
  0 -> 1
| n -> n * factorielle(n-1);;
factorielle : int -> int = <fun>
factorielle 4;;
- : int = 24

Exercice 2

Définir une fonction calculant le produit de deux nombres suivant la méthode de la multiplication dite égyptienne.

Solution 2

let rec multiplication_egyptienne p q =
  if p = 0 then 0
  else if (p mod 2) = 0 then multiplication_egyptienne (p/2) (2*q)
       else q + multiplication_egyptienne (p-1) q;;
multiplication_egyptienne : int -> int -> int = <fun>
multiplication_egyptienne 3 4;;
- : int = 12
multiplication_egyptienne 4 3;;
- : int = 12

Remarquez que p-1 étant pair on peut déplier l'appel récursif et directement écrire:

let rec multiplication_egyptienne p q =
  if p = 0 then 0
  else if (p mod 2) = 0 then multiplication_egyptienne (p/2) (2*q)
       else q + multiplication_egyptienne ((p-1)/2) (2*q);;
multiplication_egyptienne : int -> int -> int = <fun>
multiplication_egyptienne 3 4;;
- : int = 12
multiplication_egyptienne 4 3;;
- : int = 12

Pour vous aider à mettre au point, vous pouvez tracer les appels à une fonction grâce à trace. Par exemple:

trace "multiplication_egyptienne";;
The function multiplication_egyptienne is now traced.
- : unit = ()
multiplication_egyptienne 3 4;;
multiplication_egyptienne <-- 3
multiplication_egyptienne --> <fun>
multiplication_egyptienne* <-- 4
multiplication_egyptienne <-- 1
multiplication_egyptienne --> <fun>
multiplication_egyptienne* <-- 8
multiplication_egyptienne <-- 0
multiplication_egyptienne --> <fun>
multiplication_egyptienne* <-- 16
multiplication_egyptienne* --> 0
multiplication_egyptienne* --> 8
multiplication_egyptienne* --> 12
- : int = 12

Exercice 3

Définir une fonction calculant la puissance entière d'un entier selon le même principe que la multiplication égyptienne.

Solution 3

let rec puissance_egyptienne p q =
  if q = 0 then 1
  else if q mod 2 = 0
       then let r = puissance_egyptienne p (q/2) in r * r
       else p * puissance_egyptienne p (q-1);;
puissance_egyptienne : int -> int -> int = <fun>
puissance_egyptienne 4 5;;
- : int = 1024
puissance_egyptienne 5 4;;
- : int = 625

Observez le let local introduisant la variable r calculée une fois, utilisée deux fois.

Caml procure une syntaxe proche des expressions mathématiques où, comme en mathématiques, l'emploi de parenthèses est quelquefois nécessaire. Voici quelques règles, dues à Pierre Weis, concernant leur emploi.

• Les parenthèses autour des tests sont inutiles: if (x = 1) then ... est équivalent à if x = 1 then ...
• Les parenthèses autour des arguments de fonctions sont optionnelles: f x est compris comme f (x)
• Les opérateurs arithmétiques ont les mêmes règles de précédence qu'en maths: par exemple 1 + 2 * 3 signifie 1 + (2 * 3)
• les opérateurs se comportent ``bien'' avec les appels de fonctions: f x + g y signifie (f x) + (g y) (et bien sûr aussi (f (x)) + (g (y))). Mais attention aux arguments de fonctions qui sont des opérations: comme en mathématiques, il ne faut pas oublier les parenthèses: il faut écrire f (x - 1) pour appliquer f à x - 1. Si l'on écrit f x - 1 sans parenthèses, c'est compris par Caml comme (f x) - 1. De la même façon, si l'argument est un appel de fonction, il faut impérativement les parenthèses: fact (fact 3) signifie fact 6, mais fact fact 3 est mal typé (il signifie fact appliqué à fact et à 3).
• dans le doute on peut toujours ajouter des parenthèses comme en maths.

Voici la version très parenthésée de puissance_egyptienne, équivalente en fonctionnalité mais d'allure différente. Le style c'est l'Homme, dit-on, il ne vous reste plus qu'à raffiner le vôtre!

let rec puissance_egyptienne p q =
  if (q = 0) then 1
  else if (q mod 2) = 0
       then let r = (puissance_egyptienne p (q/2)) in (r * r)
       else p * (puissance_egyptienne p (q-1));;
puissance_egyptienne : int -> int -> int = <fun>
puissance_egyptienne 4 5;;
- : int = 1024
puissance_egyptienne 5 4;;
- : int = 625

Exercice 4

Définissez une fonction calculant le pgcd de deux nombres entiers.

Solution 4

let rec pgcd n m =
  if n > m then pgcd m n
  else if n = 0 then m
       else let p = m / n
            and r = m mod n in
            pgcd r n;;
pgcd : int -> int -> int = <fun>
pgcd 3 12;;
- : int = 3

Observez le let local introduisant cette fois-ci deux variables locales p et r liées par le mot clef and (même si p n'est pas ici utilisée).

Exercice 5

Définir une fonction calculant le ppcm. On pourra s'aider du pgcd.

Solution 5

let ppcm n m =
  (n*m)/(pgcd n m);;
ppcm : int -> int -> int = <fun>
ppcm 4 10;;
- : int = 20

Notez qu'il n'est nul besoin de rec dans cette définition non récursive.

Exercice 6

Calculez les nombres de Catalan. On rappelle que:

Catalan(0) = 1, Catalan(1) = 1, Catalan(n) = somme de Catalan(p)*Catalan(q) pour tout p+q = n-1. Voici les premiers nombres de Catalan: 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796.

Solution 6

Voici la solution de Michel Mauny qui définit tout d'abord une fonction générale de sommation prenant une fonction et un entier (traité par filtrage).

let rec somme f = function
  0 -> f(0)
| n -> f(n) + somme f (n-1);;
somme : (int -> int) -> int -> int = <fun>
let rec catalan = function
  0 -> 1
| 1 -> 1
| n -> let f p = catalan p * catalan (n-1-p) in
       somme f (n-1);;
catalan : int -> int = <fun>

Notez la fonction f localement créée dans catalan et fournie à somme.

for i = 0 to 10 do
  print_int (catalan i);
  print_string ", "
done;;
1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, - : unit = ()

On imprime quelques nombre de Catalan au moyen d'une classique boucle for. L'indice i de la boucle a comme portée le corps de la boucle seule: il n'est pas disponible après.

Voici un autre type de solution en une seule fonction.

let rec nombre_de_catalan n =
  if n = 0 or n = 1 then 1
  else let rec enumere p q resultat =
          if p = n then resultat
          else enumere (p+1)
                       (q-1)
                       (resultat + (nombre_de_catalan p)*(nombre_de_catalan q))
          in enumere 0 (n-1) 0;;
nombre_de_catalan : int -> int = <fun>
for i = 0 to 10 do
  print_int (nombre_de_catalan i);
  print_string ", "
done;;
1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, - : unit = ()

Notez ici l'introduction d'une fonction locale récursive à trois arguments (on pourrait remplacer q par n-1-p). Observez le connecteur logique or.

Exercice 7

Calculez les coefficients du binôme par la méthode récursive simple: $C$_n^p = C_n-1^p + C_n-1^p-1.

Solution 7

let rec nombre_de_pascal n p =
  if p = 0 or p = n then 1
  else nombre_de_pascal (n-1) (p-1) + nombre_de_pascal (n-1) p;;
nombre_de_pascal : int -> int -> int = <fun>
for i = 0 to 10 do
  for j = 0 to i do
    print_int (nombre_de_pascal i j);
    print_string " "
  done;
  print_newline ()
done;;
1 
1 1 
1 2 1 
1 3 3 1 
1 4 6 4 1 
1 5 10 10 5 1 
1 6 15 20 15 6 1 
1 7 21 35 35 21 7 1 
1 8 28 56 70 56 28 8 1 
1 9 36 84 126 126 84 36 9 1 
1 10 45 120 210 252 210 120 45 10 1 
- : unit = ()

Notez l'emploi de print_newline pour passer à la ligne. Attention n'oubliez pas () après print_newline!

Exercice 8

Calculez le nombre de coefficients binômiaux impairs sur une ligne du triangle de Pascal.

Solution 8

Cette solution utilise une fonction locale énumérant les coefficients et maintenant dans un second argument (un tampon) le compte des coefficients impairs.

let rec nombre_de_coefficients_impairs n =
  let rec enumere p resultat =
    if p > n then resultat
    else let cnp = nombre_de_pascal n p in
         if (cnp mod 2) = 1 then enumere (p+1) (resultat+1)
         else enumere (p+1) resultat in
  enumere 0 0;;
nombre_de_coefficients_impairs : int -> int = <fun>
for i = 1 to 15 do
  print_int (nombre_de_coefficients_impairs i);
  print_string " "
done;;
2 2 4 2 4 4 8 2 4 4 8 4 8 8 16 - : unit = ()

Notez les trois let imbriqués.

Exercice 9

Traitons maintenant de grands entiers ou polynômes. Ils sont tous deux représentés par une liste de coefficients ordonnés par puissance croissante. Ainsi x^2 + 2x + 4 est-il décrit par la liste [4; 2; 1].

Définir l'addition de deux polynômes.

Solution 9

let rec additionner_polynomes p1 p2 =
  if p1 = [] then p2
  else if p2 = [] then p1
       else ((hd p1)+(hd p2))::(additionner_polynomes (tl p1) (tl p2));;
additionner_polynomes : int list -> int list -> int list = <fun>
additionner_polynomes [1] [2];;
- : int list = [3]
additionner_polynomes [-1] [1];;
- : int list = [0]
additionner_polynomes [1;2] [3];;
- : int list = [4; 2]
additionner_polynomes [3;2;1] [5;4;0;0;1];;
- : int list = [8; 6; 1; 0; 1]

Exercice 10

Définir une fonction convertissant un entier en un grand entier. On supposera que la base est décimale:

let base = 10;;
base : int = 10

Solution 10

let rec convertir_en_grand_entier entier =
    if entier = 0 then [0] else
    let quotient = entier / base
    and reste = entier mod base in
    reste :: convertir_en_grand_entier quotient;;
convertir_en_grand_entier : int -> int list = <fun>
convertir_en_grand_entier 345;;
- : int list = [5; 4; 3; 0]

La précédente fonction a le défaut d'introduire un zéro superflu en tête de la représentation. Voici une solution corrigeant ce défaut:

let rec convertir_en_grand_entier entier =
    let rec convertir entier =
        if entier = 0 then [] else
        let quotient = entier / base
        and reste = entier mod base in
        reste :: convertir quotient in
    if entier = 0 then [0] else convertir entier;;
convertir_en_grand_entier : int -> int list = <fun>
convertir_en_grand_entier 345;;
- : int list = [5; 4; 3]

Exercice 11

Définir une fonction convertissant un grand entier en un entier.

Solution 11

let rec convertir_en_entier = function
    [] -> 0
  | chiffre :: reste_nombre ->
     chiffre + base *  convertir_en_entier reste_nombre;;
convertir_en_entier : int list -> int = <fun>
convertir_en_entier (convertir_en_grand_entier 345);;
- : int = 345
convertir_en_entier (convertir_en_grand_entier 0);;
- : int = 0

Exercice 12

Définir une fonction imprimant un grand entier. Voici des exemples de grands entiers codés en base décimale:

let n1 = [1]
and n987654321 = convertir_en_grand_entier 987654321
and n345 = convertir_en_grand_entier 345;; 
n1 : int list = [1]
n987654321 : int list = [1; 2; 3; 4; 5; 6; 7; 8; 9]
n345 : int list = [5; 4; 3]

Solution 12

let rec imprimer_grand_entier = function
    [] -> ()
  | chiffre :: reste_entier ->
     imprimer_grand_entier reste_entier;
     print_int chiffre;;
imprimer_grand_entier : int list -> unit = <fun>
imprimer_grand_entier n987654321;;
987654321- : unit = ()

Notez ici la valeur () qui ne désigne rien de particulier sauf qu'il faut bien retourner une valeur quelconque: revenez donc sur le type de cette fonction!

Exercice 13

Définir une fonction d'addition de grands entiers. Attention à la retenue!

Solution 13

Voici une première version avec deux match explicites

let rec somme entier1 entier2 =
    begin match entier1 with
      [] -> entier2
    | chiffre1 :: reste_entier1 ->
       begin match entier2 with
         [] -> entier1
       | chiffre2 :: reste_entier2 ->
          let nouveau_chiffre = chiffre1 + chiffre2 in
          if nouveau_chiffre < base
          then nouveau_chiffre :: somme reste_entier1 reste_entier2
          else (nouveau_chiffre - base) ::
               somme reste_entier1 (somme reste_entier2 [1])
       end
    end;;
somme : int list -> int list -> int list = <fun>
imprimer_grand_entier (somme n987654321 n987654321);;
1975308642- : unit = ()

On peut mettre à profit la curryfication implicite de ML et supprimer les appels explicites à match et ainsi écrire:

let rec somme = function
    [] -> (function entier2 -> entier2)
  | chiffre1 :: reste_entier1 as entier1 ->
     (function
        [] -> entier1
      | chiffre2 :: reste_entier2 ->
         let nouveau_chiffre = chiffre1 + chiffre2 in
         if nouveau_chiffre < base
         then nouveau_chiffre :: somme reste_entier1 reste_entier2
         else (nouveau_chiffre - base) ::
              somme reste_entier1 (somme reste_entier2 [1]));;
somme : int list -> int list -> int list = <fun>
imprimer_grand_entier (somme n987654321 n987654321);;
1975308642- : unit = ()

Notez le as qui permet de reconnaître l'argument à la fois en tant que tel comme entier1 et, déstructuré, comme une liste chiffre1 :: reste_entier1.

Exercice 14

Calculez l'opposé d'un polynôme.

Solution 14

let rec polynome_oppose = function
   [] -> []
 | coefficient :: reste ->
    (- coefficient) :: (polynome_oppose reste);;
polynome_oppose : int list -> int list = <fun>

Exercice 15

Écrire les fonctions de multiplication de grands entiers.

Solution 15

Comme dans la multiplication à la main, on introduit d'abord la multiplication par un chiffre.

let rec produit_par_un_chiffre chiffre = function
    [] -> []
  | premier_chiffre :: reste_entier ->
     let petit_produit = chiffre * premier_chiffre in
     let quotient = petit_produit / base
     and reste = petit_produit mod base in
     let grand_produit = produit_par_un_chiffre chiffre reste_entier in
     if quotient = 0
     then reste :: grand_produit
     else reste :: somme [quotient] grand_produit;;
produit_par_un_chiffre : int -> int list -> int list = <fun>
let produit_par_base entier =
    0 :: entier;;
produit_par_base : int list -> int list = <fun>
let rec produit entier1 entier2 =
    begin match entier1 with
      [] -> [0]
    | chiffre :: reste_entier ->
       somme (produit_par_un_chiffre chiffre entier2)
             (produit_par_base (produit reste_entier entier2))
    end;;
produit : int list -> int list -> int list = <fun>
imprimer_grand_entier (produit n345 n345);;
119025- : unit = ()

Exercice 16

Calculer la factorielle de 100 avec des grands entiers.

Solution 16

Comme l'on n'a pas implanté la soustraction on ne peut pas utiliser la définition précédente, cf. exercice 1. Celle-ci n'utilise que des additions et mélange entiers et grands entiers.

let rec fact limit i n =
  if i>limit then n
  else fact limit (i+1) (produit n (convertir_en_grand_entier i))
in imprimer_grand_entier (fact 100 2 (convertir_en_grand_entier 1));;
933262154439441526816992388562667004907159682643816214685929638952175999932299156089414639
76156518286253697920827223758251185210916864000000000000000000000000- : unit = ()

Présentez bien vos programmes!