2.40.6.10 Immutable association lists

An immutable association list (or “ialist”) is an ilist of ipairs. The icar of each ipair contains a key value, and the icdr contains the associated data value. They can be used to construct simple look–up tables in Scheme. Note that ialists are probably inappropriate for performance–critical use on large data; in these cases, immutable maps or some other alternative should be employed.

Function: value iassoc key ialist

Function: value iassoc key ialist =

Function: value iassq key ialist

Function: value iassv key ialist

ialist must be an immutable association list: an ilist of ipairs. These procedures find the first ipair in ialist whose icar field is key, and returns that ipair. If no ipair in ialist has key as its icar, then #f is returned. iassq uses eq? to compare key with the icar fields of the ipairs in ialist, while iassv uses eqv? and iassoc uses equal?.

(define e (iq (a 1) (b 2) (c 3)))
(iassq 'a e)                               ⇒  (a 1)
(iassq 'b e)                               ⇒  (b 2)
(iassq 'd e)                               ⇒  #f
(iassq (ilist 'a) (iq ((a)) ((b)) ((c))))  ⇒  #f
(iassoc (ilist 'a) (iq ((a)) ((b)) ((c)))) ⇒  ((a))
(iassq 5 (iq (2 3) (5 7) (11 13)))	   ⇒  *unspecified*
(iassv 5 (iq (2 3) (5 7) (11 13)))	   ⇒  (5 7)

The comparison procedure is used to compare the elements ei of ilist to the key parameter in this way:

(= key (icar ei)) ; ilist is (E1 ... En)

that is, the first argument is always key, and the second argument is one of the ilist elements. Thus one can reliably find the first entry of ialist whose key is greater than five with ‘(iassoc 5 ialist <)’.

Note that fully general ialist searching may be performed with the ifind-tail and ifind procedures, e.g.

;; Look up the first association in ialist with an even key:
(ifind (lambda (a) (even? (icar a))) ialist)

Function: ialist ialist-cons key datum ialist

Equivalent to:

(lambda (key datum ialist) (ipair (ipair key datum) ialist))

Construct a new ialist entry mapping key/datum onto ialist.

Function: alist ialist-copy alist

Make a fresh copy of alist. This means copying each pair that forms an association as well as the spine of the list:

(lambda (a)
  (imap (lambda (elt)
          (icons (icar elt) (icdr elt)))
       a))

Function: ialist ialist-delete key ialist

Function: ialist ialist-delete key ialist =

Delete all associations from ialist with the given key, using 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 ialist argument. The ialist is not disordered: elements that appear in the result ialist occur in the same order as they occur in the argument ialist.

The comparison procedure is used to compare the element keys ki of ialist’s entries to the key parameter in this way: ‘(= key ki)’. Thus, one can reliably remove all entries of ialist whose key is greater than five with ‘(ialist-delete 5 ialist <)’.