assq, assv, assoc, assp - association list lookup

LIBRARY

(import (rnrs))                     ;R6RS
(import (rnrs lists))               ;R6RS
(import (scheme r5rs))              ;R7RS
(import (scheme base))              ;R7RS

SYNOPSIS

(assq obj alist)
(assv obj alist)
(assoc obj alist)

(assp proc alist)                   ;R6RS
(assoc obj alist compare)           ;R7RS

DESCRIPTION

These procedures find the first pair in alist whose car field satisfies a given condition, and returns that pair without traversing alist further. If no pair in alist satisfies the condition, then #f is returned.
assoc, assv, and assq
These procedures look for a pair that has obj as its car. The assoc procedure uses equal? to compare obj with the car fields of the pairs in alist, while assv uses eqv? and assq uses eq?.
assp (R6RS)
The assp procedure successively applies proc to the car fields of alist and looks for a pair for which it returns a true value. Proc is always called in the same dynamic environment as assp itself. Proc should accept one argument and return a single value. Proc should not mutate alist.
assoc (R7RS)
Assoc uses compare if given and equal? otherwise. There is nothing said about the compare procedure in R7RS. Note in particular that its argument order is not specified; it might be called with the object as the first or second argument.

RETURN VALUES

Returns a pair from alist or #f.

EXAMPLES

(define img '((src "lambda.png") (width "100") (height "120")))
(assq 'src img)             => (src "lambda.png")
(assq 'width img)           => (width "100")
(assq 'alt img)             => #f

; Common pattern to look up a value using a default
(cond ((assq 'style img) => cadr)
      (else ""))            => ""

; Newly allocated pairs are not eq? to other pairs
(assq (list 'a) '(((a)) ((b)) ((c))))
                            => #f
; Instead use equal? to compare based on the structure
(assoc (list 'a) '(((a)) ((b)) ((c))))
                            => ((a))

; Behavior of eq? and assq on numbers is not specified
(assq 5 '((2 3) (5 7) (11 13)))
                            => unspecified
; So use eqv? and assv instead
(assv 5 '((2 3) (5 7) (11 13)))
                            => (5 7)

; Custom tests can be done with assp in R6RS.
(define d '((3 a) (1 b) (4 c)))
(assp even? d)              => (4 c)
(assp odd? d)               => (3 a)

; Assp in R6RS provides a test and the optional compare
; procedure in R7RS provides a comparison. Using it as
; test is possible, but awkward.
(define d '((3 a) (1 b) (4 c)))
(assoc #f d (lambda (x y) (even? (or x y))))
                            => (4 c)
(assoc #f d (lambda (x y) (odd? (or x y))))
                            => (3 a)

; When a custom comparison is needed instead of a test,
; R7RS/SRFI-1 is more elegant than in the above example:
(define d '((1 1) (2 4) (3 9)))
(assoc 2.0 d =)             => (2 4)
(assoc 2.0 d <)             => unspecified in R7RS
(assoc 2.0 d <)             => (3 9)     ; in SRFI-1

APPLICATION USAGE

Association lists are often used as a lightweight alternative to hash tables. They have the benefit of being printable as S-expressions. The linear cost of lookup is balanced by the lower constant cost when the number of keys is small.

The assq procedure is appropriate when keys are symbols (or when you would otherwise compare the keys with eq?). When the keys are characters or numbers, use assv. When the keys are strings, pairs, vectors, bytevectors or a variation of types so far mentioned, use assoc. When the keys are other types, use assp or assoc with a compare procedure.

RATIONALE

Although they are ordinarily used as predicates, these procedures do not have question marks in their names because they return useful values rather than just #t or #f.

COMPATIBILITY

R4RS and R5RS have assq, assv, and the same assoc as R6RS. R7RS modified assoc to give it an optional comparison procedure in the SRFI-1 tradition. R6RS added the assv procedure instead. R6RS specifies that these procedures do not traverse alist further once a matching pair has been found. In practice this is how it will be implemented in non-R6RS implementations as well.

Association lists are common in Lisp dialects. The assoc in Common Lisp returns NIL instead of #f when there is no matching pair.

ERRORS

This procedure can raise exceptions with the following condition types:
&assertion (R6RS)
The wrong number of arguments was passed or an argument was outside its domain, i.e. alist was not a list of pairs, or proc was not a procedure that accepts one argument and returns one value.
R7RS
The assertions described above are errors. Implementations may signal an error, extend the procedure's domain of definition to include such arguments, or fail catastrophically.

SEE ALSO

cons(3scm), find(3scm), make-hashtable(3scm), memq(3scm)

STANDARDS

R4RS, IEEE Scheme, R5RS, R6RS, R7RS, SRFI-1

HISTORY

A variant of assoc that returns the cadr of the matching pair appeared in Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I (McCarthy, 1960). It was used to represent environments in eval.

AUTHORS

This page is part of the scheme-manpages project. It includes materials from the RnRS documents. More information can be found at https://github.com/schemedoc/manpages/.


Markup created by unroff 1.0sc,    March 04, 2023.