Premiers pas en OCaml/Structures de données

Début de la boite de navigation du chapitre
Structures de données
Icône de la faculté
Chapitre no 7
Leçon : Premiers pas en OCaml
Chap. préc. :Fonctions utilitaires
Chap. suiv. :Filtrage de motif
fin de la boite de navigation du chapitre
Icon falscher Titel.svg
En raison de limitations techniques, la typographie souhaitable du titre, « Premiers pas en OCaml : Structures de données
Premiers pas en OCaml/Structures de données
 », n'a pu être restituée correctement ci-dessus.

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 listesModifier

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 tableauxModifier

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


Différence entre tableaux et listesModifier

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 listeModifier

Il est possible de construire une liste à partir d'une liste vide. Une liste vide se définie 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 listeModifier

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 listesModifier

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 tableauModifier

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 tableauModifier

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 tableauxModifier

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 tuplesModifier

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 variantsModifier

Les variants sans argumentsModifier

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 constructeursModifier

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 enregistrementsModifier

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écapitulatifModifier

Voir la fiche de synthèse.