Programmation Fonctionnelle, TD3

Exercice 1 : Récursion

Implémenter les fonctions suivantes, sans utiliser les fonctions du modules List, sauf List.rev :

(* last renvoie le dernier élément de la liste *)
val last : 'a list -> 'a
(* cut i list : coupe la liste en deux, un prefixe de taille i,
et le suffixe des éléments restants.
*)
val cut : int -> 'a list -> 'a list * 'a list
(* even_only renvoie les éléments en position paire dans la liste,
even_only [e0;e1;e2;...;en] = [e0;e2;e4;...]
*)
val even_only : 'a list -> 'a list
(* split renvoie deux listes, celles des éléments en position paire,
et celle des éléments en position impaire.
split [e0;e1;e2;...;en] = ([e0;e2;e4;...],[e1;e3;e5;...])
*)
val split : 'a list -> 'a list * 'a list
(* invert_pairs échange la position de l'élément d'indice 2i avec l'élément d'indice 2i+1,
invert_pairs [e0;e1;e2;e3;e4;...] = [e1;e0;e3;e2;e5;e4;...]
Si la liste est impaire, le dernier élément n'est pas modifié.
*)
val invert_pairs : 'a list -> 'a list
(* couple renvoie la liste des paires successives de la liste,
couple [e0;e1;e2;...;en] = [(e0,e1);(e1,e2);...;(e{n-1},en)]
*)
val couple : 'a list -> 'a * 'a list
(* triangle calcule toutes les listes suffixes d'une liste :
triangle [e0;e1;e2;e3;...] = [[e0;e1;e2;...];[e1;e2;e3;...];[e2;e3;e4;...];...]
*)
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 :

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