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 du modules List, sauf List.rev :

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

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

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

  11. (* split renvoie deux listes, celles des éléments en position paire,
  12. et celle des éléments en position impaire.
  13. split [e0;e1;e2;...;en] = ([e0;e2;e4;...],[e1;e3;e5;...])
  14. *)
  15. val split : 'a list -> 'a list * 'a list

  16. (* invert_pairs échange la position de l'élément d'indice 2i avec l'élément d'indice 2i+1,
  17. invert_pairs [e0;e1;e2;e3;e4;...] = [e1;e0;e3;e2;e5;e4;...]
  18. Si la liste est impaire, le dernier élément n'est pas modifié.
  19. *)
  20. val invert_pairs : 'a list -> 'a list


  21. (* couple renvoie la liste des paires successives de la liste,
  22. couple [e0;e1;e2;...;en] = [(e0,e1);(e1,e2);...;(e{n-1},en)]
  23. *)
  24. val couple : 'a list -> 'a * 'a list

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

Exercice 2 : Utilisation des fonctionnelles

Rependre l'exercice 1, mais cette fois, il est interdit d'écrire une fonction récursive. En revanche, on autorise l'utilisation du module List.

Exercice 3 : Triplets Pythagoriciens

Implémenter la fonction de type suivant :

  1. val filter_find : 'a list -> ('a -> 'b list) -> 'b list

tel que filter_find l f est la liste des éléments $e$ pour lesquels il existe $a$ dans la liste $l$ telle que $e$ est un élément de $f\;a$.

En déduire la liste de tous les triplets pythagoriciens $(a,b,c)$ avec $a^2 + b^2 = c^2$ d'entiers inférieurs à 100. Il faudra utiliser la fonction interval vu en TP2.

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]$.