Programmation Fonctionnelle, TD3

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é:

(* last renvoie le dernier élément de la liste *)
val last : 'a list -> 'a
(* cut i list : coupe la liste en deux, un préfixe de longueur i,
et le suffixe des éléments restants.
*)
val cut : int -> 'a list -> 'a list * 'a list
(* maximum retourne l'élément maximum d'une liste *)
val maximum : int list -> int
(* 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
(* indice ajoute un indice à chaque élément de la liste
indice [5;3;6;2] = [(0,5); (1,3); (2,6); (3,2)]
*)
val indice : 'a list -> (int * 'a) list
(* intersperse ajoute un élément entre toute paire d'éléments consécutifs d'une liste
intersperse 1 [2;3;4;1;5] = [2;1;3;1;4;1;1;1;5]
*)
val intersperse : 'a -> '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
(* 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 échange, vous pouvez utiliser les fonctionnelles de liste que vous connaissez :

val map : ('a -> 'b) -> 'a list -> 'b list
val filter : ('a -> bool) -> 'a list -> 'a list
val flatten : 'a list list -> 'a list
val fold_left : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a
val for_all : ('a -> bool) -> 'a list -> bool
val exists : ('a -> bool) -> 'a 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}; \dots; e_{n}]$ est un palindrome si $e_{i} = e_{n - i}$ pour tout $i \in [0, n]$ .

Exercice 5 : Tri rapide

É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$ .
Écrire une fonction bigger, qui renvoie cette fois la liste des éléments strictement plus grand que $a$ .
En déduire l'algorithme de tri rapide.
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.