A list is a chain and a convention.
Pairs become sequences when a program agrees that each car holds one item and each cdr holds the rest of the list.
How do recursive procedures follow the shape of a list?
- Read a list as first item plus remaining sequence
- Identify the empty-list base case
- Build a new list without mutating the inputs
- Compare linked and indexed sequence access
length asks whether any sequence remains. Each nonempty pair contributes one and leaves the cdr for the smaller problem. The empty list stops the recursion.
append follows the same shape while rebuilding the left sequence. Its final cdr points to the right sequence, so the result preserves the order of both inputs.
A vector uses an indexed sequence convention. vector-ref selects an item by position, while vector-set! changes one position without rebuilding the whole vector.
(begin
(define (length items)
(if (null? items)
0
(+ 1 (length (cdr items)))))
(define (append left right)
(if (null? left)
right
(cons (car left) (append (cdr left) right))))
(list (length '(a b c d))
(append '(a b) '(c d))))- Output
- —
- Value
- —
- Diagnostic
- —
The first program returns (4 (a b c d)).
Watch cdr shorten the active problem. append creates one new pair per item in the left input and then reaches the right input. In the vector example, locate the update and later read at index 2.
Change the program before you read the hint.
Define reverse using a helper that carries the result built so far. Test it with the list (a b c d).
Show one hint
Move the car of the remaining input onto the front of an accumulator.