Como faço para anexar a um de uma lista no esquema?

Question

Como adicionar um elemento para a cabeça de um alist (lista Associativo) é suficiente simples:

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

Acrescentando à cauda de um alist é um complicado pouco embora. Depois de algumas experiências, eu produzi o seguinte:

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

No entanto, parece-me, que esta não é a solução idiomática. Então como é que isto geralmente é feito no esquema? Ou isso é de fato o caminho?

Answer 1

Você não anexar a um um-lista. Você contras para um um-lista.

Um A-lista é logicamente um conjunto de associações. Você não se preocupam com a ordem dos elementos em um conjunto. Tudo o que importa é a presença ou ausência de um elemento particular. No caso de uma a-lista, tudo o que importa é saber se existe uma associação para uma determinada tag (ou seja, um par cujo carro é o valor especificado), e, dado que a associação, o valor associado (ou seja, neste implementação, o CDR do par).

Answer 2

Lisp comum define uma função chamada Acons exatamente para este fim, onde

(acons key value alist)

é equivalente a:

(cons (cons key value) alist)

Isto sugere fortemente que simplesmente consing para um alist é idiomática. Note que isto significa duas coisas:

1. Como pesquisas são normalmente realizados de frente para trás, associações adicionados recentemente têm precedência sobre os mais velhos. Isso pode ser usado para uma implementação simples de ambos os ambientes lexicais e dinâmicas.
2. Enquanto consing para uma lista é O (1), anexando é geralmente O (n), onde n é o comprimento da lista, de modo que o uso idiomática é melhor para o desempenho, bem como sendo estilìstica preferível.