This site is a static rendering of the Trac instance that was used by R7RS-WG1 for its work on R7RS-small (PDF), which was ratified in 2013. For more information, see Home.

Source for wiki AssociationListsCowan version 2

author

cowan

comment


    

ipnr

173.13.139.236

name

AssociationListsCowan

readonly

0

text

This proposal supersedes the association-list section of SRFI 1, maintaining compatibility but bringing it to parity with Common Lisp.

== Association lists ==

An "association list" (or "alist") is a list of pairs. The car of each pair contains a key value, and the cdr contains the associated data value. They can be used to construct simple look-up tables in Scheme. Note that association lists are probably inappropriate for performance-critical use on large data; in these cases, hash tables or some other alternative should be employed.

`(assoc `''key alist'' [ ''='' ]`)`

`(assq `''key alist''`)`

`(assv `''key alist''`)`

The ''alist'' argument must be an association list -- a list of pairs. These procedures find the first pair in ''alist'' whose car field is ''key'', and returns that pair. If no pair in ''alist'' has ''key'' as its car, then `#f` is returned. `assq` uses `eq?` to compare ''key'' with the car fields of the pairs in ''alist'', while `assv` uses `eqv?` and `assoc` uses ''='' if given and `equal?` otherwise.  (Common Lisp ASSOC.)

{{{
(define e '((a 1) (b 2) (c 3)))
(assq 'a e)                            =>  (a 1)
(assq 'b e)                            =>  (b 2)
(assq 'd e)                            =>  #f
(assq (list 'a) '(((a)) ((b)) ((c))))  =>  #f
(assoc (list 'a) '(((a)) ((b)) ((c)))) =>  ((a))
(assq 5 '((2 3) (5 7) (11 13)))	       =>  *unspecified*
(assv 5 '((2 3) (5 7) (11 13)))	       =>  (5 7)
}}}

`(reverse-assoc `''obj alist'' [ ''='' ] `)`

`(reverse-assq `''obj alist''`)`

`(reverse-assv `''obj alist''`)`

The ''alist'' argument must be an association list -- a list of pairs. These procedures find the first pair in ''alist'' whose cdr (rather than car) field is ''key'' , and return that pair. If no pair in ''alist'' has ''obj'' as its cdr, then `#f` (not the empty list) is returned. The `assq` procedure uses `eq?` to compare obj with the cdr fields of the pairs in ''alist'', while `assv` uses `eqv?` and `assoc` uses ''='' if given and `equal?` otherwise.  (Common Lisp RASSOC.)

{{{
(define e '((a 1) (b 2) (c 3)))
(reverse-assq 1 e)                            =>  (a 1)
(reverse-assq 2 e)                            =>  (b 2)
(reverse-assq 4 e)                            =>  #f
(reverse-assq 7 '((2 3) (5 7) (11 13)))	      =>  *unspecified*
(reverse-assv 7 '((2 3) (5 7) (11 13)))	      =>  (5 7)
}}}

The comparison procedure of `assoc` and `reverse-assoc` is used to compare the elements of ''alist'' to ''key'' in this way:  The first argument is always ''key'', and the second argument is one of the elements of ''list''. Thus one can reliably find the first entry of ''alist'' whose key is greater than five with `(assoc 5 alist <)`.

`(make-alist `''keys values''`)`

Returns a newly allocated alist whose pairs are constructed from the elements of the lists ''keys'' and ''values''.  (Common Lisp PAIRLIS.)

`(alist-cons `''key datum alist''`)`

Cons a new alist entry that maps ''key'' to ''datum'' onto the beginning of ''alist''.  (Common Lisp ACONS.)

`(alist-copy `''alist''`)`

Make a newly allocated copy of ''alist''. This means copying each pair that forms an association as well as the spine of the list.  (Common Lisp COPY-ALIST.)

`(alist-delete `''key alist'' [ ''='' ]`)`

`(alist-delete! `''key alist'' [ ''='' ]`)`

`alist-delete` deletes all associations from ''alist'' with the given ''key'', using the key-comparison procedure ''='', which defaults to `equal?`. The dynamic order in which the various applications of ''= ''are made is not specified.  Return values may share common tails with the ''alist'' argument. The ''alist ''is not disordered -- elements that appear in the result occur in the same order as they occur in ''alist''.  The comparison procedure is used in the same way as by `assoc`.

`alist-delete!` is the linear-update variant of `alist-delete`. It is allowed, but not required, to alter cons cells from the ''alist'' parameter to construct the result.


time

2013-01-12 13:23:42

version

2