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.

Sources et annexes

Sources

• Thèse d'Okasaki

• Purely functional data structures, Chris Okasaki

• Programmation fonctionnelle (Wikipédia)

Annexes