Lorsque des objets sont amenés à être partagés,
il est intéressant d'en avoir une implémentation fonctionnelle.
Dans le cas d'une implémentation fonctionnelle, les effets de bord
sont interdits. On ne fait que créer de nouveaux objets, modification
éventuelle d'un objet déja existant. Par exemple, si l'on
suppose que la classe Liste utilisée ci-dessous est implémentée
dans un style fonctionnel, et que la liste l1 contient les objets
a,
b
et c, on devra avoir à la fin des instructions
Liste l2 = l1;
l1 = l1.ajouter(d);
une liste l1 contenant a, b, c
et d et une liste l2 contenant a, b
et c : la modification de l1 n'a pas affecté
l2.
Ce type de liste est utilisé par exemple dans les langages symboliques
comme Lisp ou Scheme.
En Scheme :
-
le symbole '() représente la liste vide.
-
On dispose d'un constructeur cons(v,l) qui à partir d'une
valeur v et d'une liste l crée une nouvelle liste
dont le premier élément, appelé le car, est v,
et les autres éléments forment la liste l, appelée
cdr .
-
On dispose de deux sélecteurs car(l) et cdr(l)
qui renvoient respectivement le premier élément de la liste
l
et la liste l privée de son premier élément.
Ces deux sélecteurs ne peuvent être appliqués à
la liste vide.
-
La fonction append(l1,l2) concatène les deux listes l1
et l2. Concrètement, elle crée une copie de l1 dont le dernier
élément référence l2 comme suite de la liste.
Ainsi, ni l1 ni l2 ne sont modifiées.
-
La fonction length(l) renvoie la longueur de la liste l.
-
La fonction reverse(l) crée une liste contenant les mêmes
éléments que l, mais dans un ordre inversé.
La classe SList implémente une structure de liste comparable
à celle fournie par Scheme.
Notons que :
-
il n'est pas envisageable de représenter par null la liste
vide. Cela obligerait à définir toutes les méthodes
pouvant porter sur une liste vide comme méthodes de classe.
-
L'implémentation de SList garantie qu'un utilisateur ne
pourra pas créer de liste vide. La seule liste vide existente sera
la constante EMPTY_LIST.
-
Les méthodes length(), append(SList) et reverse()
sont implémentées de façon récursive grâce
aux équations suivantes :
-
length(l) = 0 si l est vide, 1 + length(cdr(l))
sinon
-
append(l1,l2) = l2 si l1 est vide, cons(car(l1),append(cdr(l1),l2))
sinon
-
rappend(l1,l2) = l2 si l1 est vide, rappend(cdr(l1),
cons(car(l1),l2)) sinon
-
reverse(l) = rappend(l,'())
-
La méthode rappend(SList) est un exemple de récursivité
terminale.