Les structures de données permettent d'organiser des collections de valeurs, de les manipuler, de retrouver des informations facilement (un appel de fonction) et rapidement (par exemple en terme de complexité asymptotique). Plusieurs interfaces et implémentations existent, selon les fonctionnalités nécessaires au programme.
Les cours d'algorithmique ont largement abordé le sujet, du point de vue de la programmation procédurale. Les interfaces proposent en général des fonctions effectuant des opérations élémentaires : insertion ou suppression d'élément, accès à un élément. En Java, les structures de données implémentent souvent en plus l'interface Iterable, permettant de boucler sur toutes les valeurs contenues dans la structure. Le principe général est cependant de fournir des opérations de bases, qui sont à disposition de l'utilisateur de la structure de données.
En programmation fonctionnelle, on constate en général une inversion des responsabilités entre la structure de donnée et son utilisateur. Plutôt que de proposer à l'utilisateur de parcourir les valeurs contenues (et faire une opération avec chacune d'elle), le style fonctionnel encourage l'utilisateur à déléguer le travail de parcours à la structure de données. Le travail à effectuer est représenté comme une fonction, qui est donnée à la structure (grâce à une interface adaptée), et la structure utilise cette fonction sur chacune de ses données.
Le principal avantage est de déléguer toute la partie algorithmique à la structure, et donc de ne pas avoir à réécrire ces algorithmes dès que le contexte d'utilisation est changé (et ainsi éviter de la duplication de code, réduire les possibilités supplémentaires d'écrire des programmes erronés, mieux libérer l'intention du programmeur de la syntaxe du langage).
Un autre avantage qui apparaîtra plus tard est d'unifier l'utilisation des différentes structures de données : en délégant les calculs, on permet d'avoir des interfaces grandement unifiées avec les mêmes fonctions quel que soit la structure, ou même pour des entités qui ne sont pas des structures de données (par exemple, pour des producteurs).
Prenons un exemple simple et comparons les solutions en Java et en OCaml. Considérons une collection d'éléments, chacun possédant une valeur, et imaginons que nous voulons calculer la somme de ces valeurs. Voici les deux solutions :
Dans la solution en Java, sumOfValuesOf est responsable de faire le parcours de tous les éléments, en utilisant une boucle. En OCaml, sum_of_values_of délègue à la structure de données (ici une liste) la responsabilité de faire le parcours. On indique seulement que l'opération à effectuer à chaque élément est la fonction donnée en premier argument de List.fold_left.
Dans ce premier exemple, on ne peut pas dire qu'une des deux solutions est clairement plus simple que l'autre (quand bien même la deuxième parait exotique au programmeur impératif expérimenté, tout comme la première aux yeux du programmeur fonctionnel). Imaginons maintenant que nous souhaitions faire la somme des valeurs des éléments vérifiant un prédicat de validité.
La solution Java s'est légèrement complexifiée, faisant apparaître une conditionnelle. La solution OCaml dévie complètement de la solution impérative, il s'agit maintenant d'une simple séquence d'opérations : filtrer la liste en gardant les éléments valides, récupérer leurs valeurs, et sommer en partant de 0 . Techniquement, la solution en OCaml ne s'est pas complexifiée, elle s'est juste allongée. Par ailleurs, elle exprime de façon immédiate les intentions du programmeur : filtrer les éléments valides, prendre les valeurs, sommer, ces trois opérations apparaissent dégagées de toute syntaxe. Au contraire, la solution Java doit être lue en entier pour être comprise.
Il ne s'agit cependant pas de dire que la solution fonctionnelle sera toujours meilleure que la solution impérative. Simplement, la possibilité de déléguer les opérations algorithmiques à la structure de données nous offre des outils permettant de simplifier l'écriture de certains programmes. Pour d'autres, nous aurons toujours besoin de programmer les boucles nous-mêmes.
Une différence majeure entre les structures des données en Java et en OCaml concerne leur durée de vie. Toutes les structures de données de la librairie standard de Java sont des structures mutables : faire des actions sur un objet le modifie. Seule la dernière version existe, on ne peut pas garder les versions précédentes d'une structure de données, sans faire de copie explicite (et coûteuse).
À l'inverse, en programmation fonctionnelle, une expression n'a qu'une valeur, il est impossible de changer sa valeur en cours d'évaluation. En particulier, les structures de données sont immortelles et immutables. Une fois définie, une structure existe, contient toujours les même valeur et se comporte toujours de la même façon. Pour faire évoluer la structure, par exemple ajouter un élément, il faut définir une nouvelle structure contenant cet élément supplémentaire. En échange, toutes les versions, tous les constructions successives ayant parmi d'aboutir à cette version de la structure continuent d'exister (jusqu'à tomber dans l'oubli). C'est ce qu'on appelle la persistance.
Prenons par exemple une liste, et faisons des opérations dessus :
Peu importe les opérations faites en utilisant list1, cette liste vaudra toujours [1;2;3;4]. Ce n'est clairement pas le même comportement que les listes ou les piles en Java. C'est pourtant le cas des listes en OCaml, et plus généralement de toutes les variables en programmation fonctionnelle. L'avantage est que le responsable d'une variable garde la main-mise sur sa variable : elle ne peut être modifié par un tiers. Ceci rend les programmes compréhensibles localement. La persistance permet aussi de pouvoir écrire simplement des programmes qui branchent : les structures de données persistentes n'ont pas besoin d'être copiée dans chaque branche, il n'y a pas de problème de gestion de conflits pour l'accès aux structures de données. En fait les programmes fonctionnelles sont naturellement parallélisables.
Les structures persistentes sont-elles propres à la programmation fonctionnelle ? Non, il est tout à fait possible d'écrire des structures persistentes dans les langages impératifs. Traditionnellement, ce n'est pas la façon de faire, car dans les langages des générations précédentes, le programmeur devait gérer l'utilisation de la mémoire utilisée par le programme : notamment rendre la mémoire devenue inutile. Avoir une structure persistente était donc un inconvénient, ou même un problème potentiel. La persistance s'oppose à l'idée de libérer l'espace, et même de réutiliser l'espace, ce qui engendre une plus grande consommation de mémoire. Les langages modernes disposent de garbage collector, chargés de libérer la mémoire devenue inutile. C'est ce qui permet au programmeur de moins se soucier de l'empreinte mémoire de son programme.
La persistance a-t-elle un coût ? Peut-on réaliser toutes les structures de données impératives de façon persistente, avec la même efficacité, en temps et en mémoire ? Non, mais la réponse demande d'être nuancée. Théoriquement, on peut simuler une mémoire persistente avec des temps d'accès logarithmique, donc toute structure de données peut être implémentée fonctionnellement avec un surcoût multiplicatif en temps logarithmique (et constant en espace). Cependant, la plupart des structures de données abstraites classiques admettent des implémentations fonctionnelles aussi efficaces que les structures impératives, et avec un surcoût en espace de l'ordre de la complexité temporelle. En pratique ces structures sont compétitives vis-à-vis des structures en impératifs. Il n'est en revanche jamais possible de pouvoir accéder à n'importe quel élément d'une structure de données en temps sous-logarithmique dans le monde fonctionnel.
Concernant ce dernier point, qui peut être décevant, notons qu'il s'agit d'une borne inférieure en théorie de l'information qui devrait s'appliquer aussi bien en programmation impérative que fonctionnelle, du moment qu'il s'agit de programmation séquentielle (sans parallélisme). En effet, pour pouvoir distinguer un élément parmi $n$, il faut traiter $\log n$ bits d'informations, ce qui nécessite donc au moins $\log n$ tests et branchements. Il n'est donc pas possible d'accéder en temps constant à un élément arbitraire d'un tableau avec un modèle de calcul séquentiel. Les ordinateurs en sont néanmoins capables, parce que l'accès dans un tableau est codé au niveau matériel, avec des circuits faisant de nombreuses opérations en parallèle. Les ordinateurs sont conçus pour traiter des programmes impératifs, et voici un endroit où cela s'en ressent en programmation fonctionnelle. Enfin, il est possible d'abstraire les tableaux sous une interface fonctionnelle, afin d'avoir des complexités similaires à ce qui existe en impératif, tant que la persistance n'est pas utilisée.
Toutes les structures de données de la librairie standard ne sont pas persistentes : OCaml permet aussi la programmation impérative. On reconnait les structures non-persistentes par le fait que les fonctions de modification ne retourne pas de valeurs du type de la structure (par exemple le type de retour est unit. Par exemple :
Les structures persistentes n'étant pas modifiées elles-mêmes, une fonction de modification doit retourner la version modifiée. Par exemple :
Nous n'utiliserons pas pendant ce cours les structures de données non-persistentes.
