Structures de données purement fonctionnelles

Présentation du problème

Lorsque l'on souhaite coder une structure de données dans un langage impératif comme C, Ada, Pascal ou Perl, il est très facile de trouver des livres sur le sujet. En revanche, si l'on souhaite utiliser le paradigme fonctionnel, que ce soit Lisp, Haskell ou OCaml, le choix est nettement plus restreint.

Un programmeur peut choisir le paradigme de son langage, pourvu que ce soit impératif. - Chris Okasaki, pastiche d'une citation de Ford, Purely functional data structures, 1996

Ainsi, Chris Okasaki a voulu explorer à travers sa thèse (et son livre la développant) diverses structures de données adaptées au paradigme fonctionnel.

Mais avant d'étudier les solutions proposées, il est nécessaire de définir quelques contraintes et termes.

Problèmes liés au paradigme fonctionnel

Différence entre structure éphémère et persistante illustrée par une liste chaînée dont on supprime le dernier élément.

Le paradigme fonctionnel est principalement basé sur l'évaluation de fonctions et d'expressions mathématiques, et tout ce qui ne peut être représenté ainsi n'est pas admis.

De ce fait naît le premier obstacle à la création de structures de données purement fonctionnelles : Le changement d'état étant banni, on ne peut pas réaliser d'assignation de variable.
Là où les langages impératifs font fréquemment usage de l'assignation de variable et de la modification de valeurs, il faut trouver d'autres solutions en fonctionnel pour contourner ce problème. Okasaki compare le lien entre l'assignation et le programmeur à celui entre les couteaux et un chef cuisinier. Dans les deux cas, un mauvais usage peut être dangereux et destructeur, mais extrêmement efficace avec un usage intelligent.

Une deuxième difficulté liée à l'absence d'assignation provient du fait que l'on attende davantage une persistance d'une structure de données fonctionnelle. En effet, là où il est admis que l'actualisation d'une structure impérative détruit l'ancienne version pour ne garder que la nouvelle (ce genre de structure de données est dit "éphémère"), on s'attend que l'actualisation d'une structure fonctionnelle donne l'accès aux deux versions (d'où la notion de structure "persistante"). Il est possible d'avoir des structures persistantes en impératif, mais on associera ici la notion d'éphémérité au paradigme impératif tandis que la persistance sera liée au paradigme fonctionnel.

Enfin, un troisième problème lié au paradigme fonctionnel relève du temps d'exécution, le fonctionnel étant généralement considéré comme étant moins efficace que l'impératif. Ainsi, il est nécessaire de trouver des structures de données qui soient aussi efficaces que celles utilisées en impératif.

Évaluation stricte et évaluation paresseuse

On appelle évaluation stricte une technique d'implémentation d'un programme récursif où les arguments sont évalués avant le corps de la fonction. L'évaluation est dite paresseuse quand les arguments sont évalués lors du premier appel par la fonction avant d'être mis en cache pour un autre usage ultérieur.

Chaque type d'évaluation a ses avantages et inconvénients. Une évaluation stricte permettra de gérer le cas "Pire scénario" tandis qu'une évaluation paresseuse sera plus à l'aise avec les structures dites amorties.

Un avantage indéniable qu'a cependant l'évaluation stricte sur l'évaluation paresseuse est que l'on peut calculer le temps d'évaluation plus facilement (notion de comparaison asymptotique, notamment du grand O de Landau).

Vocabulaire

Avant de commencer à étudier les solutions proposées par Okasaki, il est nécessaire de poser quelques termes de vocabulaire.

Abstraction

Un type de données abstrait, autrement dit un type et un ensemble de fonctions agissant sur ce type.

Exemple : Le premier bloc de code de liste chaînée (voir ci-dessous) est une abstraction de cette structure, avec le type élément et les divers constructeurs, destructeurs et méthodes sur cette structure.

Implémentation

Une réalisation concrète d'une abstraction. Il est important de noter qu'une implémentation ne correspond pas nécessairement à du code, un modèle concret suffit.

Exemple : Posons qu'un élément est soit null, soit le couplet liant un entier et un pointeur vers l'élément suivant. Ceci correspond à l'implémentation de l'abstraction de la structure liste chaînée.

Objet / Version

Une instance d'un type de données, telle une variante spécifique de liste ou d'arbre.

