Retour au sommaire.

Comment construire une liste.

Nous avons discuter des façons de manipuler et transformer des listes, mais hormis par construction explicite nous ne savons pas en créer. En fait très fréquemment, les listes proviendront de fonctions dans diverses librairies. Dans l'exemple du comptage des fichiers sources, nous avons utilisé Sys.ls_dir pour lister les éléments d'un répertoire. Les listes sont une structure très standard en OCaml et les fonctions retournant des collections de valeurs le font en général en retournant des listes.

Le module List de la librairie standard ne fournit pas de fonction permettant de créer des listes à partir de rien (depuis OCaml 4.06.0 , List.init fait partie de la librairie standard). Core.Std.List en propose deux.

• range permet de créer la liste de tous les entiers entre deux bornes.

  1. open Core.Std
     
  2. 
     
  3. let list1 = List.range 0 10 (* list1 = [0;1;2;3;4;5;6;7;8;9] *)
     
  4. let list2 = List.range ~stop:`inclusive 0 10
     
  5. (* list2 = [0;1;2;3;4;5;6;7;8;9;10] *)
     
  6. let list3 = List.range ~stride:2 0 10 (* list3 = [0;2;4;6;8] *)
     
  7. let list4 = List.range ~stride:2 1 10 (* list3 = [1;3;5;7;9] *)
     

  Les arguments optionnels permettent de paramétrer plus finement la fonction. ~start et ~stop permettent de préciser si la borne minimum (~start) et la borne maximum (~stop) doivent être incluses (`inclusive) ou exclues (`exclusive). ~stride:k permet d'aller de $k$ en $k$ en partant du minimum.

• init construit une liste d'une longueur donnée, la valeur du $i$^e élément est donné par une fonction.

  1. let ints = List.init 10 ~f:(fun i -> i) (* ints = [0;1;2;3;4;5;6;7;8;9] *)
     
  2. let squares = List.init 10 ~f:(fun i -> i * i)
     
  3. (* squares = [0;1;4;9;16;25;36;49;64;81] *)
     
  4. let chars = List.init 26 ~f:(fun i -> char_of_int (i + int_of_char 'a'))
     
  5. (* chars = ['a';'b';'c';'d';...;'y';'z'] *)
     
  6. 
     
  7. (* a possible definition of [init] *)
     
  8. let init length ~f =
     
  9. List.range length
     
  10. |> List.map ~f
      

Quelques fonctions essentielles sur les listes.

Toutes les fonctions que nous avons vu sont fondamentales pour la manipulation des listes. Mais il nous en manque encore quelques unes.

• List.sort, List.stable_sort permettent de trier une liste (la deuxième version garantit que le tri est stable : l'ordre relatif d'éléments égaux n'est pas modifié). La fonction prend en argument la fonction de comparaison.

  1. val List.sorted : ('elt -> 'elt -> int) -> 'elt list -> 'elt list
     
  2. val Core.Std.List.sorted : 'elt list -> cmp:('elt -> 'elt -> int) -> 'elt list
     
  3. 
     
  4. let sorted = List.sort [1;5;3;4;8;7;2;9] ~cmp:(fun a b -> a - b)
     
  5. (* sorted = [1;2;3;4;5;7;8;9] *)
     

• Core.Std.List.zip = List.combine prend deux listes de même longueur et en crée une seule de même longueur, donc le $i$^e élément est la paire du $i$^e élément de la première liste avec le $i$^e élément de la deuxième liste.

  1. let pairs = Core.Std.zip [1;2;3] ['a';'b';'c']
     
  2. (* pairs = [(1,'a'); (2,'b'); (3,'c')] *)
     

  La fonction n'est pas définie si les listes n'ont pas la même longueur, elle provoquera donc une erreur à l'exécution dans ce cas. La fonction inverse, prenant une liste de paires et retournant une paire de listes, s'appelle List.split = Core.Std.List.unzip.

  zip, c'est la fermeture éclair en anglais.

• nth permet de récupérer le $i$^e élément d'une liste (commençant à l'indice 0). length retourne la longueur de la liste. On a donc :

  1. let last list = List.nth list (List.length list - 1)
     

• map, fold_left, exists et les autres fonctionnelles de listes ont des versions map2, fold_left2, exists2, qui permettent d'appliquer une fonction prenant deux arguments, un dans chaque liste. C'est équivalent à utiliser zip, puis la fonctionnelle usuelle.

Retour au sommaire.