Listes

Un article de Mangue.org, l'encyclopéde libre.

La seule construction que nous connaissons jusqu'à présent pour rassembler des données est le n-uplet. Les produits cartésiens sont peu pratiques, en effet il n'existe aucune fonction permettant d'isoler des éléments autres que le premier ou le deuxième.
Avec les listes nous allons pouvoir faire varier le nombre d'éléments facilement et les isoler plus rapidement. En contre partie il y a des limitations, tous les éléments d'une liste doivent être du même type (int par exemple)

Sommaire

1 Construction de listes 2 Filtrage sur les listes 3 Exercices 4 Fonctions sur les listes 5 Exercices 6 Application : fonction de tri polymorphe

Construction de listes

Comme en mathématiques il existe des listes vides. Une liste est tout simplement une suite finie et ordonnée d'éléments du même type.
En Caml, les listes sont encadrées par des crochets et les éléments de cette liste sont séparés par des points virgules comme dans l'exemple suivant :

# [ 1; 2; 3; 4; 5 ] ;;
- : int list = [1; 2; 3; 4; 5]
# [ `r`; `s`; `t`] ;;
- : char list = [`r`; `s`; `t`]
# [
   [0.0;1.0;2.0];
   [1e-5;235.156;123.221;0.011];
   []
  ] ;;
(* liste de listes donc ! *)
- : float list list =
 [[0.0; 1.0; 2.0]; [1e-005; 235.156; 123.221; 0.011]; []]
# [] ;;
- : 'a list = []

Une liste vide est typée en 'a list tout simplement puisque si elle ne contient aucun élément le compilateur n'a aucun moyen de savoir s'il s'agit d'une liste d'entiers, de nombres réeles ou encore de fonctions !

Vous pouvez construire autant de listes que vous le désirez en énumérant ses valeurs comme nous venons de le faire. Mais en général dans un programme on construit surtout les listes en y ajoutant des valeurs ou en les fusionnant avec d'autres listes.

Vous pouvez utiliser l'opérateur :: pour ajouter une valeur à une liste. Vous pouvez aussi utiliser l'opérateur @ pour fusionner deux listes entre elles.
Ces opérateurs ont la particularité d'être associatifs à gauche, c'est à dire que vous pouvez les enchaîner sur une même ligne, Caml se chargera lui même d'ajouter les valeurs dans l'ordre que vous désirez

# let liste_vide = [] ;;
liste_vide : 'a list = []
# 63 :: liste_vide ;;
- : int list = [63]
# true :: liste_vide ;;
- : bool list = [true]
# 1e1 :: 1e2 :: 1e3 :: liste_vide ;;
- : float list = [10.0; 100.0; 1000.0]
# liste_vide :: liste_vide ;;
- : 'a list list = [[]]
# liste_vide :: 4 ;;
Toplevel input:
> liste_vide :: 4 ;;
>               ^
This expression has type int,
but is used with type 'a list list.
# 0.0 :: [1;2;3] ;;
Toplevel input:
> 0.0 :: [1;2;3] ;;
>        ^^^^^^^
This expression has type int list,
but is used with type float list.
#[1;2;3] = (1 :: 2 :: 3 :: liste_vide) ;;
- : bool = true
#[1;2;4] >= (1 :: 2 :: 3 :: liste_vide) ;;
- : bool = true
# [0] @ [1;2;3] ;;
- : int list = [0; 1; 2; 3]
# [0.0] @ [0;1;2;3] ;;
Toplevel input:
> [0.0] @ [0;1;2;3] ;;
>         ^^^^^^^^^
This expression has type int list,
but is used with type float list.
# liste_vide @ [1e-1;1e0;1e1] ;;
- : float list = [0.1; 1.0; 10.0]
# 0 :: [1] @ [2;3] ;;
- : int list = [0; 1; 2; 3]
# liste_vide @ liste_vide ;;
- : '_a list = []

Danger

Attention à ne pas vous trompez dans l'opérateur que vous utilisez. Dans la plus part des cas vous obtiendrez un message d'erreur mais il peut arriver que votre requète soit évaluée correctement dans quel cas vous n'aurez pas du tout le résultat attendu !

Le Caml évalue ce type d'expression de droite à gauche (oui on lit de droite à gauche dans le pays d'origine des chameaux). Voici quelques exempels avec des parenthèses pour vous montrer comment le Caml procède. En pratique les parenthèses ne sont pas requises mais vous pouvez les indiquer systématiquement si vous avez des doutes :

