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 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 (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.

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.

Objet / Version

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

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 a été 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 - zs = xs :: ys

En impératif, une liste chaînée comporte généralement deux pointeurs, 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 ->
  match xs with
  | [] -> ys
  | x :: xs' -> x :: (append xs' ys);;

Sources et annexes

Sources

• Thèse d'Okasaki

• Purely functional data structures, Chris Okasaki

• Programmation fonctionnelle (Wikipédia)

Annexes