Programmation Fonctionnelle, TD1

Figure
Version & licenses
Creative Commons License

Programmation Fonctionnelle, TD1 : Variables et fonctions.

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

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

Est-ce correct ? Réécrivez 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.

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

  3. let rec gcd a b =
  4. if a mod b = 0 then b
  5. else gcd b (a mod b)

  6. 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 'any -> 'any -> 'any.

Couples et $k$-uplets

Définissez les fonctions suivantes en Ocaml. Précisez 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 'left * 'right -> 'left et 'left * 'right -> 'right.

Un programme.

On considère le programme suivant :

  1. module Box =
  2. struct

  3. module Vector = struct
  4. type t = (float * float)

  5. let add (x1,y1) (x2,y2) = (x1 +. x2, y1 +. y2)

  6. let sub (x1,y1) (x2,y2) = (x1 -. x2, y1 -. y2)

  7. end

  8. type t = (Vector.t * Vector.t)

  9. let create ~x_min ~y_min ~diagonal =
  10. ((x_min, y_min), diagonal)

  11. let mem point (corner,diagonal) =
  12. let (x,y) = Vector.sub point corner in
  13. x >= 0. && y >= 0. && x <= fst diagonal && y <= snd diagonal

  14. end
  1. Listez les types, les valeurs et les modules définis par ce programme.
  2. Listez les types, les valeurs et les modules utilisés mais pas définis par ce programme.
  3. Pour chaque variable du programme, donnez son type.
  4. Proposez d'autres écritures pour la fonction mem. Laquelle vous semble être la meilleure ?
  5. Ajoutez une fonction qui étant donné une boîte $r$ et un point $v$définie la plus petite boîte contenant $r$ et $v$.