# let liste = [7] ;;
liste : int list = [7]
# 6 :: liste ;;
- : int list = [6; 7]
# 5 :: ( 6 :: liste) ;;
- : int list = [5; 6; 7]
# 4 :: ( 5 :: ( 6 :: liste)) ;;
- : int list = [4; 5; 6; 7]
# 4 :: ( [5] @ ( 6 :: liste)) ;;
- : int list = [4; 5; 6; 7]
# 4 :: [5] @ ( 6 :: liste) ;;
- : int list = [4; 5; 6; 7]
# 3 :: 4 :: [5] @ ( 6 :: liste) ;;
- : int list = [3; 4; 5; 6; 7]
# 1 :: [2;3;4] @ 5 :: 6 :: liste ;;
- : int list = [1; 2; 3; 4; 5; 6; 7]

Filtrage sur les listes

Il est aussi possible d'utiliser des filtres sur les listes. Ca devient même indispensable pour les fonctions que nous allons écrire dans la suite de ce cours.
Commençons d'abord par les introduire progessivement au travers d'exemples dans lesquels nous faisons des définitions simples en utlisant des listes :

# let notre_liste = [0;1;2;3;4;5;6;7;8;9] ;;
notre_liste : int list = [0; 1; 2; 3; 4; 5; 6; 7; 8; 9]
# let (zéro :: reste_de_la_liste) = notre_liste ;;
Toplevel input:
> let (zéro :: reste_de_la_liste) = notre_liste ;;
> ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Warning: this matching is not exhaustive.
zéro : int = 0
reste_de_la_liste : int list = [1; 2; 3; 4; 5; 6; 7; 8; 9]
# let élément :: reste = [fst;snd] ;;
Toplevel input:
> let élément :: reste = [fst;snd] ;;
> ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Warning: this matching is not exhaustive.
élément : 'a * 'a -> 'a = <fun>
reste : ('a * 'a -> 'a) list = [<fun>]
# let premier_reste (premier :: reste) = (premier,reste) ;;
Toplevel input:
> let premier_reste (premier :: reste) = (premier,reste) ;;
>     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Warning: this matching is not exhaustive.
premier_reste : 'a list -> 'a * 'a list = <fun>
# premier_reste [1e5;1e3;1e6] ;;
- : float * float list = 100000.0, [1000.0; 1000000.0]
# premier_reste [];;
Uncaught exception: Match_failure ("", 750, 800)

Vous pourriez vous demander d'où viennent ces mises en garde du compilateur. En effet nous cherchons simplement à "filtrer" une constante de type int list, il ne devrait pas y avoir de problèmes :(
Cependant le Caml ne sait pas ce que votre liste contient, il regarde simplement le type et voit int list, pour lui rien n'empèche quel a liste soit vide et donc que ce filtre n'ait aucun sens. C'est justement contre ça qu'il vous met en garde !

Nous allons écrire ensemble une fonction récursive longueur nous indiquant la longueur d'une liste. Pour ça nous allons utiliser un filtrage très simple.
Lorsque la liste est vide elle ne contient aucun élément, elle est donc de longueur 0. Ce sera notre cas d'arrêt, pour le cas général je vous propose d'ajouter une unité à chaque fois que nous retirons un élément de la liste. Voilà ce que ça donne en Caml :

# let rec longueur = fun
|       []     -> 0
| (_ :: reste) -> 1 + longueur (reste) ;;
longueur : 'a list -> int = <fun>
# longueur [] ;;
- : int = 0
# longueur [fst;snd] ;;
- : int = 2
# longueur notre_liste ;;
- : int = 10

Danger

N'oubliez pas de mettre des parenthèses autour de votre argument, sans quoi le compilateur génèrerait un message d'erreur : "Syntax error"

Il arrivera dans bien des fonctions que nous allons écrire que le motif du filtre serve tel quel dans un résultat ou dans une expression. L'opérateur as permet de définir des synonymes dans les filtres comme nous le montre l'exemple qui suit.<br /<Le but est d'améliorer la lisibilité de votre programme biensûr, alors ne vous en privez pas !

# let (abs_monome : float * int -> float * int) = function
(* renvoie la valeur absolue d'un monome du type a·x^n *)
(a, degré) as monome -> if (a<. 0.0) then (-.a,degré) else monome ;;
abs_monome : float * int -> float * int = <fun>

Remarque

Ce constructeur ne sera que très rarement utilisé dans mes cours. Et ça pour une raison très simple, il ne fonction que sur les fonctions à un seul argument (mot clé function donc). Même s'il est toujours possible d'utiliser ce mot clé même pour une fonction à 2 arguments (vous verriez alors apparaître deux fois le mot clé function), nous ne "perdrons" pas de temps à ça.

Exercices

Je vous vous demander d'écrire des fonctions très simples. Vous ne devriez pas y réfléchir très longtemps mais ça vous permettra néanmoins de manipuler un peu les listes ;-)

Ecrivez une fonction somme calculant la somme des éléments entiers d'une liste. Vous vous en doutez cette fonction est récursive...
Voici une correction :

# let rec somme = fun
|      []       -> 0
| (a :: reste ) -> a + somme (reste) ;;
somme : int list -> int = <fun>
#somme [1;2;3;4] ;;
- : int = 10
# somme ( 0 :: 1 :: 2 :: 3 :: [4;5;6] @ notre_liste) ;;
- : int = 66

Un peu sur le même modèle écrivez une fonction moyenne permettant de calculer la moyenne d'un ensemble de notes (des nombres réels donc). Difficulté supplémentaire cette fonction doit aussi vérifier que les notes sont comprises entre 0 et 20 ; si ce n'est pas le cas une erreur doit être générée.
Indication : vous pouvez bien entendu utiliser la fonction longueur déjà définie.

# let moyenne liste_de_notes =
let nombre_de_notes = longueur (liste_de_notes)
in
let rec somme_notes = fun
|            []          -> 0.0
| (note :: autres_notes) ->
  if ( (note < 0.0) || (note > 20.0))
  then failwith "moyenne: note incorrecte"
  else note +. somme_notes (autres_notes)
in
  (somme_notes (liste_de_notes)) /. float_of_int (nombre_de_notes) ;;
moyenne : float list -> float = <fun>
# moyenne [12.0;14.0;8.5;7.0;11.5;18.5;3.75] ;;
- : float = 10.75
# moyenne [10.0;4.0;18.25;21.5;18.5;0.75] ;;
Uncaught exception: Failure "moyenne: note incorrecte"

Astuce

Nous commençons à écrire des fonctions plutôt robustes. Elles sont moins faciles à comprendre que celles des premiers cours c'est évident, c'est pourquoi je vous rappelle (encore une fois) que le forum est là pour toutes vos questions. Vous ne lisez pas un livre, vous êtes sur un site Internet, nous sommes là pour vous aider :-)

Fonctions sur les listes

Il existe beaucoup de fonctions prédéfinies sur les listes, comme par exemple list_length qui correspond à la fonction longueur que nous avons implémenté.
Vous pourrez également trouver dans certains programmes les fonctions hd et tl qui vous renverront respectivement le premier élément d'une liste et tous les éléments à l'exception du premier d'une liste. Nous utiliserons plus fréquemment le filtrage pour ceci mais vous devez au moins connaître l'existence de ces fonctions.

# hd ;;
- : 'a list -> 'a = <fun>
# hd [1;2;3;4] ;;
- : int = 1
# tl ;;
- : 'a list -> 'a list = <fun>
# tl [1;2;3;4];;
- : int list = [2; 3; 4]

Il existe une fonction fort pratique répondant au doux nom de map (nom emprunté au langage Lisp) permettant d'appliquer une fonction sur tous les éléments d'une liste. Grace à elle vous pourrez donc effectuer des traitements complexes en une seule instruction.
Dans l'exemple suivant, nous utilisons map pour convertir une liste d'entiers en liste de flottant ou encore pour obtenir la valeur absolue d'une liste d'un seul coup :

# map ;;
- : ('a -> 'b) -> 'a list -> 'b list = <fun>
# map float_of_int [1;2;3;4] ;;
- : float list = [1.0; 2.0; 3.0; 4.0]
# map (fun x -> if (x<0) then -x else x) [-5;0;3;-4;3;2;2;1;-8;-6;-2;7] ;;
- : int list = [5; 0; 3; 4; 3; 2; 2; 1; 8; 6; 2; 7]
# let int_of_float_list = map int_of_float ;;
int_of_float_list : float list -> int list = <fun>
# int_of_float_list [1e5;1e-6;1e2;1e3;0.0; 4.0 *. atan(1.0)] ;;
- : int list = [100000; 0; 100; 1000; 0; 3]

Il existe beaucoup d'autres fonctionnelles sur les listes. Je vous propose d'explorer l'aide à propos du module list. Les plus utilisées seront certainement map, exists, list_it, it_list, index, rev, union, substract et enfin intersect

Exercices

Plutôt que de vous expliquer de manière théorique comment fonctionnent ces fonctionnelles je vous porpose de réécrire quelques unes d'entre elles.
Je ne vous donnerai pas de corrections ici, elles sont accessibles depuis le sommaire ds cours :-)

