Pile fonctionnelle

Une pile fonctionnelle est une implémentation du type abstrait pile avec une interface fonctionnelle.

Voici les détails de ces opérations :

Implémentation

L'implémentation d'une pile fonctionnelle ne pose pas de problème. Typiquement, une liste est utilisée. De cette manière, l'opération empiler d'une pile est identique à l'opération cons sur la liste, l'opération de dépiler une pile p n'est autre que l'opération p.queue sur la liste, l'opération de récupérer l'objet au sommet de la pile est simplement l'opération p.tête sur la liste (après avoir vérifié que la liste n'est pas vide), et pour déterminer si la pile est vide, il suffit de comparer celle-ci à la valeur NIL.

La complexité asymptotique de chacune des opérations sur une pile fonctionnelle implémentée sous forme de liste est O(1) (temps constant).

La localité d'une implémentation de la file fonctionnelle sous forme de liste peut ne pas être très bonne, selon la qualité du ramasse-miettes.html employé par le système. Il est possible que les cellules de la liste soient dispersées dans la mémoire, ce qui diminue considérablement la localité.

Une implémentation sous forme de tableau de la pile fonctionnelle n'est pas envisageable. En fait, une telle implémentation nécessiterait que le tableau soit copié à chaque modification de la pile afin d'éviter des effets de bord, avec comme résultat une complexité asymptotique linéaire de ces opérations.