How do I append to an alist in scheme?
-
01-07-2019 - |
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?
Solution
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).
OTHER TIPS
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:
- 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.
- 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.