Premiers pas en OCaml/Structures de données
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é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
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é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
Voir la fiche de synthèse.