alist.c

Status: useful (particularly if you don't know about ass*-set!)

Description: alists (association lists) are a somewhat common method of using lists in lisp-like languages to represent collections indexed by keys. The idea is that we can represent a collection of (key value) pairs with a list containing cons cells in the form (key . value).

Example: say I want to create a data structure that allows me to put in my cat's names, assign a certain value to them, and later get at the value by name. Using alists, I could do this as follows:

(define cats '((tiger . lazy-fat-and-surly)
               (frodo . fluffy-and-evil)
               (loki  . insane)))

Now, using alist operations, I can easily find the value associated with tiger

(assq 'tiger cats)
=> (tiger . lazy-fat-and-surly)

(cdr (assq 'tiger cats))
=> lazy-fat-and-surly

(assq-ref cats 'tiger)
=> lazy-fat-and-surly

Guile provides most of the common operations on alists. The operations generally come in triples, where part of the name is either assq, assv, or assoc; these correspond to testing for key equality by means of scheme's eq?, eqv? or equal? operators.

Also keep in mind that alists are really only useful with small sets. As the set becomes large, so does the access time, so an alternative approach, like a hashtable, should be considered.

Function: acons car cdr alist

C Function: SCM scm_acons (SCM car, SCM cdr, SCM alist)

acons returns an alist with (car . cdr) placed on alist

(acons 'tom 'dead cats)
=> ((tom . dead)
    (tiger . lazy-fat-and-surly)
    (frodo . fluffy-and-evil)
    (loki . insane))

Note that this is a quick and stupid operation that doesn't look at the arguments:

(acons 'tiger 'not-at-all-surly-you-can-withdraw-the-claws-now cats)
=> ((tiger . not-at-all-surly-you-can-withdraw-the-claws-now)
    (tiger . lazy-fat-and-surly)
    (frodo . fluffy-and-evil)
    (loki . insane))

To insure a unique value for each key, see the ass[q,v,oc]-set! functions below.

(acons 'tiger 'loki 'frodo)
=> ((tiger . loki) . frodo)

The same operation can be performed manually by doing (cons (cons car cdr) alist)

The original alist isn't modified, so if you want alist to be set to alist + this new pair, you'll have to do (set! alist (acons car cdr alist))

Function: sloppy-assq elem alist

Function: sloppy-assv elem alist

Function: sloppy-assoc elem alist

C Function: SCM scm_sloppy_assq (SCM elem, SCM alist)

C Function: SCM scm_sloppy_assv (SCM elem, SCM alist)

C Function: SCM scm_sloppy_assoc (SCM elem, SCM alist)

Versions of the association functions that don't do robust argument checking.

(sloppy-assq 'tiger cats)
=> (tiger . lazy-fat-and-surly)

Function: assq elem alist

Function: assv elem alist

Function: assoc elem alist

C Function: SCM scm_assq (SCM elem, SCM alist)

C Function: SCM scm_assv (SCM elem, SCM alist)

C Function: SCM scm_assoc (SCM elem, SCM alist)

These are the procedures described in rnrs. These differ from the sloppy-* versions in that they actually make sure the arguments are correct.

Function: assq-ref alist key

Function: assv-ref alist key

Function: assoc-ref alist key

C Function: SCM scm_assq_ref (SCM alist, SCM key)

C Function: SCM scm_assv_ref (SCM alist, SCM key)

C Function: SCM scm_assoc_ref (SCM alist, SCM key)

These functions provide an interface to alists similar to vector-ref for vectors. The result is the value associated with key.

(assq-ref cats 'tiger)
=> lazy-fat-and-surly

Function: assq-set! alist key val

Function: assv-set! alist key val

Function: assoc-set! alist key val

C Function: SCM scm_assv_set_x (SCM alist, SCM key, SCM val)

C Function: SCM scm_assq_set_x (SCM alist, SCM key, SCM val)

C Function: SCM scm_assoc_set_x (SCM alist, SCM key, SCM val)

The ass*-set! functions provide an easy way to add a value and a key in the alist, which won't create duplicates.

(assq-set! cats 'tiger 'not-at-all-surly-you-can-withdraw-the-claws-now)
=> ((tiger . not-at-all-surly-you-can-withdraw-the-claws-now) 
    (frodo . fluffy-and-evil)
    (loki . insane))
cats
=> ((tiger . not-at-all-surly-you-can-withdraw-the-claws-now) 
    (frodo . fluffy-and-evil)
    (loki . insane))

Note that, if you use this to add values to a list, you must still set! the list to the return value.

(assq-set! cats 'tom 'dead)
=> ((tom . dead)
    (tiger . not-at-all-surly-you-can-withdraw-the-claws-now)
    (frodo . fluffy-and-evil)
    (loki . insane))

cats
=> ((tiger . not-at-all-surly-you-can-withdraw-the-claws-now) 
    (frodo . fluffy-and-evil)
    (loki . insane)) 

(set! cats (assq-set! cats 'tom 'dead))
cats
=> ((tom . dead)
    (tiger . not-at-all-surly-you-can-withdraw-the-claws-now) 
    (frodo . fluffy-and-evil)
    (loki . insane))

Function: assq-remove! alist key

Function: assv-remove! alist key

Function: assoc-remove! alist key

C Function: SCM scm_assq_remove_x (SCM alist, SCM key)

C Function: SCM scm_assv_remove_x (SCM alist, SCM key)

C Function: SCM scm_assoc_remove_x (SCM alist, SCM key)

The ass*-remove! functions, as their name implies, remove the pair associated with key from alist. As with the ass*-set! functions, you should use (set! alist (ass*-remove! alist key)), to insure that alist is actually what you want it to be.

(set! cats (assq-remove! cats 'tom))
cats
=> ((tiger . not-at-all-surly-you-can-withdraw-the-claws-now) 
    (frodo . fluffy-and-evil)
    (loki . insane))