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 : 'a list -> 'a
val cut : int -> 'a list -> 'a list * 'a list
val maximum : int list -> int
val even_only : 'a list -> 'a list
val indice : 'a list -> (int * 'a) list
val intersperse : 'a -> 'a list -> 'a list
val split : 'a list -> 'a list * 'a list
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;\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.