Wie erreiche ich eine Liste in Schema anhängen?

Question

Das Hinzufügen eines Elements auf den Kopf eines alist (Assoziative Liste) ist einfach:

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

Anfügen an den Schwanz eines alist ist allerdings etwas schwieriger. Nach einigem Experimentieren, produzierte ich diese:

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

Allerdings scheint es mir, dass dies nicht die idiomatische Lösung. Also, wie ist dies in der Regel in Schema getan? Oder ist diese Tatsache in der Art und Weise?

Answer 1

Sie anhängen nicht auf eine a-Liste. Sie cons auf eine a-Liste.

Eine a-Liste ist logisch eine Reihe von Verbänden. Sie müssen nicht über die Reihenfolge der Elemente in einem Satz kümmern. Alles über die Sie interessieren ist das Vorhandensein oder Fehlen eines bestimmten Elements. Im Falle einer a-Liste, alle kümmern uns um, ob es eine Verbindung für einen bestimmten Tag vorhanden ist (dh ein Paar, dessen Auto der angegebene Wert ist), und gegeben, dass Verein, der zugehörige Wert (dh in diesem Implementierung, die CDR des Paares).

Answer 2

Common Lisp definiert eine Funktion namens Acons für genau diesen Zweck, wobei

(acons key value alist)

entspricht:

(cons (cons key value) alist)

Dies legt nahe, dass einfach consing auf eine alist idiomatische ist. Beachten Sie, dass dies bedeutet zwei Dinge:

1. Wie sucht in der Regel von vorne durchgeführt werden, vor kurzem hinzugefügt Verbände übernehmen ältere Vorrang zu unterstützen. Dies kann für eine naive Umsetzung beider lexikalischen und dynamischen Umgebungen verwendet werden.
2. Während consing auf eine Liste O (1), Anfügen ist in der Regel O (n), wobei n die Länge der Liste, so dass die idiomatische Nutzung ist auch für die Leistung am besten als stilistisch bevorzugt wird.