Exemple : Soit une liste chaînée d'entiers. Il s'agit d'une version d'une liste chaînée.

Identité persistante

Une identité unique et invariante malgré les changements. Par exemple, "la pile" en parlant de toutes ses différentes versions correspond à son identité persistante.

Maintenant que nous avons posé des bases solides, nous pouvons commencer à étudier les diverses structures de données proposées par Okasaki. Le langage utilisé est OCaml.

Solutions proposées

En se basant sur la présentation, on peut faire remarquer deux points :

• Afin d'avoir des structures persistantes, il est nécessaire de travailler sur une copie de l'argument plutôt que l'argument lui-même
• À l'exception de la liste chaînée, toutes les structures évoquées ci-après ne fonctionnent qu'avec des types ordonnés.

module type ORDERED = sig
  type t
  val eq: t -> t -> bool
  val lt: t -> t -> bool
  val leq: t -> t -> bool
end;;

Code permettant d'implémenter un type polymorphe ordonné. On admet que ce type est défini pour toutes les structures ci-dessous.

Liste chaînée

Cette structure basique sert d'introduction à la persistance, ce qui nous permet de présenter les différences d'implémentation de cette structure dans un paradigme impératif comparé à un paradigme fonctionnel.

Abstraction de la structure liste chaînée

module type LIST = sig
  type 'a t

  (* Constructeurs *)
  val nil: 'a t
  val cons: 'a -> 'a t -> 'a t
  val is_empty: 'a t -> bool
  
  (* Destructeurs *)
  val head: 'a t -> 'a
  val tail: 'a t -> 'a t

  (* Méthodes *)
  val append: 'a t -> 'a t -> 'a t
  val update: 'a t -> int -> 'a -> 'a t
  val suffixes: 'a t -> 'a t t
end;;

Ici, nous allons observer les méthodes, à savoir append, update et suffixes.

• append - Concaténation de deux listes

Soient xs et ys deux listes et zs la concaténation de xs et ys.

En impératif, une structure de données efficace basée sur la liste chaînée peut comporter deux pointeurs globaux, un sur le premier élément et un sur le dernier. Ainsi, pour concaténer xs et ys, il suffit de modifier le dernier élément de xs pour qu'il pointe vers le premier de ys. L'avantage, c'est que le temps d'exécution est d'ordre O(1), donc constant. Cependant, en obtenant zs, on garde ys mais on perd xs.

En fonctionnel, zs est une reconstruction de xs à laquelle on accole ys. Si on note n la longueur de xs, la fonction a un temps d'exécution d'ordre O(n), mais on garde toujours xs et ys.

let rec append = fun xs ys ->
  if is_empty xs
  then ys
  else cons (head xs) (append (tail xs) ys)

L'idée est de "déconstruire" xs afin de se retrouver avec une liste vide. Au fur et à mesure, on reconstruit xs élément par élément avant d'y accoler ys lorsque cet objectif est atteint.

• update - Mise à jour d'un nœud

On cherche à changer la valeur x au rang i dans xs par la valeur y.

En impératif, on cherche le nœud concerné et on change la valeur. Le temps d'exécution est d'ordre O(n) dans le pire des cas, mais le xs original est perdu.

En fonctionnel, la méthode de recherche est la même. Le temps d'exécution est toujours d'ordre O(n) dans le pire des cas, mais on récupère ys, reconstruction altérée de xs tout en conservant l'original.

let rec update = fun xs i y ->
  if is_empty xs
  then raise Index_out_of_bounds (* Si la liste est vide, il n'y a rien à remplacer ! *)
  else if i = 0
       then cons y (tail xs)
       else cons (head xs) (update (tail xs) (i - 1) y)

Comme pour append, on déconstruit puis reconstruit xs, sauf que l'on a un compteur qui est décrémenté de 1 par élément reconstruit. S'il atteint 0, la valeur de l'élément actuel est replacé par y. Si on reconstruit xs dans son intégralité (donc qu'il ne reste que la liste vide) avant que le compteur ait atteint 0, on lève une exception.

• suffixes - Afficher tous les suffixes d'une liste par ordre décroissant de taille

Par exemple, la liste [1, 2, 3, 4] doit retourner [[1, 2, 3, 4], [2, 3, 4], [3, 4], [4], []].

