Come posso aggiungere a un elenco in schema?

Question

Aggiungere un elemento all'inizio di una alist (lista associativa) è abbastanza semplice:

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

Tuttavia, aggiungere alla coda di un alist è un po' più complicato.Dopo alcuni esperimenti, ho prodotto questo:

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

Tuttavia, mi sembra che questa non sia la soluzione idiomatica.Quindi, come viene solitamente fatto questo nello schema?Oppure è proprio così?

Answer 1

Non si aggiunge a una lista A.Sei su una lista A.

Una a-list è logicamente un insieme di associazioni.Non ti interessa l'ordine degli elementi in un insieme.Tutto ciò che ti interessa è la presenza o l'assenza di un particolare elemento.Nel caso di una a-list, tutto ciò che ti interessa è se esiste un'associazione per un dato tag (cioè una coppia il cui CAR è il valore specificato) e, data tale associazione, il valore associato (cioè, in questo implementazione, il CDR della coppia).

Answer 2

Common Lisp definisce una funzione chiamata ACONS esattamente per questo scopo, dove

(acons key value alist)

è equivalente a:

(cons (cons key value) alist)

Ciò suggerisce fortemente che il semplice consenso su un alista sia idiomatico.Tieni presente che questo significa due cose:

1. Poiché le ricerche vengono generalmente eseguite dalla parte anteriore a quella posteriore, le associazioni aggiunte di recente hanno la precedenza su quelle precedenti.Questo può essere utilizzato per un'implementazione ingenua di ambienti sia lessicali che dinamici.
2. Mentre la conversione in un elenco è O(1), l'aggiunta è generalmente O(n) dove n è la lunghezza dell'elenco, quindi l'uso idiomatico è migliore per le prestazioni oltre ad essere stilisticamente preferibile.