Purement fonctionnel

En informatique, l'adjectif purement fonctionnel désigne un algorithme, une structure de données ou un langage de programmation qui exclut les modifications destructives. Par conséquent, les variables en sont exclues et les identificateurs désignent au contraire des valeurs persistantes, immuables. Cela signifie également que les valeurs antérieures à une opération sont toujours accessibles après cette opération, et identiques[1].

Les structures de données purement fonctionnelles constituent un sous-ensemble des structures de données persistantes. Elles sont particulièrement utilisées dans les langages de programmation fonctionnels purs tels que Haskell[1].

Exemples de structure de données purement fonctionnelles

Listes chaînées

Les listes simplement chaînées constituent l'exemple classique de structure de données purement fonctionnelle. Lorsqu'un nouvel élément est ajouté en tête d'une liste, seule une nouvelle cellule est allouée ; le reste de la liste est partagé entre l'ancienne et la nouvelle version. Ainsi, plusieurs versions d'une même liste peuvent coexister sans duplication complète des données[2].

Par exemple, si une liste L est constituée des éléments [2,3,4], la création d'une nouvelle liste [1,2,3,4] ne nécessite que l'allocation du premier nœud ; le suffixe [2,3,4] est partagé entre les deux listes[2].

Arbres

Les arbres de recherche binaires, notamment les arbres rouge-noir, admettent également des implémentations purement fonctionnelles. Une mise à jour consiste à reconstruire uniquement les nœuds situés sur le chemin menant à l'élément modifié, tandis que les autres sous-arbres sont partagés entre les différentes versions[1].

Cette technique permet de conserver simultanément toutes les versions précédentes de l'arbre avec un surcoût mémoire limité. Elle est utilisée dans de nombreuses structures fonctionnelles telles que les ensembles, dictionnaires et files de priorité persistants[1].

D'autres exemples de structures purement fonctionnelles incluent les files en temps réel (real-time queues), les listes à accès aléatoire (random-access lists), les finger trees et les files de priorité de Brodal[1].

Intérêts et applications

L'absence de modification destructive confère plusieurs propriétés importantes :

  • Persistance complète : les anciennes versions d'une structure demeurent accessibles après chaque mise à jour ;
  • Partage structurel : plusieurs versions peuvent partager une grande partie de leurs nœuds, limitant les besoins mémoire ;
  • Transparence référentielle : une expression peut être remplacée par sa valeur sans modifier le comportement du programme ;
  • Sécurité en environnement concurrent : les données immuables peuvent être partagées entre plusieurs processus ou fils d'exécution sans mécanisme de synchronisation supplémentaire[1].

Ces propriétés rendent les structures purement fonctionnelles particulièrement adaptées aux systèmes de gestion de versions, aux compilateurs, aux assistants de preuve, ainsi qu'aux applications parallèles et concurrentes[3].

Valeurs cycliques

Les structures purement fonctionnelles sont généralement représentées sous forme d'arbres ou de graphes acycliques. Cependant, certains langages fonctionnels à évaluation paresseuse permettent la définition de valeurs cycliques immuables, parfois appelées nœuds noués (tying the knot). Une telle structure demeure purement fonctionnelle tant que ses composantes restent immuables après leur création[4].

Voir aussi

Liens externes

Références

  1. 1 2 3 4 5 6 (en) Chris Okasaki, Purely Functional Data Structures, Cambridge University Press, (ISBN 978-0-521-66350-2)
  2. 1 2 (en) Chris Okasaki, Purely Functional Data Structures, Cambridge University Press, , « Persistence »
  3. ↑ (en) Laxman Dhulipala, Guy E. Blelloch, Yan Gu et Yihan Sun, « PaC-trees: Supporting Parallel and Compressed Purely-Functional Collections », arXiv,‎
  4. ↑ (en) Chris Okasaki, Purely Functional Data Structures, Cambridge University Press,

Bibliographie

  • (en) Chris Okasaki, Purely Functional Data Structures, Cambridge University Press, (ISBN 978-0-521-66350-2)
  • (en) James R. Driscoll, Neil Sarnak, Daniel D. Sleator et Robert E. Tarjan, « Making Data Structures Persistent », Journal of Computer and System Sciences, vol. 38, no 1,‎ , p. 86-124
  • icône décorative Portail de l’informatique
Cet article est issu de Wikipédia. Sauf mention contraire, le texte est disponible sous Creative Commons Attribution-Share Alike 4.0. Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.