Une structure de données est l'association :
On distingue la structure abstraite de la structure concrète. La structure abstraite, également appelée interface ou spécification, décrit la structure du point de vue du programmeur qui l'utilise. C'est le mode d'emploi de la structure. La structure concrète est la façon dont est implémentée la structure. Les types abstraits deviennent des types Caml parfaitement définis et les primitives des fonctions Caml codées selon des algorithmes précis.
La caractéristique fondamentale d'une pile est que la valeur que l'on extrait est toujours la dernière valeur à avoir été placée dans la pile. On parle de structure LIFO (Last In Fast Out).
La structure abstraite de pile peut être décrite par l'embryon de code Caml ci-dessous :
type 'a stack
exception Stack_empty
(** Retourne une nouvelle pile vide *)
let create () : 'a stack = ???
(** Indique si la pile s est vide *)
let is_empty (s : 'a stack) : bool = ???
(** Retourne la valeur du sommet de la pile s *)
let peek (s : 'a stack) : 'a = ???
(** Ajoute la valeur x sur le sommet de la pile s *)
let push (s : 'a stack) (x : 'a) : unit = ???
(** Supprime et retourne la valeur du sommet de la pile s *)
let pop (s : 'a stack) : 'a = ???
Le dernier élément placé dans la pile est appelé le sommet de la pile. Les primitives push
et pop
permettent respectivement d'ajouter ou de retirer un élément.
Cette propriété ressemble à celle des listes chaînées Caml, le sommet correspondant à la tête de la liste.
La différence réside dans le fait que, contrairement aux listes, les piles sont des structures impératives.
La fonction create
permet de créer une valeur de type 'a stack
destinée à mémoriser les éléments de la pile.
Il s'agit d'un type mutable et l'effet des fonctions push
et pop
est précisément de modifier cette valeur.
Une façon simple d'implémenter une pile en Caml est de définir le type 'a stack
par une référence sur une liste.
type 'a stack = 'a list ref ;;
exception Stack_empty ;;
(** Retourne une nouvelle pile vide *)
let create () : 'a stack = ref []
(** Indique si la pile s est vide *)
let is_empty (s : 'a stack) : bool =
!s = []
;;
(** Retourne la valeur du sommet de la pile s *)
let peek (s : 'a stack) : 'a =
match !s with
| [] -> raise Stack_empty
| x :: xq -> x
;;
(** Ajoute la valeur x sur le sommet de la pile s *)
let push (s : 'a stack) (x : 'a) : unit =
s := x :: !s
;;
(** Supprime et retourne la valeur du sommet de la pile s *)
let pop (s : 'a stack) : 'a =
match !s with
| [] -> raise Stack_empty
| x :: xq -> s := xq ; x
;;
let my_stack = create () ;;
for i = 0 to 5 do
push my_stack (i * i)
done ;;
while not (is_empty my_stack) do
print_int (pop my_stack) ;
print_newline ()
done ;;
Rien n'interdit malheureusement le programmeur d'accéder directement à la valeur my_stack
:
my_stack := [7; 8] ;;
pop my_stack ;;
my_stack ;;
Le postulat de base de la programmation structurée est que le programmeur ne manipule jamais directement la valeur de type 'a stack
. Il utilise systématiquement les primitives d'accès décrites dans la structure abstraite.
Ceci contribue ainsi à produire du code modulaire où il devient possible de modifier certaines parties sans en perturber d'autres.
On peut ainsi imaginer de modifier l'implémentation de la pile en remplaçant la référence de liste par un tableau.
Si le programmeur qui utilise la structure a respecté l'interface, alors son code fonctionnera tout aussi bien.
Le langage Caml comporte une syntaxe pour encapsuler proprement les structures de données. Il n'est pas nécessaire que vous connaissiez cette syntaxe, mais elle peut contribuer à vous faire bien comprendre cette notion essentielle de structures de données.
Ci-dessous, on a simplement encadré le code Caml de la structure de pile entre un
module Stack = struct
et un
end
.
Nous avons également suivi la convention habituelle qui consiste à nommer 'a t
plutôt que 'a stack
le type principal de la structure.
module Stack = struct
type 'a t = 'a list ref
exception Stack_empty
(** Retourne une nouvelle pile vide *)
let create () : 'a t = ref []
(** Indique si la pile s est vide *)
let is_empty (s : 'a t) : bool =
!s = []
(** Retourne la valeur du sommet de la pile s *)
let peek (s : 'a t) : 'a =
match !s with
| [] -> raise Stack_empty
| x :: xq -> x
(** Ajoute la valeur x sur le sommet de la pile s *)
let push (s : 'a t) (x : 'a) : unit =
s := x :: !s
(** Supprime et retourne la valeur du sommet de la pile s *)
let pop (s : 'a t) : 'a =
match !s with
| [] -> raise Stack_empty
| x :: xq -> s := xq ; x
end
La structure s'utilise alors de cette façon :
let my_stack = Stack.create () ;;
for i = 0 to 5 do
Stack.push my_stack (i * i)
done ;;
while not (Stack.is_empty my_stack) do
print_int (Stack.pop my_stack) ;
print_newline ()
done ;;
Caml dispose également d'une syntaxe pour définir les structures abstraites :
module type STACK = sig
type 'a t
exception Stack_empty
val create : unit -> 'a t
val is_empty : 'a t -> bool
val peek : 'a t -> 'a
val push : 'a t -> 'a -> unit
val pop : 'a t -> 'a
end
La création d'une structure concrète qui implémente la structure abstraite STACK
peut alors s'écrire de cette façon :
module Stack : STACK = struct
type 'a t = 'a list ref
exception Stack_empty
(** Retourne une nouvelle pile vide *)
let create () : 'a t = ref []
(** Indique si la pile s est vide *)
let is_empty (s : 'a t) : bool =
!s = []
(** Retourne la valeur du sommet de la pile s *)
let peek (s : 'a t) : 'a =
match !s with
| [] -> raise Stack_empty
| x :: xq -> x
(** Ajoute la valeur x sur le sommet de la pile s *)
let push (s : 'a t) (x : 'a) : unit =
s := x :: !s
(** Supprime et retourne la valeur du sommet de la pile s *)
let pop (s : 'a t) : 'a =
match !s with
| [] -> raise Stack_empty
| x :: xq -> s := xq ; x
end
let my_stack = Stack.create () ;;
for i = 0 to 5 do
Stack.push my_stack (i * i)
done ;;
Le programmeur n'a maintenant plus aucun moyen d'accéder directement à la valeur my_stack
:
my_stack
my_stack := [7; 8]
Les expressions arithmétiques sont habituellement écrites en notation infixe, c'est-à-dire en plaçant les opérateurs binaires entre leurs deux arguments. Ceci nécessite des parenthèses pour préciser la hiérarchie des calculs. La formule $\frac{1+2\sqrt{3}}{4}$ s'écrit ainsi :
(1 + ( 2 * ( sqrt 3 ) ) ) / 4
.
Une autre écriture possible est la notation postfixée, où les deux arguments sont placés avant l'opérateur. Cette même formule s'écrit alors :
1 2 3 sqrt * + 4 /
Nous allons voir comment, à l'aide d'une pile, évaluer une expression postfixée.
La première étape consiste à découper la chaîne de caractères en ses éléments de base appelés tokens.
On définit pour cela le type token
:
type token =
| Num of float
| Binary_op of string
| Unary_op of string
;;
Il faut ensuite associer à chaque token de type opération, la fonction Caml qui lui correspond. Ceci est fait à l'aide d'une liste de couples :
let unary_ops = [
("sqrt", sqrt)
] ;;
let binary_ops = [
("+", ( +. ) ) ;
("-", ( -. ) ) ;
("*", ( *. ) ) ;
("/", ( /. ) )
] ;;
L'analyse lexicale de l'expression consiste à produire la liste des tokens à partir du texte de l'expression.
Ceci est réalisé par la fonction lexer
ci-dessous.
Il n'est pas nécessaire pour la suite de comprendre ce code.
exception Syntax_error ;;
#load "str.cma";;
let lexer (expr : string) : token list =
List.map
(fun t ->
try Num (float_of_string t)
with Failure _ ->
if List.mem_assoc t unary_ops then Unary_op t
else if List.mem_assoc t binary_ops then Binary_op t
else raise Syntax_error
)
@@ Str.split (Str.regexp "[ ]+") expr
;;
lexer "1 2 3 sqrt * + 4 /"
Voici le principe de l'algorithme :
Lire un token
Si le token est un nombre, ajouter le nombre dans la pile
sinon si le token est une opération unaire
Retirer un nombre de la pile
Effectuer l'opération sur ce nombre
Ajouter le résultat dans la pile
sinon si le token est une opération binaire
Retirer deux nombres de la pile
Effectuer l'opération sur ces deux nombres
Ajouter le résultat dans la pile
S'il reste des tokens à lire, recommencer au début
sinon la valeur de l'expression est l'unique nombre
présent dans la pile.
let eval (expr : string) : float =
let s = Stack.create () in
let rec eval_rec ts =
match ts with
| [] ->
let value = Stack.pop s in
if Stack.is_empty s then value
else raise Syntax_error
| t :: tq ->
begin match t with
| Num x -> Stack.push s x
| Unary_op op ->
let x = Stack.pop s in
let f = List.assoc op unary_ops in
Stack.push s (f x)
| Binary_op op ->
let x2 = Stack.pop s in
let x1 = Stack.pop s in
let f = List.assoc op binary_ops in
Stack.push s (f x1 x2)
end ;
eval_rec tq
in
try eval_rec (lexer expr)
with Stack.Stack_empty -> raise Syntax_error
;;
eval "1 2 3 sqrt * + 4 /"
Une structure de file est une structure FIFO (First In Firts Out). Le modèle est celui de la file d'attente. L'élément que l'on retire de la file est toujours premier à y être entré.
La structure abstraite d'une file est donnée par le code Caml suivant :
module type QUEUE = sig
type 'a t
exception Queue_empty (* Action invalide sur une file vide *)
exception Queue_overflow (* Dépassement de capacité de file *)
val create : unit -> 'a t
(** Retourne une nouvelle file vide *)
val is_empty : 'a t -> bool
(** Indique si la file est vide *)
val peek : 'a t -> 'a
(** Retourne le plus ancien élément de la file
Lève l'exception Queue_empty si la file est vide *)
val enqueue : 'a t -> 'a -> unit
(** Ajoute un nouvel élément dans la file
Lève l'exception Queue_overflow si la file est pleine *)
val dequeue : 'a t -> 'a
(** Supprime et retourne le plus ancien élément de la file
Lève l'exception Queue_empty si la file est vide *)
end
On verra comment implémenter la structure de file à l'aide d'un tableau
Les structures de données que nous avons construites jusqu'ici sont toutes des structures impératives. Le type de base est un type mutable qui est modifié par effet de bord par les primitives d'accès à la structure. Pour écrire du code fonctionnel pur il faut pouvoir disposer de structures de données persistantes, c'est-à-dire immuables. Le rôle des primitives d'accès est alors de calculer une nouvelle structure à partir de la structure passée en argument. Cette dernière n'est pas modifiée par la fonction. Illustrons ceci en construisant une structure persistante de file. Sa définition abstraite est donnée par le code Caml ci-dessous :
module type QUEUE = sig
type 'a t
exception Queue_empty
val empty : 'a t
(** File vide *)
val is_empty : 'a t -> bool
(** Indique si la file est vide *)
val enqueue : 'a -> 'a t -> 'a t
(** Ajoute un nouvel élément dans la liste *)
val dequeue : 'a t -> 'a * 'a t
(** Retire le plus ancien élément de la liste *)
end
Insistons bien, les fonctions enqueue
et dequeue
retournent une nouvelle file qui diffère de celle passée en argument par l'ajout, respectivement le retrait, d'un élément. La file passée en argument n'est pas modifiée.
Une file persistante peut être implémentée à l'aide de deux listes rear
et front
. La primitive enqueue
ajoute les éléments dans la liste rear
. Pour retirer un élément de la file, la primitive dequeue
les prend dans la liste front
. Si la liste front
est vide, elle renverse au préalable la liste rear
dans la liste front
.
module Queue : QUEUE = struct
type 'a t = {
rear : 'a list ;
front : 'a list
}
exception Queue_empty
let empty : 'a t = {rear = [] ; front = []}
let is_empty (q : 'a t) : bool =
q = {rear = [] ; front = []}
let enqueue (x : 'a) (q : 'a t) : 'a t =
{rear = x :: q.rear ; front = q.front}
let dequeue (q : 'a t) : 'a * 'a t =
match q with
| {rear = [] ; front = []} -> raise Queue_empty
| {rear = xs ; front = []} ->
let xr = List.rev xs in List.hd xr, {rear = [] ; front = List.tl xr}
| {rear = xs ; front = x :: xq} ->
x, {rear = xs ; front = xq}
end
let rec fill (q : int Queue.t) (n : int) =
if n = 0 then q
else fill (Queue.enqueue n q) (n - 1)
;;
fill Queue.empty 5 ;;
let rec fill (q : int Queue.t) (n : int) =
if n = 0 then q
else fill (Queue.enqueue n q) (n - 1)
;;
let rec deq (q : int Queue.t) =
if not (Queue.is_empty q) then
let x, qq = Queue.dequeue q in
print_int x ;
print_newline () ;
deq qq
in
deq (fill Queue.empty 5)
Lorsque nous avons étudié les arbres binaires nous avons écrit des fonctions pour parcourir les noeuds et les feuilles d'un arbre. Nous avons ainsi présenté les parcours préfixe, infixe et postfixe. Ces trois types de parcours étaient tous des parcours en profondeur. Les fonctions parcourent récursivement tous les noeuds de la branche de gauche avant de s'intéresser à la branche de droite. Nous présentons maintenant un type très différent de parcours, appelé parcours en largeur. L'idée est de parcourir tous les noeuds de profondeur $n$ avant de passer aux noeuds de profondeur $n+1$. Ainsi par exemple, les noeuds de l'arbre ci-dessous seront parcourus dans l'ordre croissant de leurs étiquettes.
type tree =
| Nil
| Node of int * tree * tree
;;
let t1 =
Node (
1,
Node (
2,
Node (
4,
Node (7, Nil, Nil),
Node (8, Nil, Nil)
),
Node (5, Nil, Nil)
),
Node (
3,
Nil,
Node (
6,
Node (9, Nil, Nil),
Node (10, Nil, Nil)
)
)
)
;;
Pour rappel, voici une fonction de parcours en profondeur selon l'ordre préfixe :
let rec parcours_en_profondeur (t : tree) : unit =
match t with
| Nil -> ()
| Node (x, tg, td) ->
print_int x ;
print_char ' ' ;
parcours_en_profondeur tg ;
parcours_en_profondeur td
;;
parcours_en_profondeur t1 ;;
Le parcours en largeur utilise une file. On place dans la file la racine de l'arbre puis, tant qu'il reste des éléments dans la file, on effectue les actions suivantes :
Retirer un noeud de la file
Imprimer ce noeud
Ajouter le fils gauche dans la file
Ajouter le fils droit dans la file
open Queue
let parcours_en_largeur (t : tree) : unit =
let rec parcours q =
if not (is_empty q) then
let t, qq = dequeue q in
match t with
| Nil -> parcours qq
| Node (x, left, right) ->
print_int x ;
print_char ' ' ;
qq |> enqueue left
|> enqueue right
|> parcours
in
parcours (enqueue t empty)
;;
parcours_en_largeur t1 ;;
open Queue
let parcours_en_largeur (t : tree) : unit =
let rec parcours q =
if not (is_empty q) then begin
let t, qq = dequeue q in
match t with
| Nil -> parcours qq
| Node (x, left, right) ->
print_int x ;
print_char ' ' ;
parcours (enqueue right (enqueue left qq))
end
in
parcours (enqueue t empty)
;;
parcours_en_largeur t1 ;;
L'instruction open Queue
permet de désigner les valeurs du module Queue
sans avoir à les faire précéder du préfixe Queue
.
C'est l'équivalent du from module import *
de Python.
Pour les plus avancés uniquement, voici une seconde version qui utilise le mécanisme d'exception au lieu de tester si la file est vide à chaque appel récursif et qui utilise l'opérateur infixe d'application inverse de fonction.
open Queue
let parcours_en_largeur (t : tree) : unit =
let rec parcours q =
try
let t, qq = dequeue q in
match t with
| Nil -> parcours qq
| Node (x, left, right) ->
print_int x ;
print_char ' ' ;
qq |> enqueue left
|> enqueue right
|> parcours
with Queue_empty -> ()
in
parcours (enqueue t empty)
;;
parcours_en_largeur t1 ;;