Éléments de syntaxe d'Ocaml

Version & licenses
Creative Commons License

Un peu de syntaxe de base

Guyslain Naves

Manipulations de bases

  1. (* Définition une liste est soit vide, soit un élément suivi d'une liste *)
  2. type 'a list =
  3. | []
  4. | (::) of 'a * 'a list

:: est l'insertion en tête (gauche) de liste. On ne peut pas l'utiliser pour ajouter un élément à la fin (droite) de la liste. Les listes se manipulent uniquement depuis la gauche. Accèder à la droite demander de parcourir toute la liste, ce qui a une complexité linéaire par rapport au nombre d'éléments.

La définition des listes est inductive : elles se manipulent donc naturellement avec la combinaison récursion-filtrage par motif.

  1. let rec my_function list = match list with
  2. | [] -> ...
  3. | first::others -> ...
  4. (* first : 1er élément, others : liste des autres éléments *)

  6. (* D'autres motifs sont possibles dans le match : *)
  7. | [single_elt] -> (* liste à un seul élément *)
  8. | first::second::others -> (* avec 2 éléments ou plus *)
  9. | [one;two;three] -> (* liste à 3 éléments exactement *)
  10. | ...

Principales fonctionnelles

Le triumvirat qui règne sur les listes :

  1. (* map transforme une liste en une liste de même taille *)
  2. List.map f [e1;e2;e3;...;ek] ---> [f e1; f e2; f e3; ...; f ek]

  4. (* filter garde les éléments qui vérifie une propriété *)
  5. (* en utilisant une notation mathématique (<> Ocaml) *)
  6. List.filter predicat [e1;e2;e3;...ek] ---> [ei | predicat ei]

  8. (* fold_left calcule une valeur en utilisant tous les éléments d'une liste *)
  9. List.fold_left (++) neutral [e1;e2;...;ek]
  10. ---> (...((neutral ++ e1) ++ e2 ) ...) ++ ek

Pour compléter :

  1. (* flatten aplatit une liste de listes en liste *)
  2. flatten [[a_1;...a_k];[b_1;...;k_l];...]
  3. ---> [a_1;a_2;...;a_k;b_1;b_2;...;b_l;c_1;...]

  5. (* pour chainer des opérations, définir : *)
  6. let rec bind list ~f =
  7. list
  8. |> List.map f
  9. |> List.flatten
  10. let (>>=) list f = bind list ~f
  11. (* bind : 'elt list -> ~f:('elt -> 'im list) -> 'im list *)

  13. (* Exemple : construire toutes les paires d'éléments de deux listes : *)
  14. let product list1 list2 =
  15. list1 >>= fun elt1 -> (* pour tout elt1 dans list1 *)
  16. list2 >>= fun elt2 -> (* pour tout elt2 dans list2 *)
  17. [(elt1,elt2)] (* construire la paire (elt1,elt2) *)

  19. let res = product [1;2;3] [4;5]
  20. (* res = [(1,4);(1,5);(2,4);(2,5);(3,4);(3,5)] *)

Tester une liste

  1. (* Test d'appartenance *)
  2. List.mem elt [e1;e2;...;ek]
  3. ---> elt = e1 || elt = e2 || ... || elt = ek

  5. (* Test de la validité de tous les éléments *)
  6. List.for_all predicat [e1;e2;...;ek]
  7. ---> predicat e1 && predicat e2 && ... && predicat ek

  9. (* Test de l'existence d'un élément valide *)
  10. List.exists predicat [e1;e2;...;ek]
  11. ---> predicat e1 || predicat e2 || ... || predicat ek
  12. (* on peut utiliser List.find pour obtenir le premier élément valide *)

Autres fonctions très utiles

  1. (* La longueur d'une liste *)
  2. List.length [a1;a2;...ak] ---> k

  4. (* La fonction de tri en ordre ascendant. *)
  5. List.sort compare_op unsorted_list ---> sorted_list
  6. (* compare_op : 'elt -> 'elt -> int, compare_op a b est comme a - b *)

  8. (* Coupler deux listes de même longueur *)
  9. List.combine [a1;a2;...;ak] [b1;b2;...;bk]
  10. ---> [(a1,b1);(a2,b2);...(ak,bk)]

  12. (* L'opération inverse de combine *)
  13. List.split [(a1,b1);(a2,b2);...(ak,bk)]
  14. ---> ([a1;a2;...;ak],[b1;b2;...;bk])