On imagine une collection {\mathcal{V}} de valeurs appartenant à certain ensemble {\mathcal{E}(}donc {\mathcal{V}} est un sous-ensemble de {\mathcal{E}).}
Pour faciliter les recherches dans la collection {\mathcal{V},} on associe à chaque élément de {\mathcal{E}} une « clef ».
Les clefs sont des éléments d’un ensemble {\mathcal{K}(}qu’on peut appeler l’univers des clefs).
On suppose que deux éléments différents de {\mathcal{E}} ont des clefs différentes.
Autrement dit, on dispose d’une application injective {k:\mathcal{E}\to \mathcal{K}(}on écrit {k} pour « key »).
Plutôt que la collection {\mathcal{V},} on considérera plutôt l’ensemble {\mathcal{D}=\left\{(k(v),v),v\in \mathcal{V}\right\}.}
L’ensemble {\mathcal{D},} dont les éléments sont les couples (clef, valeur), est appelé un « dictionnaire » (ou une « table d’association »), par analogie avec un vrai dictionnaire, où les clefs sont les mots de la langue et les valeurs les définitions associées.
6.1.1 Une première idée (peu réaliste)
À une bijection près, on considère ici que l’univers des clefs est {\mathcal{K}=[\![ 0,N-1]\!] ,} où {N\in \mathbb{N}^{\star}.}
Si {N} n’est pas trop grand, on peut imaginer le dictionnaire {\mathcal{D}} comme un tableau indicé par les clefs {k\in [\![ 0,N-1]\!] .}
Si on nomme tab ce tableau, le contenu tab.(k) de la case d’indice {k} serait alors :
- la valeur {v} dont la clef est {k} si cette valeur appartient effectivement à la collection ;
- vide si cette valeur {v} n’appartient pas à la collection.
Supposons que ce dictionnaire soit de type 'a array. Il faut alors trouver le moyen d’indiquer qu’il n’y a rien (ou qu’au contraire il y a quelque chose de type 'a) dans une case donnée du tableau.
On pourrait imaginer de choisir une valeur dans le type 'a qui serait synonyme de rien (par exemple la chaîne vide pour le type string, ou 0 pour le type int) mais ce n’est pas idéal.
Le langage OCaml propose le type 'a option (qu’on pourrait comprendre comme le type des valeurs optionnelles de type 'a ) et dont la définition est la suivante :
|
1 |
type 'a option = None | Some of 'a;; |
Une valeur du type 'a option est donc soit None (c’est-à-dire rien), soit est un exemplaire (Some) d’un objet de type 'a.
Voici un premier exemple de création et de modification d’un tableau de type 'a option array :
|
1 2 3 4 5 6 7 8 |
let create n = Array.make n None;; (* fonction initialisant un tableau de n cases "vides" *) val create : int -> 'a option array = <fun> let tab = create 10;; (* on crée un tel tableau, de longueur 10 *) val tab : '_a option array = [|None; None; None; None; None; None; None; None; None; None|] tab.(6) <- Some 27;; (* on place une valeur du type int option en case 6 *) - : unit = () tab;; (* maintenant le tableau est de type int option array, de cases toutes "vides" sauf une *) - : int option array = [|None; None; None; None; None; None; Some 27; None; None; None|] |
L’idée évoquée ici est cependant irréaliste, car l’univers {\mathcal{K}} des clefs possibles a en général une taille {N} considérable, et il est illusoire de vouloir maintenir un dictionnaire par une structure de tableau indicé par ces clefs (les valeurs associées étant vides le plus souvent).
- avoir une souscription active sur mathprepa
- et être connecté au site
- revenir à la page d'accueil
- ou tester la page d'extraits libres