The closure property of cons: the result of combining things can itself be combined. Pairs of pairs build lists and trees. map, filter, accumulate are the universal interfaces for sequence operations — once you have them, you stop writing loops and start describing pipelines.
Sequences as lists
A list is a chain of pairs. (list 1 2 3) builds (cons 1 (cons 2 (cons 3 '()))). car takes the first element, cdr takes the rest. map applies a function to every element, producing a new list with the same structure.
Scheme
; Building and traversing lists
(define xs (list 12345))
(display "list: ") (display xs) (newline)
(display "car: ") (display (car xs)) (newline)
(display "cdr: ") (display (cdr xs)) (newline)
(display "cadr: ") (display (cadr xs)) (newline)
; length โ count elements
(define (length items)
(if (null? items) 0
(+ 1 (length (cdr items)))))
(display "length: ") (display (length xs)) (newline)
; map โ apply f to every element
(define (my-map f items)
(if (null? items) '()
(cons (f (car items))
(my-map f (cdr items)))))
(display "map square: ")
(display (my-map (lambda (x) (* x x)) xs))
Python
# Building and traversing lists
xs = [1, 2, 3, 4, 5]
print(f"list: {xs}")
print(f"first: {xs[0]}")
print(f"rest: {xs[1:]}")
print(f"second: {xs[1]}")
print(f"length: {len(xs)}")
# map โ apply f to every elementprint(f"map square: {[x*x for x in xs]}")
Hierarchical structures
When list elements are themselves lists, you get a tree. count-leaves recursively walks both the car and cdr of each pair. This is where the closure property pays off: the same operations that work on flat lists work on nested structures.
Scheme
; Trees as nested lists
(define tree (list (list 12) (list 3 (list 45))))
(display "tree: ") (display tree) (newline)
; count-leaves: walk both branches
(define (count-leaves t)
(cond ((null? t) 0)
((not (pair? t)) 1)
(else (+ (count-leaves (car t))
(count-leaves (cdr t))))))
(display "leaves: ") (display (count-leaves tree)) (newline)
; scale-tree: multiply every leaf by a factor
(define (scale-tree t factor)
(cond ((null? t) '())
((not (pair? t)) (* t factor))
(else (cons (scale-tree (car t) factor)
(scale-tree (cdr t) factor)))))
(display "scale by 10: ")
(display (scale-tree tree 10))
Python
# Trees as nested lists
tree = [[1, 2], [3, [4, 5]]]
print(f"tree: {tree}")
# count_leaves: walk both branchesdef count_leaves(t):
if t == []:
return0ifnotisinstance(t, list):
return1returnsum(count_leaves(x) for x in t)
print(f"leaves: {count_leaves(tree)}")
# scale_tree: multiply every leafdef scale_tree(t, factor):
ifnotisinstance(t, list):
return t * factor
return [scale_tree(x, factor) for x in t]
print(f"scale by 10: {scale_tree(tree, 10)}")
Sequence operations
filter keeps elements that satisfy a predicate. accumulate (fold) combines elements with an operation. Together with map, they form a signal-processing pipeline: enumerate, then map, then filter, then accumulate. No explicit loops.
Scheme
; filter โ keep elements where predicate is true
(define (my-filter pred items)
(cond ((null? items) '())
((pred (car items))
(cons (car items) (my-filter pred (cdr items))))
(else (my-filter pred (cdr items)))))
; accumulate (fold-right) โ combine with op
(define (accumulate op init items)
(if (null? items) init
(op (car items)
(accumulate op init (cdr items)))))
(define xs (list 12345678910))
(display "evens: ")
(display (my-filter even? xs)) (newline)
(display "sum: ")
(display (accumulate + 0 xs)) (newline)
(display "product of odds: ")
(display (accumulate * 1 (my-filter odd? xs))) (newline)
; Pipeline: sum of squares of odd numbers
(define (square x) (* x x))
(display "sum of odd squares: ")
(display (accumulate + 0
(map square (my-filter odd? xs))))
Python
fromfunctoolsimport reduce
xs = list(range(1, 11))
# filter
evens = [x for x in xs if x % 2 == 0]
print(f"evens: {evens}")
# accumulate (reduce)print(f"sum: {reduce(lambda a, b: a+b, xs, 0)}")
odds = [x for x in xs if x % 2 == 1]
print(f"product of odds: {reduce(lambda a, b: a*b, odds, 1)}")
# Pipeline: sum of squares of odd numbersprint(f"sum of odd squares: {sum(x*x for x in xs if x % 2 == 1)}")
Nested mappings
flatmap maps a function that returns a list over a list, then flattens the results into a single list. It replaces nested loops. Here it generates all ordered pairs (i, j) where 1 ≤ j < i ≤ n and their sum is prime.
Scheme
; flatmap = append all results of mapping
(define (accumulate op init items)
(if (null? items) init
(op (car items) (accumulate op init (cdr items)))))
(define (flatmap f items)
(accumulate append '() (map f items)))
; enumerate integers from low to high
(define (enumerate-interval low high)
(if (> low high) '()
(cons low (enumerate-interval (+ low 1) high))))
; All pairs (i,j) with 1 <= j < i <= n
(define (unique-pairs n)
(flatmap (lambda (i)
(map (lambda (j) (list i j))
(enumerate-interval 1 (- i 1))))
(enumerate-interval 1 n)))
(display "pairs up to 5: ")
(display (unique-pairs 5)) (newline)
; Filter to pairs whose sum is prime
(define (divides? a b) (= (remainder b a) 0))
(define (smallest-divisor n)
(define (find d)
(cond ((> (* d d) n) n)
((divides? d n) d)
(else (find (+ d 1)))))
(find 2))
(define (prime? n) (and (> n 1) (= (smallest-divisor n) n)))
(define (prime-sum-pairs n)
(map (lambda (p) (list (car p) (cadr p) (+ (car p) (cadr p))))
(filter (lambda (p) (prime? (+ (car p) (cadr p))))
(unique-pairs n))))
(display "prime-sum pairs up to 6: ")
(display (prime-sum-pairs 6))
Python
frommathimport isqrt
def is_prime(n):
if n < 2: returnFalsefor d inrange(2, isqrt(n) + 1):
if n % d == 0: returnFalsereturnTrue# Nested mapping: all pairs (i,j) with j < idef unique_pairs(n):
return [(i, j) for i inrange(1, n+1) for j inrange(1, i)]
print(f"pairs up to 5: {unique_pairs(5)}")
# Filter to pairs whose sum is primedef prime_sum_pairs(n):
return [(i, j, i+j) for i, j in unique_pairs(n) if is_prime(i+j)]
print(f"prime-sum pairs up to 6: {prime_sum_pairs(6)}")
Notation reference
Scheme
Python
Meaning
(list 1 2 3)
[1, 2, 3]
Construct a list
(cons x xs)
[x] + xs
Prepend element
(car xs)
xs[0]
First element
(cdr xs)
xs[1:]
All but first
(map f xs)
[f(x) for x in xs]
Apply f to each element
(filter pred xs)
[x for x in xs if pred(x)]
Keep elements satisfying predicate
(accumulate op init xs)
functools.reduce(op, xs, init)
Fold right with initial value
(flatmap f xs)
[y for x in xs for y in f(x)]
Map then flatten
Translation notes
Scheme's accumulate is a right fold: it processes the last element first. Python's reduce is a left fold. For associative operations (addition, multiplication) they give the same result. For non-associative ones (subtraction, cons) they differ. The SICP convention uses right fold because it mirrors the recursive structure of lists: process the head, then recurse on the tail.
Python's list comprehensions do the work of map, filter, and flatmap in a single syntax. The Scheme decomposition is more explicit about the pipeline stages, which matters when you start composing them programmatically.
Neighbors
SICP chapters
๐ช Chapter 4 โ Data Abstraction (cons, car, cdr introduced)
๐ช Chapter 6 โ Symbolic Data (quotation enables data as code)
Cons โ the pair primitive underlying all Lisp data structures