Programmation Fonctionnelle, TD3

Version & licenses
Creative Commons License

Programmation Fonctionnelle, TD3 : Manipulations de listes.

Guyslain Naves

Exercice 1 : Récursion

Implémenter les fonctions suivantes, sans utiliser les fonctions map, filter, flatten, for_all et fold_left, mais List.rev est autorisé:

  1. (* last renvoie le dernier élément de la liste *)
  2. val last : 'elt list -> 'elt

  3. (* cut i list : coupe la liste en deux, un préfixe de longueur i,
  4. et le suffixe des éléments restants.
  5. *)
  6. val cut : int -> 'elt list -> 'elt list * 'elt list

  7. (* maximum retourne l'élément maximum d'une liste *)
  8. val maximum : int list -> int

  9. (* even_only renvoie les éléments en position paire dans la liste,
  10. even_only [e0;e1;e2;...;en] = [e0;e2;e4;...]
  11. *)
  12. val even_only : 'elt list -> 'elt list

  13. (* indice ajoute un indice à chaque élément de la liste
  14. indice [5;3;6;2] = [(0,5); (1,3); (2,6); (3,2)]
  15. *)
  16. val indice : 'elt list -> (int * 'elt) list

  17. (* intersperse ajoute un élément entre toute paire d'éléments consécutifs d'une liste
  18. intersperse 1 [2;3;4;1;5] = [2;1;3;1;4;1;1;1;5]
  19. *)
  20. val intersperse : 'elt -> 'elt list -> 'elt list

  21. (* split renvoie deux listes, celles des éléments en position paire,
  22. et celle des éléments en position impaire.
  23. split [e0;e1;e2;...;en] = ([e0;e2;e4;...],[e1;e3;e5;...])
  24. *)
  25. val split : 'elt list -> 'elt list * 'elt list

  26. (* triangle calcule toutes les listes suffixes d'une liste :
  27. triangle [e0;e1;e2;e3;...] = [[e0;e1;e2;...];[e1;e2;e3;...];[e2;e3;e4;...];...]
  28. *)
  29. val triangle : 'elt list -> 'elt list list

Exercice 2 : Utilisation des fonctionnelles

Rependre l'exercice 1, mais cette fois, il est interdit d'écrire une fonction récursive. En échange, vous pouvez utiliser les fonctionnelles de liste que vous connaissez :

  1. val map : ('elt -> 'image) -> 'elt list -> 'image list
  2. val filter : ('elt -> bool) -> 'elt list -> 'elt list
  3. val flatten : 'elt list list -> 'elt list
  4. val fold_left : ('accu -> 'elt -> 'accu) -> 'accu -> 'elt list -> 'accu
  5. val for_all : ('elt -> bool) -> 'elt list -> bool
  6. val exists : ('elt -> bool) -> 'elt list -> bool

Quel vous semble être le style le plus approprié pour chacune de ces fonctions ?

Exercice 3 : Triplets Pythagoriciens

Comment calculer la liste de tous les triplets pythagoriciens $(a,b,c)$ avec $a^2 + b^2 = c^2$ d'entiers inférieurs à 100, en utilisant map, filter et flatten ? Il faudra aussi utiliser la fonction range déjà vue plusieurs fois.

Exercice 4 : Palindrome

Écrire une fonction vérifiant si une liste est un palindrome. La liste $[e_0;e_1;\ldots;e_n]$ est un palindrome si $e_i = e_{n-i}$ pour tout $i \in [0,n]$.

Exercice 5 : Tri rapide

  1. Écrire une fonction smaller qui prend un entier $a$ et une liste d'entier $l$, et calcule la sous-liste des entiers de $l$ plus petits que ou égaux à $a$.
  2. Écrire une fonction bigger, qui renvoie cette fois la liste des éléments strictement plus grand que $a$.
  3. En déduire l'algorithme de tri rapide.
  4. bigger et smaller nous obligent à faire deux parcours de la liste à chaque appel récursif. Utiliser fold_left pour calculer en même temps les deux listes : celle des éléments plus petits et celle des éléments plus grand.