How do I append to an alist in scheme?

Question

Adding an element to the head of an alist (Associative list) is simple enough:

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

Appending to the tail of an alist is a bit trickier though. After some experimenting, I produced this:

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

However, it seems to me, that this isn't the idiomatic solution. So how is this usually done in scheme? Or is this in fact the way?

Answer 1

You don't append to an a-list. You cons onto an a-list.

An a-list is logically a set of associations. You don't care about the order of elements in a set. All you care about is presence or absence of a particular element. In the case of an a-list, all you care about is whether there exists an association for a given tag (i.e., a pair whose CAR is the specified value), and, given that association, the associated value (i.e., in this implementation, the CDR of the pair).

Answer 2

Common Lisp defines a function called ACONS for exactly this purpose, where

(acons key value alist)

is equivalent to:

(cons (cons key value) alist)

This strongly suggests that simply consing onto an alist is idiomatic. Note that this means two things:

1. As searches are usually performed from front to back, recently added associations take precedence over older ones. This can be used for a naive implementation of both lexical and dynamic environments.
2. While consing onto a list is O(1), appending is generally O(n) where n is the length of the list, so the idiomatic usage is best for performance as well as being stylistically preferable.