Les Listes

Une liste contient au minimum 0 élément, elle peut en contenir 0 ou 1 ou une infinité.
Je dis ça parce que ça nous servira ;-) !

Voilà une liste d'entier:

let liste1 = [0;1;2;3;4;5;6;7;8;9;10];;
val liste1 : int list = [0;1;2;3;4;5;6;7;8;9;10]

Il n'y a que des entiers dedans.


Et voici une liste de caractères:

let liste2 = ['a';'b';'c';'d';'e';'f';'g'];;
val list2 : char list = ['a';'b';'c';'d';'e';'f';'g']

Il n'y a que des caractères dedans.
La règle est simple, une liste peut contenir un très grand nombre d'éléments mais ces éléments doivent tous être du même type.

Opérateurs de Listes

Admettons que vous ayez une liste d'élément(s), pour y concaténer un autre élément en tête de liste pensez à utiliser le double : .

let liste1 = ['c';'a';'m';'l'];;
val liste1 : char list = ['c';'a';'m';'l']

let liste2 = 'o'::liste;;
val liste2 : char list = ['o';'c';'a';'m';'l']

Cet opérateur ne s'utilise qu'avec un élément et une liste du même type que l'élément.

Vous voulez concaténer deux listes ? Utilisez l'arobase @:

let liste1 = [-3;-2;-1];;
val liste1 : int list = [-3;-2;-1]

let liste2 = [1;2;3];;
val liste2 : int list = [1;2;3]

let liste3 = liste1@liste2;;
val liste3 : int list = [-3;-2;-1;0;1;2;3]

A n'utiliser qu'avec deux listes du même type.

Si vous compilez et exécutez (>ocamlc et >./a.out) vous ne verrez pas s'afficher ces deux listes. Je vais vous donner la fonction permettant d'afficher une liste d'entier:

let rec print_list l = match l with
 |[] -> ()
 |e::f -> print_int e; print_string " "; print_list f;;

print_liste [1;2;3;4;5;6;7;8;9;10];;

1 2 3 4 5 6 7 8 9 10

Je précise que vous n'avez pas besoin de comprendre cette fonction, je vous la donne juste pour que vous vous en serviez. Vous la comprendrez tous un peu plus tard !

Fonctions Prédéfinies

Deux fonctions sur les listes à connaître absolument List.hd et List.tl (hd pour head et tl pour tail).
List.hd renvoie la "tête" de la liste avec laquelle on l'appelle (c'est-à-dire le premier élément), List.tl renvoie la "queue" de la liste avec laquelle on l'appelle.

Ces deux fonctions n'ont pas la même signature :

List.hd;;
- : 'a list -> 'a

List.tl;;
- : 'a list -> 'a list

List.hd renvoie le premier élément de la liste donc renvoie un (seul) élément.
List.tl renvoie une liste d'élément(s) sans la tête.

List.hd:

print_int ( List.hd [1;2;3] );;
1

List.tl:

print_list (List.tl [1;2;3] );;
2 3

List.length [4.;5.;9.;23.;33.;32.];;
- : int = 6

List.mem 3 [3;5;7];;
- : bool = true

List.mem 'z' ['o';'c';a';'m';'l'];;
- : bool = false

let f x = x-1 in List.map f [12;23;45;89];;
- : int list [11;22;44;88]

let g x = if x > 0 then true else false in List.for_all g [56;123;90;67;32;-4;6];;
- : bool = false

let h x y = y - x in List.sort h [12;23;45;89];;
- : int list = [89;45;23;12]

let miroir liste = List.rev liste in miroir [0;1;2;3;4;5;6;7;8;9];;
- : int list = [9;8;7;6;5;4;3;2;1;0]

Match With What ? (part 2)

Vous vous souvenez bien sûr du match with ? Parce qu'on en a besoin pour les fonctions Récursives qui utilisent les listes . . .

let rec longueur_liste l = match l with
 |[] → 0 (* Si la liste est vide, alors la longueur est 0 *)
 |e::f → 1 + longueur_liste f;; (* Sinon on ajoute 1 et on rappelle la fonction avec la "queue" *)

Cette fonction est récursive, elle calcule le nombre d'éléments dans notre liste.
L'utilité du match with sur les listes est de pouvoir décomposer des éléments de cette liste. Explications des deux dernières lignes:

 |[] -> 0

On regarde si la liste l est vide, si c'est le cas alors on renvoie 0. C'est tout simplement le cas d'arrêt de notre fonction.

  |t::q -> 1 + longueur_liste f;;

Vous vous souvenez de la première chose que j'ai dit sur cette page 8-o ?
Une liste contient soit 0 élément, soit plusieurs éléments. Donc si vous avez suivi, on a déjà géré le cas où la liste est vide (le cas d'arrêt). Cette dernière ligne gère donc le cas où la liste n'est pas vide. >t représente la "tête" de la liste et >q sa "queue". A chaque récursion, on décompose la liste >t::q on oublie >t, on ajoute 1 et on rappelle la fonction avec >q.

Dans le match, vous choisissez de décomposer avec les lettres que vous voulez.
Avec >t et >q vous ne serez pas perdu (tête et queue).

print_string "La liste [1;2;3;4;5;6] contient ";;
print_int (longueur_liste [1;2;3;4;5;6]);;
print_string "éléments.";;

Nous affiche à l'écran:

La liste [1;2;3;4;5;6] contient 6 éléments.

Calculons longueur_liste [1;2;3]:
longueur_liste [1;2;3] =
1 + longueur_liste [2;3].................................................................Or longueur_liste [2;3] = 1 + >longueur_liste [3]
1 + 1 + >longueur_liste [3] ...................................................................Or >longueur_liste [3] = 1 + longueur_liste []
1 + 1 + 1 + longueur_liste [].....................................................................Or longueur_liste [] = 0
1 + 1 + 1 + 0
1 + 1 + 1
1 + 2
3
Au final on a: longueur_liste [1;2;3] = 1 + 1 + 1 + 0 = 3

Comme on a déjà vu la récursivité, la seule chose nouvelle ici est la décomposition de la liste envoyée en paramètre.
Cas d'arrêt: Quand la liste est vide [] on renvoie 0 (logique).
Paramètre variant: On rappelle la fonction avec la queue de la liste.

Voici la même fonction longueur_liste qui n'utilise pas de match with:

let rec longueur_liste l =
 if l = [] then 0
 else 1 + longueur_liste (List.tl l);;

Les deux méthodes fonctionnent mais je conseille de vous mettre au match with ;-) !

Le tutoriel est déjà bien avancé mais pas fini !
Question théorie vous devriez en avoir assez pour vous débrouiller au premier contrôle :-/ , pour en être sûr, direction les exercices !!! Mais si vous en voulez encore, vous pouvez apprendre les enregistrement qui vont devenir primordial pour vos prochains "gros" programmes (mais aussi d'une manière générale en Programmation).