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 fa.

En déduire la liste de tous les triplets pythagoriciens (a,b,c) avec a2+b2=c2 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 [e0;e1;;en] est un palindrome si ei=eni pour tout i[0,n].