Le temps d'exécution de cette fonction est d'ordre O(n).

let rec suffixes = fun xs ->
  if is_empty xs
  then nil
  else cons xs (suffixes (tail xs))

Ici, on utilise le fait que la fonction tail renvoie toute la liste sauf la tête. Ainsi, on peut accoler tous les suffixes un par un, jusqu'à s'arrêter avec la liste vide.

Arbre de recherche binaire

Il est possible d'utiliser des méthodes de recherche plus complexes lorsque l'on utilise une structure où un élément pointe vers plus qu'un seul autre élément. Prenons par exemple les arbres de recherche binaires.

Un arbre de recherche binaire est un arbre dont les valeurs stockées dans chaque élément sont rangées par ordre symétrique, c'est-à-dire que pour un nœud donné, sa valeur est supérieure à toutes les valeurs stockées dans le sous-arbre de gauche et inférieure à celles dans le sous-arbre de droite.

Dans le code ci-dessous, BalancedTree est un foncteur, autrement dit une fonction qui prendre comme paramètre un module O de type ORDERED.

module BalancedTree(O: ORDERED)= struct
  type elem = O.t

  type tree = E | T of (tree * elem * tree)

  let rec member...

  let rec insert...
end;;

Penchons-nous sur les méthodes member et insert.

• member - Vérifie si une valeur est présente dans l'arbre

En reprenant notre type ordonné, on remarque que l'on ne dispose que de 3 fonctions de test, à savoir l'égalité (O.eq), l'infériorité stricte (O.lt) et l'infériorité (O.leq).

Pour construire cette fonction, on serait tenté d'écrire :

let rec member = fun xs x ->
  match xs with
  | E -> false
  | T(e1, y, e2) -> if (O.lt x y)
                    then member e1 x
                    else if (O.lt y x)
                         then member e2 x
                         else true

On regarde si la valeur du nœud est strictement plus grande que celle recherchée. Si oui, on continue à chercher à gauche. Sinon, on regarde si la valeur du nœud est strictement inférieure à celle recherchée. Si c'est le cas, on poursuit la recherche à gauche. Sinon, il y a égalité et la valeur est bien membre de l'arbre. Si on atteint une feuille sans avoir eu d'égalité, alors la valeur n'appartient pas à l'arbre.

