Comment puis-je ajouter à une liste dans un schéma?

Question

Ajouter un élément à la tête d'une liste (liste associative) est assez simple:

> (cons '(ding . 53) '((foo . 42) (bar . 27)))
((ding . 53) (foo . 42) (bar . 27))

Ajouter une liste à la liste est un peu plus compliqué. Après quelques expériences, j'ai produit ceci:

> (define (alist-append alist pair) `(,@alist ,pair))
> (alist-append '((foo . 42) (bar . 27)) '(ding . 53))
'((foo . 42) (bar . 27) (ding . 53))

Cependant, il me semble que ce n’est pas la solution idiomatique. Alors, comment cela se fait-il habituellement dans un schéma? Ou est-ce vraiment le chemin?

Answer 1

Vous n’ajoutez pas à une liste. Vous par contre sur une liste.

Une a-liste est logiquement un ensemble d’associations. Vous ne vous souciez pas de l'ordre des éléments dans un ensemble. Tout ce qui compte pour vous, c'est la présence ou l'absence d'un élément particulier. Dans le cas d’une liste a, tout ce qui vous importe est de savoir s’il existe une association pour une balise donnée (c’est-à-dire une paire dont CAR est la valeur spécifiée) et, étant donné cette association, la valeur associée (c.-à-d. implémentation, la CDR de la paire).

Answer 2

Common Lisp définit une fonction appelée ACONS à cet effet, où

(acons key value alist)

est équivalent à:

(cons (cons key value) alist)

Cela suggère fortement que consister simplement dans une liste est idiomatique. Notez que cela signifie deux choses:

1. Les recherches étant généralement effectuées de l'avant à l'arrière, les associations récemment ajoutées ont priorité sur les anciennes. Ceci peut être utilisé pour une implémentation naïve des environnements lexicaux et dynamiques.
2. Si la liste contient O (1), l’ajout est généralement O (n), où n est la longueur de la liste. Par conséquent, l’utilisation idiomatique est préférable pour les performances mais également pour le style.