Lycée Claude Fauriel MP2I
TRAVAUX PRATIQUES IX
Listes OCaml
Le type list ne contient que des éléments d’un même type 'a . Une liste est :
Définition 1
— Soit la liste vide []
— Soit de la forme h::t , où h est un élément de type 'a' appelé tête (head), et t est le reste de la liste
appelée queue (tail) de la liste.
C’est donc un type récursif, qui doit être manipulé avec des filtrages (et des récursions).
On ne peut accéder qu’à l’élément de la tête de pile. Ainsi, le premier élément que l’on met dans une pile se retrouve
tout en bas de la pile, et sera le dernier à en ressortir. Au contraire, la dernière entrée est la première à sortir. On verra
plus tard en cours que cette structure est ce que l’on appelle également une pile.
Dans ce TP, on recode des fonctions de la librairie OCaml. Bien sûr, plus tard vous ne les recoderez plus mais utiliserez
les versions de OCaml.
A Premières fonctions
1. Écrire une fonction is_empty qui prend en argument une liste et renvoie si elle est vide ou non.
2. Écrire une fonction print_int_list qui affiche successivement les éléments d’une liste d’entiers (sans se
prendre la tête sur la mise en forme).
(Bonus) Si vous êtes motivés, vous pouvez faire en sorte que votre fonction affiche [… ;… ;…] à la place. Vous devrez
utiliser des string.
3. Écrire une fonction length qui prend en argument une liste et renvoie son nombre d’éléments.
4. Écrire une fonction mem : 'a -> 'a list -> bool qui prend en argument un élément, une liste et teste si
cet élément est dans la liste.
mem x [a1; ...; an] renvoie vrai si l’un des éléments a1 , …, an est égal à x, et faux sinon.
5. Écrire une fonction cat : 'a list -> 'a list -> 'a list qui prend en argument deux listes (de même
type) et renvoie la nouvelle liste constituée de la première suivie de la seconde (elle recode l’opérateur ”@”).
cat [a1; ...; an] [b1; ...; bn] renvoie [a1; ...; an; b1; ...; bn] .
B Fonctions de listes et booléens
6. Écrire une fonction exists : ('a -> bool) -> 'a list -> bool qui prend en argument une fonction de
type 'a -> bool (dans l’idée, une fonction qui teste si un élément vérifie une certain propriété) et une liste, et
qui teste s’il existe un élément de la liste sur lequel la fonction s’évalue à true (dans l’idée, s’il existe un élément
qui vérifie la propriété).
exists f [a1; ...; an] renvoie vrai si l’un des f a1 , …, f an est vrai, et faux sinon.
7. Écrire une fonction for_all : ('a -> bool) -> 'a list -> bool qui prend en argument une fonction
de type 'a -> bool et une liste et qui teste si sur tous les éléments de la liste la fonction s’évalue à true (dans
l’idée, si tous les éléments vérifient la propriété).
for_all [a1; ...; an] renvoie vrai si tous les f a1 , …, f an sont vrai, et faux sinon.
1
TP IX. Listes OCaml
8. Écrire une fonction filter qui prend en argument une fonction de type 'a -> bool et une liste et qui renvoie
la liste uniquement composée des éléments de la liste sur lesquels la fonction s’évalue à true.
filter [a1; ...; an] renvoie la liste des ai tels que f ai est vrai.
C Fonctions avancées
9. Écrire une fonction map : ('a -> 'b) -> 'a list -> 'b list qui prend en argument une fonction et
une liste et renvoie la liste composée des images de la première par la fonction (dans le même ordre).
map f [a1; ...; an] renvoie la liste [f a1; ...; f an] .
10. Écrire une fonction iter : ('a -> unit) -> 'a list -> unit qui prend en argument une procédure
(fonction de sortie unit) et une liste et applique la fonction successivement à tous les éléments de la liste.
iter f [a1; ...; an] est équivalent begin f a1; f a2; ...; f an; () end .
D Comparaisons et Tris
Dans cette section, on utilise le comportement suivant pour une fonction de comparaison : elles renvoient un entier
négatif si le premier argument est strictement inférieur au second, 0 s’ils sont égaux, et 1 sinon.
11. Écrire une fonction compare : ('a -> 'a -> int) -> 'a list -> 'a list -> int qui prend en argu-
ment une fonction de comparaison, deux listes, et compare lexicographiquement les deux listes (c’est l’ordre du
dictionnaire : on compare d’abord le premier élément, puis le second, etc).
12. Écrire une fonction sort : ('a -> 'a -> int) -> 'a list -> 'a list qui prend en argument une
fonction de comparaison, une liste, et renvoie une nouvelle liste égale à sa liste argument triée par ordre croissant.
On pourra faire un tri par insertion récursif (en 𝑂(𝑛2 )) : à chaque étape, on rajoute un élément dans une liste déjà
triée, comme pour trier un jeu de cartes.
E Pour occuper les plus rapides
13. Écrire une fonction rev qui prend en argument une liste et renvoie cette même liste mais en ordre inverse.
rev [a1; ...; an] renvoie la liste [an; ...; a1] .
14. a. Écrire une fonction isole : int -> 'a list -> 'a list telle que isole n lst renvoie les n
premiers éléments de lst. Si lst contient moins de n éléments, elle les renvoie tous.
b. Écrire une fonction enleve : int -> 'a list -> 'a list telle que enleve n lst renvoie la liste
lst privée de ses n premiers éléments. Si lst contient moins de n éléments, elle renvoie une liste vide.
15. Écrire une fonction fold_left : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a qui étant donnée une
fonction f, un élément 𝑎 et une liste [𝑏0 ; 𝑏1 ; ...; 𝑏𝑘−1 ] calcule f (... (f (f a 𝑏0 ) 𝑏1 ) ...) 𝑏𝑘−1 . Inspirez-
vous de la recherche de maximume dans une liste, et recodez là si besoin.
16. Faire de même une fonction fold_right 'a -> 'b -> 'a) -> 'a list -> 'b -> 'a qui étant donnée
une fonction f , une liste [𝑎0 ; 𝑎1 ; ...; 𝑎𝑘−1 ] calcule f 𝑎0 (f 𝑎1 (... (f 𝑎𝑘−1 b))) .