Skip to content
LumenaryAcademy
Practice 60 min

Association lists, vectors, strings and records

Lookup tables made of pairs, constant-time indexed vectors, text as characters and strings, and record types with named fields.

Code tested · 4AI-draftedAwaiting review by a computer scientist
MotivationH

Beyond the plain list

Lists can represent anything, but not everything is best represented as a plain list. A phone book is a mapping from names to numbers. A chessboard is sixty-four squares you want to reach by position, instantly. A sentence is a string of characters. A library book has a title, an author and a number of copies, and code that writes (caddr b) to get the year is code that nobody can read.

R7RS gives you a small, well-chosen set of tools for these jobs. Association lists are lookup tables built from pairs, perfect for small mappings and for representing environments. Vectors are fixed-size arrays with constant-time access by index. Strings and characters handle text, with full Unicode. Records define new data types with named fields. This lesson covers each, shows what it costs, and ends with advice on choosing between them.

Worked examplesH

Association lists

Definition— Association list (alist)

A list of pairs, each pairing a key with a value: ((kenya . "Nairobi") (peru . "Lima")). assq, assv and assoc search an alist and return the first pair whose key matches (using eq?, eqv? and equal? respectively), or #f.

scheme
(import (scheme base) (scheme write))

(define capitals
  '((kenya . "Nairobi") (peru . "Lima") (japan . "Tokyo") (norway . "Oslo")))

(write (assq 'peru capitals)) (newline)
(write (cdr (assq 'japan capitals))) (newline)
(write (assq 'chile capitals)) (newline)
(write (assv 2 '((1 . "one") (2 . "two")))) (newline)
(write (assoc "b" '(("a" . 1) ("b" . 2)))) (newline)

(define (lookup key alist default)
  (let ((entry (assq key alist)))
    (if entry (cdr entry) default)))

(define updated (cons '(peru . "Lima (capital)") capitals))
(write (lookup 'peru updated "?")) (newline)
(write (lookup 'peru capitals "?")) (newline)
(write (lookup 'chile capitals "unknown")) (newline)

(define (count-words words)
  (let loop ((words words) (counts '()))
    (if (null? words)
        counts
        (let* ((w (car words))
               (entry (assoc w counts)))
          (if entry
              (begin (set-cdr! entry (+ (cdr entry) 1))
                     (loop (cdr words) counts))
              (loop (cdr words) (cons (cons w 1) counts)))))))

(write (count-words '("to" "be" "or" "not" "to" "be"))) (newline)
(write (map car capitals)) (newline)
text
(peru . "Lima")
"Tokyo"
#f
(2 . "two")
("b" . 2)
"Lima (capital)"
"Lima"
"unknown"
(("not" . 1) ("or" . 1) ("be" . 2) ("to" . 2))
(kenya peru japan norway)
  • The lookup procedures return the whole pair, not just the value. That lets you tell "the key is absent" (#f) from "the key is present with the value #f", and it is why lookup takes the cdr only after checking.
  • Choose the procedure by key type: assq for symbols, assv for numbers and characters, assoc for strings and lists.
  • Functional update: consing a new pair onto the front shadows the old one, because lookups stop at the first match. updated sees the new value; capitals is unchanged, and the two alists share all their old pairs. This is exactly how environments in interpreters work, and lesson 8 relies on it.
  • count-words builds an alist of word counts. It updates counts in place with set-cdr!, which is safe because it only mutates pairs it created itself, never the quoted literal.

Alist lookup is a linear search, so it costs O(n)O(n). For a dozen keys that is faster than anything fancier; for thousands, use a hash table (below).

Worked examplesH

Vectors

Definition— Vector

A fixed-length sequence of values stored contiguously, written #(1 2 3). vector-ref and vector-set! read and write any element by its index in constant time. Unlike a list, a vector cannot grow; to change its size, copy it.

scheme
(import (scheme base) (scheme write))

(define v (make-vector 5 0))
(vector-set! v 0 'first)
(vector-set! v 4 'last)
(write v) (newline)
(write (list (vector-length v) (vector-ref v 4))) (newline)

(define primes (vector 2 3 5 7 11 13 17 19 23 29 31 37))
(write (vector->list primes 0 4)) (newline)
(write (list->vector '(a b c))) (newline)
(write (vector-map (lambda (p) (* p p)) (vector-copy primes 0 5))) (newline)
(write (vector-copy primes 3 6)) (newline)
(write (vector-append #(1 2) #(3))) (newline)

(define (binary-search vec target)
  (let loop ((lo 0) (hi (- (vector-length vec) 1)))
    (if (> lo hi)
        #f
        (let* ((mid (quotient (+ lo hi) 2))
               (x (vector-ref vec mid)))
          (cond ((= x target) mid)
                ((< x target) (loop (+ mid 1) hi))
                (else (loop lo (- mid 1))))))))

(write (list (binary-search primes 23) (binary-search primes 24))) (newline)

(define histogram (make-vector 4 0))
(for-each (lambda (score)
            (let ((bucket (min 3 (quotient score 25))))
              (vector-set! histogram bucket (+ 1 (vector-ref histogram bucket)))))
          '(12 47 88 91 30 64 75 100 5))
(write histogram) (newline)
text
#(first 0 0 0 last)
(5 last)
(2 3 5 7)
#(a b c)
#(4 9 25 49 121)
#(7 11 13)
#(1 2 3)
(8 #f)
#(2 2 1 4)
  • make-vector creates a vector of a given length filled with a value; vector builds one from its arguments.
  • Many vector procedures accept optional start and end indexes: (vector->list primes 0 4) converts the first four elements, and (vector-copy primes 3 6) copies indexes 3, 4 and 5.
  • vector-map and vector-for-each mirror map and for-each.
  • Binary search needs constant-time indexing, so it belongs to vectors, not lists. On the twelve primes it found 23 at index 8 in at most four comparisons; on a sorted vector of a million elements it needs at most twenty. It returns #f for a value that is absent.
  • The histogram counts scores into four buckets (0 to 24, 25 to 49, 50 to 74, 75 and up). Updating counts by index is the classic job for a mutable vector.

Example— A grid as a vector of vectors

Two-dimensional data such as a game board is usually a vector of rows, each row a vector. Hide the representation behind three small procedures:

scheme
(define (make-grid rows cols fill)
  (let ((g (make-vector rows)))
    (do ((r 0 (+ r 1))) ((= r rows) g)
      (vector-set! g r (make-vector cols fill)))))

(define (grid-ref g r c) (vector-ref (vector-ref g r) c))
(define (grid-set! g r c v) (vector-set! (vector-ref g r) c v))

(define board (make-grid 3 3 '_))
(grid-set! board 0 0 'x)
(grid-set! board 1 1 'o)
(grid-set! board 2 2 'x)
board                  ; => #(#(x _ _) #(_ o _) #(_ _ x))
(grid-ref board 1 1)   ; => o

Why the loop in make-grid, when (make-vector 3 (make-vector 3 '_)) looks shorter? Because that expression evaluates (make-vector 3 '_) once and puts the same row object in all three slots. Setting one square then appears to set a whole column:

scheme
(define shared (make-vector 3 (make-vector 3 '_)))
(vector-set! (vector-ref shared 0) 0 'x)
shared                 ; => #(#(x _ _) #(x _ _) #(x _ _))

This aliasing mistake exists in every language with mutable arrays (Python's [[0] * 3] * 3 behaves the same way). The cure is to create each row separately, as the loop does.

A literal vector such as #(1 2) is a constant, like a quoted list: read it freely, but create vectors you intend to modify with make-vector, vector or vector-copy.

Worked examplesH

Characters and strings

scheme
(import (scheme base) (scheme write) (scheme char))

(define s "Kigali, Rwanda")
(write (list (string-length s) (string-ref s 0) (substring s 0 6))) (newline)
(write (string-upcase s)) (newline)
(write (string->list "abc")) (newline)
(write (list->string (list #\o #\k))) (newline)
(write (list (char->integer #\A) (integer->char 97) (char-upcase #\z))) (newline)
(write (list (char-alphabetic? #\x) (char-numeric? #\7) (char-whitespace? #\space))) (newline)
(write (list (string->number "42") (string->number "3/4") (string->number "abc") (number->string 255 2))) (newline)
(write (string=? "abc" (string #\a #\b #\c))) (newline)

(define (split-on ch str)
  (let loop ((chars (string->list str)) (current '()) (parts '()))
    (cond ((null? chars)
           (reverse (cons (list->string (reverse current)) parts)))
          ((char=? (car chars) ch)
           (loop (cdr chars) '() (cons (list->string (reverse current)) parts)))
          (else
           (loop (cdr chars) (cons (car chars) current) parts)))))

(write (split-on #\, "red,green,,blue")) (newline)

(define (caesar shift text)
  (string-map
   (lambda (c)
     (if (char-alphabetic? c)
         (let ((base (if (char-upper-case? c) 65 97)))
           (integer->char (+ base (modulo (+ (- (char->integer c) base) shift) 26))))
         c))
   text))

(write (caesar 3 "Hello, Scheme!")) (newline)
(write (caesar -3 (caesar 3 "Hello, Scheme!"))) (newline)

(define out (open-output-string))
(write 'total out)
(write-string ": " out)
(write (+ 40 2) out)
(write (get-output-string out)) (newline)
text
(14 #\K "Kigali")
"KIGALI, RWANDA"
(#\a #\b #\c)
"ok"
(65 #\a #\Z)
(#t #t #t)
(42 3/4 #f "11111111")
#t
("red" "green" "" "blue")
"Khoor, Vfkhph!"
"Hello, Scheme!"
"total: 42"
  • A character is written #\K, #\space or #\newline; a string is a sequence of characters. string-ref takes an index, substring a start and an end.
  • Case conversion and character classification (char-alphabetic?, char-numeric?) live in (scheme char) and follow Unicode rules.
  • string->number parses any number Scheme can read, including the rational 3/4, and returns #f for text that is not a number, a convenient test. number->string takes an optional radix.
  • Compare strings with string=? (or equal?), never with eq?. string<? and friends compare alphabetically by code point.
  • R7RS-small has no string-splitting procedure, so split-on converts the string to a list of characters and collects runs between separators. Note the empty string between the two commas.
  • The Caesar cipher (shift each letter three places, as Julius Caesar reportedly did) uses string-map and character codes. Shifting by −3 restores the original.
  • Strings are sequences of Unicode characters, not bytes. (string-length "Olá") is 3 and (string-length "こんにちは") is 5, while the UTF-8 encoding of "Olá" takes 4 bytes, as (bytevector-length (string->utf8 "Olá")) shows. Case conversion follows Unicode too: in Chibi-Scheme, (string-upcase "straße") gives "STRASSE", because the German sharp s has no single-character capital in that mapping. Text processing that assumes one byte per character, or that upper-casing never changes a string's length, breaks on real-world names and languages.
  • A string port collects output in memory: write, display and write-string all accept a port as an extra argument, and get-output-string returns everything written so far. It is the standard way to build a string from many pieces.
Worked examplesH

Records: data types with named fields

Definition— Record type

A new, distinct data type defined with define-record-type, which creates a constructor, a type predicate, an accessor for each field and, optionally, a modifier for any field that may change.

scheme
(import (scheme base) (scheme write) (scheme cxr))

(define-record-type book
  (make-book title author year copies)
  book?
  (title book-title)
  (author book-author)
  (year book-year)
  (copies book-copies set-book-copies!))

(define shelf
  (list (make-book "Things Fall Apart" "Chinua Achebe" 1958 2)
        (make-book "Pedro Páramo" "Juan Rulfo" 1955 1)
        (make-book "The Tale of Genji" "Murasaki Shikibu" 1008 3)))

(define (lend! b)
  (if (> (book-copies b) 0)
      (begin (set-book-copies! b (- (book-copies b) 1)) #t)
      #f))

(define (filter-books keep? books)
  (cond ((null? books) '())
        ((keep? (car books)) (cons (car books) (filter-books keep? (cdr books))))
        (else (filter-books keep? (cdr books)))))

(define genji (caddr shelf))
(write (list (book? genji) (book? "Genji") (book-author genji))) (newline)
(let* ((pedro (cadr shelf))
       (first-loan (lend! pedro))
       (second-loan (lend! pedro)))
  (write (list first-loan second-loan)) (newline))
(write (map book-copies shelf)) (newline)
(write (map book-title (filter-books (lambda (b) (< (book-year b) 1957)) shelf))) (newline)
text
(#t #f "Murasaki Shikibu")
(#t #f)
(2 0 3)
("Pedro Páramo" "The Tale of Genji")

The definition reads: a type named book; a constructor make-book taking four fields in order; a predicate book?; then each field with its accessor, and for copies a modifier set-book-copies!. Fields without a modifier cannot be changed, which documents your intent.

Records are a genuinely new type: book? is true only for books, and no list, vector or other record type will pass it. That makes records safer than "a list whose third element happens to be the year", and the accessor names make code self-explanatory. lend! succeeded once and then refused, because Pedro Páramo had only one copy. How a record prints is up to the implementation, so print its fields, as here, rather than the record itself.

define-record-type began as SRFI 9 in 1999 and became part of the standard in R7RS, a typical path for Scheme features: proven in a SRFI, then adopted by the report.

ComputationC

Choosing a structure

StructureLookupAddGrows?Best for
listby position O(n)O(n)at front O(1)O(1)yessequences processed front to back, recursion, sharing
alistby key O(n)O(n)at front O(1)O(1)yessmall maps, environments, functional update
vectorby index O(1)O(1)no (copy to resize)notables, grids, binary search, counting by index
stringby index (often O(1)O(1))no (copy)notext
recordby field O(1)O(1)nonoentities with named fields
hash tableby key, O(1)O(1) on averageO(1)O(1) on averageyeslarge maps

Hash tables are not part of R7RS-small, but every serious implementation provides them, usually through SRFI 69 or the newer SRFI 125. With SRFI 69, as in Chibi-Scheme, Gauche, CHICKEN and Guile, the core looks like this:

scheme
(import (srfi 69))
(define phone (make-hash-table equal?))
(hash-table-set! phone "Ama" "024-555-0101")
(hash-table-ref/default phone "Ama" #f)    ; => "024-555-0101"
(hash-table-ref/default phone "Kofi" #f)   ; => #f

The rule of thumb many Scheme programmers follow: start with lists and alists, which are simple, printable and easy to test at the REPL; switch to a vector when you need positions and to a hash table when a map grows past a few dozen keys or sits in a hot loop; and define a record type as soon as a piece of data has named fields that more than one procedure uses.

ExplanationH

Data abstraction: hide the representation

The grid procedures above illustrate the most important habit in this lesson, one that Scheme programmers have practised since the 1980s: separate how data is used from how it is represented. Code elsewhere in a game calls grid-ref and grid-set!; it never mentions vectors. If you later decide to store the board as a single flat vector of nine elements (index (+ (* r 3) c)), or as a hash table of only the occupied squares, you rewrite three procedures and nothing else changes.

The same applies to every structure here. A phone book module might offer make-phone-book, phone-book-add and phone-book-lookup, implemented today with an alist. When the data grows, the internals switch to a hash table and every caller keeps working. Records make this discipline almost automatic, because their constructors and accessors are such an interface, and the underlying representation is hidden by the implementation.

Two practical consequences follow. First, write the interface procedures before the code that uses them, and test them at the REPL on small examples. Second, resist the temptation to reach "through" an abstraction: code that calls vector-ref on a board, or cdr on an entry from someone else's alist, will break the day the representation changes. R7RS libraries (define-library with an export list) let you enforce this, by exporting only the interface procedures; lesson 8 shows a library definition.

Common misconceptionsH

Common mistakes

Misconception

Taking the cdr of a failed lookup. (cdr (assq 'chile capitals)) raises an error because assq returned #f. Always check the result first, or wrap the pattern in a helper such as lookup.

Misconception

Mutating literal constants. (vector-set! #(1 2 3) 0 9), (string-set! "abc" 0 #\x) and (set-car! '(1 2) 9) are all errors in R7RS because literals are constants. Chibi-Scheme and many other implementations reject them at run time. Copy first: (vector-copy #(1 2 3)), (string-copy "abc"), (list-copy '(1 2)).

Misconception

Using assq with string keys. Two strings with the same characters are usually different objects, so (assq "b" '(("a" . 1) ("b" . 2))) may return #f. Use assoc, which compares with equal?.

Misconception

Assuming an alist's keys are unique. Nothing prevents an alist from containing the same key twice; functional update relies on it. Lookups return the first match, so the newer entry wins, but procedures that walk the whole alist (to list its keys, count entries, or "delete" a key) must take the shadowed duplicates into account. To remove a key completely, filter out every pair with that key, not just the first.

Misconception

Indexing from 1. Vector and string indexes start at 0, and the last valid index is the length minus 1. (vector-ref v (vector-length v)) is an error.

Exercises

Exercises

1. Association lists, vectors, strings and records

Warm-upComputational

What does this print?

(write (assv 3 '((1 . a) (3 . c) (3 . z))))

2. Association lists, vectors, strings and records

CoreComputational

What does this print?

(define env '((x . 1) (y . 2)))
(define env2 (cons '(x . 10) env))
(write (list (cdr (assq 'x env2)) (cdr (assq 'x env))))

3. Association lists, vectors, strings and records

Warm-upComputational

What is (vector-ref (vector-map (lambda (x) (* x x)) #(1 2 3 4)) 2)?

4. Association lists, vectors, strings and records

CoreComputational

With the lesson's primes vector #(2 3 5 7 11 13 17 19 23 29 31 37) and its binary-search, what does (binary-search primes 37) return?

5. Association lists, vectors, strings and records

CoreComputational

Using the lesson's split-on, what does (write (split-on #\- "2026-11-19")) print?

6. Association lists, vectors, strings and records

CoreComputational

Using the lesson's caesar, what does (write (caesar 1 "HAL")) print?

7. Association lists, vectors, strings and records

CoreHuman

Your alist maps country names (strings) to capitals. Which procedure should look up a country?

Choose one

8. Association lists, vectors, strings and records

CoreHuman

After (define-record-type point (make-point x y) point? (x point-x) (y point-y)), which statement is true?

Choose one

Further reading and resources