Programmation Fonctionnelle, TD1

Version & licenses
Creative Commons License

Programmation Fonctionnelle, TD1 : Découverte d'Ocaml.

Guyslain Naves

Découverte d'Ocaml

Syntaxe des fonctions

Un adepte de C/Java a défini ces fonctions en Ocaml :

  1. let has_sum_ten(a,b) : bool =
  2. a+b = 10

  4. let rec sum_interval(mini,maxi) : int =
  5. if mini > maxi then 0
  6. else mini + sum_interval(mini+1,maxi)

Est-ce correct ? Réécrire ces deux définitions dans un style plus idiomatique.

Quelques définitions

Pour chacune des variables définies ci-dessous, indiquez si c'est une fonction, et ce que vous pouvez dire de son type et de sa valeur.

  1. let average a b = (a +. b) /. 2.

  3. let ints = 1::2::3::4::[]

  5. let compose f g x = f (g x)

  7. let rec gcd a b =
  8. if a mod b = 0 then b
  9. else gcd b (a mod b)

  11. let sq = (fun x -> x ** 2.) 8.

Définition de fonctions

Définir les fonctions suivantes en Ocaml. Quel est le type de chacune ?

  1. La fonction identité, qui prenant un argument $x$, s'évalue en $x$.
  2. La fonction maximum de deux entiers, et la fonction minimum.
  3. La fonction factorielle : $n! = n \times (n-1)!$ pour $n > 0$, $0! = 1$.
  4. La fonction puissance entière : $a^b = a \times a^{b-1}$ si $b > 0$, $a^0 = 1$.
  5. La fonction de Fibonacci : $f_n = f_{n-1} + f_{n-2}$ si $n>1$, $f_1 = f_0 = 1$.

Bonus : faire des versions efficaces de la puissance et de Fibonacci.

À savoir : max et min sont déjà définies en Ocaml. Ce sont des fonctions polymorphes prenant deux arguments, leur type est 'a -> 'a -> 'a.

Couples et $k$-uplets

Définir les fonctions suivantes en Ocaml. Préciser leurs types.

  1. duplicate prend un entier $n$ et s'évalue (avec son argument) en le couple $(n,n)$.
  2. fst prend un couple $(x,y)$, et s'évalue en $x$.
  3. snd prend un couple $(x,y)$, et s'évalue en $y$.
  4. max_couple prend deux couples $(x_1,y_1)$ et $(x_2,y_2)$, et s'évalue en $(\max\{x1,x2\}, \max\{y1,y2\})$.
  5. swap prend un couple $(x,y)$, et s'évalue en le couple $(y,x)$.
  6. merge prend en argument deux couples $(a,b)$ et $(c,d)$, et s'évalue en le quadruplet $(a,b,c,d)$.

À savoir : fst et snd sont déjà définies en Ocaml, avec respectivement les types 'a * 'b -> 'a et 'a * 'b -> 'b.

Listes

Définir les fonctions suivantes en OCaml (indice : utiliser des fonctions récursives). Quels sont leur types ?

  1. enumerate prend un entier $n$ en argument, et s'évalue en la liste des $n$ premiers entiers en ordre décroissant.
  2. sum prend une liste d'entiers en argument, et s'évalue en la somme de ses éléments.
  3. print_int_list prend une liste d'entiers en argument, et affiche à l'exécution chaque élément de cette liste, un par ligne.
  4. last prend une liste d'entiers, et s'évalue en le dernier élément de la liste. Si la liste est vide, last s'évalue en $0$.
  5. pairs prend une liste d'entiers l$= [e_1;\ldots;e_k]$, et s'évalue en la liste de couples $[(e_1,e_2);(e_2,e_3);\ldots;(e_{k-1},e_k)]$. Si $k \leq 1$, pairs l s'évalue en [].
  6. rev prend une liste en argument, et s'évalue en la liste ayant les mêmes éléments, mais en sens inverse (indice : définir une fonction à deux arguments transvasant les éléments d'une liste dans une deuxième liste).

À savoir : rev est définie dans le module (une forme de librairie en Ocaml) List, vous pouvez l'utiliser en l'appelant List.rev.