Premiers pas en OCaml/Structures de données

Début de la boite de navigation du chapitre

fin de la boite de navigation du chapitre

Les types primitifs vus au chapitre 3 sont la base des données, mais nous avons besoin de les organiser dans des structures pour pouvoir faire des manipulations plus complexes dans nos programmes.

Les listes

Les listes sont une séquence d'éléments successifs :

# [1; 2; 3; 4; 5] ;;
- : int list = [1; 2; 3; 4; 5]

Les listes ne sont qu'un conteneur, elles peuvent contenir n’importe quel autre type. Ci-dessus une liste d'entiers, ci-dessous une liste de chaîne de caractères :

# ["alpha"; "beta"; "gamma"; "delta"] ;;
- : string list = ["alpha"; "beta"; "gamma"; "delta"]

Les tableaux

# [| "alpha"; "beta"; "gamma"; "delta" |] ;;
- : string array = [|"alpha"; "beta"; "gamma"; "delta"|]

Différence entre tableaux et listes

Les listes sont une structure où l'accès des éléments est réalisé par parcours séquenciellement à partir du premier élément (appelé la tête). Leur construction est réalisée par empilement de nouveaux éléments à sa tête, et leur déconstruction par filtrage de motif.

Les tableaux sont une structure dont le nombre d'éléments reste le même, et où l’on peut accéder à n’importe lequel de ses éléments directement.

Les tableaux sont modifiables contrairement aux listes qui ne le sont pas. Les tableaux sont donc des structures impératives, et les listes des structures fonctionnelles.

Construction d'une liste

Il est possible de construire une liste à partir d'une liste vide. Une liste vide se définit comme suit :

# [] ;;
- : 'a list = []

Voici comment empiler un élément sur une liste :

# 24 :: [] ;;
- : int list = [24]

Il est possible d'empiler autant d'éléments qu'on le souhaite à la fois :

# 'A' :: 'B' :: 'C' :: 'D' :: ['E'; 'F'; 'G'] ;;
- : char list = ['A'; 'B'; 'C'; 'D'; 'E'; 'F'; 'G']

Déconstruction d'une liste

La déconstruction d'une liste permet d'accéder à ses éléments et de faire divers manipulations. La déconstruction d'une liste s'effectue par filtrage de motif qui est le sujet du chapitre suivant.

Itérateurs sur les listes

La bibliothèque standard d'OCaml fournit un module List qui met à disposition un certain nombre d'itérateurs pour les listes dont :

# List.iter ;;
- : ('a -> unit) -> 'a list -> unit = <fun>

# List.map ;;
- : ('a -> 'b) -> 'a list -> 'b list = <fun>

# List.fold_left ;;
- : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a = <fun>

# List.iter print_endline ["alpha"; "beta"; "gamma"; "delta"] ;;
alpha
beta
gamma
delta
- : unit = ()

# List.map int_of_char ['A'; 'B'; 'C'; 'D'; 'E'; 'F'; 'G'] ;;
- : int list = [65; 66; 67; 68; 69; 70; 71]

# List.fold_left ( + ) 0 [1; 2; 3; 4; 5; 6; 7; 8] ;;
- : int = 36

Initialisation d'un tableau

Le module Array de la bibliothèque standard fournit la fonction suivante :

# Array.init ;;
- : int -> (int -> 'a) -> 'a array = <fun>

Qui s'utilise en lui fournissant le nombre d'éléments que doit contenir le tableau, ainsi qu'une fonction qui reçoit en argument l'indice de l'élément qu'elle doit retourner :

# let my_arr = Array.init 10 (fun i -> i + 1) ;;
val my_arr : int array = [|1; 2; 3; 4; 5; 6; 7; 8; 9; 10|]

# let my_arr2 = Array.init 8 (fun i -> i * 10) ;;
val my_arr2 : int array = [|0; 10; 20; 30; 40; 50; 60; 70|]

Accès aux éléments d'un tableau

Pour un tableau contenant n éléments, ceux-ci sont indexés de 0 à n - 1. 0 étant le premier, et n - 1 le dernier.

# let my_arr = [| 2.0; 3.2; 6.8; 7.3; 12.0 |] ;;
val my_arr : float array = [|2.; 3.2; 6.8; 7.3; 12.|]

# my_arr.(2) ;;
- : float = 6.8

Tenter un accès en dehors de ses limites lèvera une exception :

# my_arr.(30) ;;
Exception: Invalid_argument "index out of bounds".

Conversions entre listes et tableaux

Deux fonctions permettent de convertir les listes en tableaux et inversement :

# Array.of_list ;;
- : 'a list -> 'a array = <fun>

# Array.to_list ;;
- : 'a array -> 'a list = <fun>

Les tuples

Les tuples permettent d'agréger plusieurs éléments ensemble.
Ceux-ci peuvent-être de même type ou de types différents.

# 14, "abricot" ;;
- : string * int = (14, "abricot")

# (22, 107, 5, ['K'; 'S']) ;;
- : int * int * int * char list = (22, 107, 5, ['K'; 'S'])

Les variants

Les variants sans arguments

Les variants simples sont une énumération de différentes valeurs possibles.

Voici un exemple de définition :

# type my_variant =
    | Alpha
    | Beta
    | Gamma
    | Delta
  ;;
type my_variant = Alpha | Beta | Gamma | Delta

Le premier caractère doit être une lettre majuscule.

En utilisation :

# Gamma ;;
- : my_variant = Gamma

Les variants comme constructeurs

Les variants peuvent également être utilisés pour regrouper des types de données hétérogènes.

Définition :

# type points =
    | Point2D_real of float * float
    | Point3D_real of float * float * float
    | Point2D_discrete of int * int
    | Point3D_discrete of int * int * int
  ;;
type points =
    Point2D_real of float * float
  | Point3D_real of float * float * float
  | Point2D_discrete of int * int
  | Point3D_discrete of int * int * int

Utilisation :

# Point2D_discrete (3, 4) ;;
- : points = Point2D_discrete (3, 4)

Les enregistrements

Les enregistrements (record en anglais) sont un type qui doit être défini avant de pouvoir être utilisé.

Ici nous définissons un enregistrement dont le type s'appellera « vector » et qui contient trois éléments de type flottant. Chacun de ses éléments pourra être accédé à partir d'une étiquette, ici respectivement x, y et z :

# type vector = {
    x: float;
    y: float;
    z: float;
  } ;;
type vector = { x : float; y : float; z : float; }

Un élément de type vector est alors ensuite définit comme suit :

# let v = { x = 3.0; y = 4.0; z = 5.0 } ;;
val v : vector = {x = 3.; y = 4.; z = 5.}

Et on accède à ses sous-éléments en utilisant ses étiquettes :

# v.x ;;
- : float = 3.

Tableau récapitulatif

Voir la fiche de synthèse.