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.
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.
(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)(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 whylookuptakes thecdronly after checking. - Choose the procedure by key type:
assqfor symbols,assvfor numbers and characters,assocfor strings and lists. - Functional update: consing a new pair onto the front shadows the old one, because lookups stop at the first match.
updatedsees the new value;capitalsis 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-wordsbuilds an alist of word counts. It updates counts in place withset-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 . For a dozen keys that is faster than anything fancier; for thousands, use a hash table (below).
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.
(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)#(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-vectorcreates a vector of a given length filled with a value;vectorbuilds 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-mapandvector-for-eachmirrormapandfor-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
#ffor 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:
(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) ; => oWhy 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:
(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.
Characters and strings
(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)(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,#\spaceor#\newline; a string is a sequence of characters.string-reftakes an index,substringa start and an end. - Case conversion and character classification (
char-alphabetic?,char-numeric?) live in(scheme char)and follow Unicode rules. string->numberparses any number Scheme can read, including the rational3/4, and returns#ffor text that is not a number, a convenient test.number->stringtakes an optional radix.- Compare strings with
string=?(orequal?), never witheq?.string<?and friends compare alphabetically by code point. - R7RS-small has no string-splitting procedure, so
split-onconverts 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-mapand 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,displayandwrite-stringall accept a port as an extra argument, andget-output-stringreturns everything written so far. It is the standard way to build a string from many pieces.
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.
(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)(#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.
Choosing a structure
| Structure | Lookup | Add | Grows? | Best for |
|---|---|---|---|---|
| list | by position | at front | yes | sequences processed front to back, recursion, sharing |
| alist | by key | at front | yes | small maps, environments, functional update |
| vector | by index | no (copy to resize) | no | tables, grids, binary search, counting by index |
| string | by index (often ) | no (copy) | no | text |
| record | by field | no | no | entities with named fields |
| hash table | by key, on average | on average | yes | large 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:
(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) ; => #fThe 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.
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 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
1. Association lists, vectors, strings and records
Warm-upComputationalWhat does this print?
(write (assv 3 '((1 . a) (3 . c) (3 . z))))
2. Association lists, vectors, strings and records
CoreComputationalWhat 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-upComputationalWhat is (vector-ref (vector-map (lambda (x) (* x x)) #(1 2 3 4)) 2)?
4. Association lists, vectors, strings and records
CoreComputationalWith 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
CoreComputationalUsing the lesson's split-on, what does (write (split-on #\- "2026-11-19")) print?
6. Association lists, vectors, strings and records
CoreComputationalUsing the lesson's caesar, what does (write (caesar 1 "HAL")) print?
7. Association lists, vectors, strings and records
CoreHumanYour alist maps country names (strings) to capitals. Which procedure should look up a country?
8. Association lists, vectors, strings and records
CoreHumanAfter (define-record-type point (make-point x y) point? (x point-x) (y point-y)), which statement is true?
Further reading and resources
- R7RS-small, sections 6.4 to 6.8Pairs and lists (including association lists), symbols, characters, strings and vectors.
- R7RS-small, section 5.5: Record-type definitionsThe define-record-type form, adopted from SRFI 9.
- SRFI 69: Basic hash tablesA widely implemented hash table library.
- SRFI 125: Intermediate hash tablesThe newer hash table interface chosen for R7RS-large.