rev est une fonction renvoyant le mirroir d'une liste. C'est à dire la même liste mais inversée.
Nous écrirons une telle fonction de manière récursive évidemment. Voici des exemples de son utilisation :

# rev [1;2;3;4] ;;
- : int list = [4; 3; 2; 1]
# rev [fst;snd] ;;
- : ('_a * '_a -> '_a) list = [<fun>; <fun>]
# rev ;;
- : 'a list -> 'a list = <fun>

Réécrivons ensembles la fonction map. Attention celle-ci admet un paramètre qui ne varira pas (la fonction), il faut donc veiller à ce que les appels récursifs ne le fassent pas intervenir.
Indication : il s'agit donc de définir localement une fonction récursive...

# map float_of_int [1;2;3;4] ;;
- : float list = [1.0; 2.0; 3.0; 4.0]
# map (fun x -> if (x<0) then -x else x) [-5;0;3;-4;3;2;2;1;-8;-6;-2;7] ;;
- : int list = [5; 0; 3; 4; 3; 2; 2; 1; 8; 6; 2; 7]
# let int_of_float_list = map int_of_float ;;
int_of_float_list : float list -> int list = <fun>
# int_of_float_list [1e5;1e-6;1e2;1e3;0.0; 4.0 *. atan(1.0)] ;;
- : int list = [100000; 0; 100; 1000; 0; 3]
# map ;;
- : ('a -> 'b) -> 'a list -> 'b list = <fun>

exists prends en argument une fonction qui renvoie un résultat booléen et une liste de valeurs sur laquelle appliquer cette fonction.
Voici deux exemples de son application :

# not ( exists (fun x -> x = 0) [0;1;2;3;4;5]) ;;
(* vérifie qu'il n'y ait pas de 0 dans la liste *)
- : bool = false
# exists (fun x -> x *. x +. 4.0 *. x -. 5.0 =. 0.0) [-. 1.0; 0.0; 1.0] ;;
(* vérifie qu'il y ait une solution au trinôme dans la liste *)
- : bool = true
# exists ;;
- : ('a -> bool) -> 'a list -> bool = <fun>

Application : fonction de tri polymorphe

Nous allons écrire une fonction de tri polymorphe sur les listes. Nous allons utiliser une algorithme de tri par insertion, ce n'est pas le plus performant mais il a l'avantage de se coder très rapidement avec une fonction récursive. Pour résoudre ce problème, nous allons ordonner notre liste en commençant par le début et en allant vers la fin (logique jusque là).

Nous supposerons qu'une fonction insérer_élément existe, cette fonction insèrera un élément à la bonne place dans une liste triée.
Utilisons la fonction insérer_élément pour écrire notre fonction de tri, trier_liste.

C'est une fonction récursive, vous vous en doutiez. Deux cas sont à considérer, le cas général où il reste encore des éléments dans la liste que nous devrons trier et le cas simple dans lequel la liste est vide, et donc forcément triée.
Pour chacun des éléments de la liste, il nous suffira de l'insérer à la bonne position dans le reste de la liste trié. Voilà la fonction trier_liste est implémentée, mais il nous reste justement à écrire la fonction insérer_élément...

Si la liste est vide il nous suffit de la retourner avec l'élément à ajouter. Il est forcément à la bonne place dans ce cas.
Sinon on doit vérifier pour chacun des éléments de la liste si il est suppérieur ou égal à la valeur que nous souhaitons ajouter. Nous ajouterons la valeur passée en argument de la fonction insérer_éléments dès que nous tomberons sur une valeur de la liste supérieure ou égale. Si ce n'est pas le cas, les appels récursifs continueront.

Pour résoudre notre problème de tri, il nous suffirait de définir localement la fonction insérer_élément, mais nous allons tout de même la définir globalement puisqu'elle pourra vous servir par la suite.

# let insérer_élément élément liste =
let rec aux = fun
|      []      -> [élément]
| (x :: reste) -> if (élément <= x)
                  then élément :: x :: reste
                  else x :: (aux (reste))
in
  aux liste ;;
insérer_élément : 'a -> 'a list -> 'a list = <fun>
# let rec trier_liste = fun
|       []      -> []
| ( x :: reste) -> insérer_élément x (trier_liste (reste)) ;;
trier_liste : 'a list -> 'a list = <fun>
# trier_liste [1;2;3;5;0;2;4;3;1;7] ;;
- : int list = [0; 1; 1; 2; 2; 3; 3; 4; 5; 7]
# (* autre définition de trier_liste *)
(* avec insérer_élément définie localement *)
let trier_liste =
let insérer_élément élément liste =
 let rec aux = fun
 |       []      -> [élément]
 | ( x :: reste) -> if (élément <= x)
                    then élément :: x :: reste
                    else x :: (aux(reste))
 in
  aux liste
in
 let rec trie = fun
 |      []      -> []
 | (x :: reste) -> insérer_élément x (trie(reste))
in
 fun liste -> trie liste ;;
trier_liste : 'a list -> 'a list = <fun>
# trier_liste [1;2;3;1;1;2;3;-1;0;0;4;5;6;7;9;11;8] ;;
- : int list = [-1; 0; 0; 1; 1; 1; 2; 2; 3; 3; 4; 5; 6; 7; 8; 9; 11]

Astuce

Comme vous le constatez par vous même les définitions deviennent hardues, c'est la raison pour laquelle, depuis le début, je vous conseille d'utiliser au maximum les parenthèses et l'indentation.