En effet, le pire scénario, ici la branche qui tourne toujours à droite jusqu'au bout de l'arbre, exigerait 2n comparaisons (avec n la profondeur de l'arbre) pour retourner un résultat, étant donné qu'il effectue deux comparaisons par nœud.

let rec member =
  let rec member_aux = fun xs aux x ->
    match xs with
    | E -> O.eq aux x
    | T(e1, y, e2) -> if (O.lt x y)
                      then member_aux e1 aux x
                      else member_aux e2 y x
  in fun xs x ->
  match xs with
  | E -> false
  | T(e1, y, e2) -> if(O.lt x y)
                    then member e1 x
                    else member_aux e2 y x

Ici, on fait appel à une fonction auxiliaire itérative stockant une valeur intermédiaire. Cette fonction fait appel au fait que si x n'est pas strictement inférieur à y, alors x est supérieur ou égal à y. Ainsi, on parcourt la branche correspondante comme précédemment, mais on garde ce candidat potentiel jusqu'à ce que l'on atteigne une feuille. Ainsi, on ne réalise dans le pire des cas que n + 1 comparaisons, une par niveau de profondeur et une supplémentaire pour vérifier l'égalité une fois arrivé aux feuilles.

• insert - Insère une valeur dans l'arbre

Pour l'insertion, on procède similairement pour atteindre la feuille correspondante.

let rec insert = fun xs x ->
  match xs with
  | E -> T(E, x, E)
  | T(e1, y, e2) as s -> if (O.lt x y)
                         then T((insert e1 x), y, e2)
                         else if (O.lt y x)
                              then T(e1, y, (insert e2 x))
                              else s

Comme précédemment, on regarde s'il faut continuer à gauche ou à droite en reconstruisant une copie de l'arbre au fur et à mesure. Cependant, si la valeur à ajouter est déjà présente dans l'arbre, on recopie également ce nœud, ce qui fait que la branche de recherche est testée de la racine à la feuille sans aucun changement à appliquer. En levant une exception si l'on trouve la valeur à ajouter dans l'arbre, on optimise le temps d'exécution en ne faisant pas de copie inutile.

exception Already_there

let rec insert = fun xs x ->
  try begin
    match xs with
    | E -> T(E, x, E)
    | T(e1, y, e2) -> if(O.lt x y)
                      then T((insert e1 x), y, e2)
                      else if (O.lt y x)
                           then T(e1, y, (insert e2 x))
                           else raise Already_there
  end with Already_there -> xs

Ainsi, on s'arrête si l'on trouve la valeur à ajouter et l'on retourne une copie de l'arbre tel quel. Et comme pour member, il est possible d'optimiser le nombre de comparaisons, ce qui donne au final une fonction qui ressemble à ceci :

let rec insert =
  let rec insert_aux = fun xs aux x ->
    match xs with
    | E -> if (O.eq aux x)
           then raise Already_there
           else T(E, x, E)
    | T(e1, y, e2) -> if (O.lt x y)
                      then T((insert_aux e1 aux x), y, e2)
                      else T(e1, y, (insert_aux e2 y x))
  in fun xs x ->
    try begin
      match xs with
      | E -> T(E, x, E)
      | T(e1, y, e2) -> if (O.lt x y)
                        then T((insert e1 x), y, e2)
                        else T(e1, y, (insert_aux e2 y x))
    end with Already_there -> xs

On se retrouve donc avec une fonction d'insertion qui ne copie pas inutilement et qui ne réalise pas plus que n + 1 comparaisons.

Tas gaucher

Exemple de tas gaucher et illustration de la notion de rang.

Un tas est une version d'arbre particulière. En effet, elle se caractérise par le fait que la valeur de chaque nœud ne peut être plus grand que n'importe laquelle de ses enfants. Cette caractéristique fait que l'élément le plus petit se trouve toujours à la racine.

Un tas est dit gaucher si le rang de n'importe quel enfant de gauche est supérieur ou égal à celui de l'enfant de droit qui lui est associé. On appelle rang d'un nœud la longueur de sa colonne vertébrale droite, c'est-à-dire le chemin le plus à droite qui va de ce nœud à une feuille. Une conséquence simple de cette propriété est que la colonne vertébrale droite d'un nœud constitue le chemin le plus court de ce nœud à une feuille.

Soit r le rang de la racine d'un tas gaucher de taille n. On peut en déduire que chaque nœud de profondeur inférieure ou égale à r-1 a exactement deux enfants, car sinon r aurait une valeur plus faible ou la propriété gauchère ne serait pas respectée. Ainsi, on peut affirmer que la taille d'un tas est donc d'au moins 2^r - 1. De ce fait, on peut en déduire que le rang de la racine vaut au plus log(n + 1). Par conséquent, la colonne vertébrale droite d'un tas gaucher de taille n comporte au plus ⌊log(n + 1)⌋ éléments.

Code de la structure tas gaucher

module LeftistHeap (O: ORDERED) = struct
  type elem = O.t

  type heap = Nil | Cons of (int * heap * elem * heap)

  let rank = fun h ->
    match h with
    | Nil -> 0
    | Cons(r, _, _, _) -> r

  let makeH...

  let merge...

  let insert...

  exception EmptyHeap

  let findMin...

  let deleteMin...
end;;

Ici, nous allons étudier les fonctions merge, insert, findMin et deleteMin.

• merge - Fusionne deux tas

Afin de simplifier l'opération, on remarque que la colonne vertébrale droite d'un tas gaucher est ordonnée. On en déduit que le concept clé est de fusionner les colonnes vertébrales des deux tas comme on fusionnerait deux listes triées avant d'échanger les enfants le long de la branche afin de restaurer la propriété gauchère.

Comme il a été démontré précédemment que la longueur de la colonne vertébrale est au plus logarithmique, on peut en déduire que merge a un temps d'exécution d'ordre O(log n).

let makeH = fun v a b ->
  if rank a >= rank b
  then Cons(rank b + 1, a, v, b)
  else Cons(rank a + 1, b, v, a)

let rec merge = fun x y ->
  match x, y with
  | Nil, _ -> y
  | _, Nil -> x
  | Cons(_, e11, v1, e12), Cons(_, e21, v2, e22) -> if (O.leq v1 v2)
                                                    then makeH v1 e11 (merge e12 y)
                                                    else makeH v2 e21 (merge x e22)

Ici, on fait appel à une fonction intermédiaire : makeH.

Cette fonction compare le rang des deux tas et échange les enfants si besoin afin de respecter la propriété gauchère.

Ensuite, concernant merge en elle-même, on compare les valeurs des deux racines et on fait appel à makeH pour combiner et potentiellement échanger les enfants.

• insert - Insère une valeur dans l'arbre

Une fois merge défini, il suffit d'établir que l'on veut fusionner le tas avec un tas d'une seule valeur. Et puisque le temps d'exécution de merge est d'ordre O(log n), il en va de même pour insert.

let insert = fun v h -> (merge (Cons(1, Nil, v, Nil)) h)

• findMin - Récupère le minimum

Comme le minimum est par définition à la racine, le temps d'exécution de findMin est d'ordre O(1), donc constant.

let findMin = fun h ->
  match h with
  | Nil -> raise EmptyHeap
  | Cons(_, _, v, _) -> v

• deleteMin - Supprime le minimum

Similairement, le minimum étant à la racine, on peut établir que le supprimer revient à fusionner ses enfants. De plus, merge ayant un temps d'exécution d'ordre O(log n), celui de deleteMin est le même.

let deleteMin = fun h ->
  match h with
  | Nil -> raise EmptyHeap
  | Cons(_, a, _, b) -> merge a b

Tas binomial

Représentation des arbres binaires de rangs 0 à 3

Les tas binomiaux sont des tas composés d'un type plus primitif appelé arbre binomial. Les arbres binomiaux sont défini inductivement comme suit :

• Un arbre binomial de rang 0 est un singleton de nœud ;
• Un arbre binomial de rang r est formé en liant deux arbres binomiaux de rang r-1 tel qu'un des arbres devient l'enfant le plus à gauche de l'autre.

De cette définition, on comprend qu'un arbre binomial de rang r contient exactement 2^r nœuds.

Il existe une deuxième définition équivalente des arbres binomiaux :

• Un arbre binomial de rang r est un nœud ayant r enfants t₁ à t_r où chaque enfant t_i est un arbre binomial de rang r - i.

Dans le code ci-dessous, on représente un nœud dans un arbre binomial comme un élément avec une liste de ses enfants. Par commodité, on note aussi le rang de chaque nœud.

De plus, un tas binomial étant une liste d'arbres binomiaux ne pouvant comporter qu'un seul arbre d'un rang donné et un arbre binomial de rang r comportant 2^r éléments, on constate alors que les arbres d'un tas binomial de taille n correspondent à la représentation binaire de n.

Par exemple, la représentation binaire de 13 est 1101, donc un tas binomial de taille 13 contient un arbre de rang 0, un de rang 2 et un de rang 3 (de taille respective 1, 4 et 8). De plus, comme la représentation binaire de n contient au plus ⌊log(n + 1)⌋ bits à 1, un tas binomial de taille n contient au plus ⌊log(n + 1)⌋ arbres.

module BinomialHeap (O: ORDERED) = struct
  type elem = O.t

  type tree = Node of (int * elem * tree list)
  type heap = tree list

  exception EmptyHeap

  let rank (Node(r, _, _)) = r
  let root (Node(_, x, _)) = x

  let link = fun (Node(r, x1, c1) as t1) (Node(_, x2, c2) as t2) ->
    if (O.leq x1 x2)
    then Node(r + 1, x1, t2 :: c1)
    else Node(r + 1, x2, t1 :: c2)

  let rec insTree...

  let insert = fun x ts -> insTree (Node(0, x, [])) ts

  let rec merge...

  let rec removeMinTree...

  let findMin = fun ts -> let (t, _) = removeMinTree ts in root t

  let deleteMin = fun ts -> let (Node(_, x, ts1), ts2) = removeMinTree ts in merge (rev ts1) ts2
end;;

Les fonctions que nous allons étudier ici sont insTree, merge et removeMinTree.

• insTree -

Sources et annexes

Sources

• Thèse d'Okasaki

• Purely functional data structures, Chris Okasaki

• Programmation fonctionnelle (Wikipédia FR)

• Tas gaucher (Wikipédia EN)

Annexes