Leçons de niveau 14

Premiers pas en OCaml/Structures de données

Une page de Wikiversité.
Sauter à la navigation Sauter à la recherche
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 listes[modifier | modifier le wikicode]

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[modifier | modifier le wikicode]

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


Différence entre tableaux et listes[modifier | modifier le wikicode]

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[modifier | modifier le wikicode]

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 liste[modifier | modifier le wikicode]

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[modifier | modifier le wikicode]

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[modifier | modifier le wikicode]

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[modifier | modifier le wikicode]

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[modifier | modifier le wikicode]

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[modifier | modifier le wikicode]

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[modifier | modifier le wikicode]

Les variants sans arguments[modifier | modifier le wikicode]

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[modifier | modifier le wikicode]

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[modifier | modifier le wikicode]

Les enregistrements (record en anglais) sont un type qui doit être définit 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[modifier | modifier le wikicode]

Voir la fiche de synthèse.