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é:
val last : 'elt list -> 'elt
val cut : int -> 'elt list -> 'elt list * 'elt list
val maximum : int list -> int
val even_only : 'elt list -> 'elt list
val indice : 'elt list -> (int * 'elt) list
val intersperse : 'elt -> 'elt list -> 'elt list
val split : 'elt list -> 'elt list * 'elt list
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 :
val map : ('elt -> 'image) -> 'elt list -> 'image list
val filter : ('elt -> bool) -> 'elt list -> 'elt list
val flatten : 'elt list list -> 'elt list
val fold_left : ('accu -> 'elt -> 'accu) -> 'accu -> 'elt list -> 'accu
val for_all : ('elt -> bool) -> 'elt list -> bool
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
É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.
