# SICP 2.2.3 Sequences as Conventional Interfaces

Published: 2020-07-23T18:21:19.000Z

Here we become skilled in list manipulation and build a set of useful subroutines.

## Exercise 2.33

``````(define (accumulate op initial sequence)
(if (null? sequence)
initial
(op (car sequence)
(accumulate op initial (cdr sequence)))))

(define (map p sequence)
(accumulate (lambda (x y) (cons (p x) y)) nil sequence))

(map (lambda (x) (+ 1 x)) (list 1 2 3))

(define (append seq1 seq2)
(accumulate cons seq2 seq1))

(append (list 1 2 3) (list 4 5))

(define (length sequence)
(accumulate (lambda (x y) (+ 1 y)) 0 sequence))``````

## Exercise 2.34

``````(define (horner-eval x coefficient-sequence)
(accumulate (lambda (this-coeff higher-terms) (+ this-coeff (* higher-terms x)))
0
coefficient-sequence))

(horner-eval 2 (list 1 3 0 5 0 1))
; 79``````

## Exercise 2.35

``````(define (identity x) x)

(define (count-leaves t)
) 0 (map identity t)))``````

Don't know why map is here...

## Exercise 2.36

``````(define (accumulate-n op init seqs)
(if (null? (car seqs))
nil
(cons (accumulate op init (map car seqs))
(accumulate-n op init (map cdr seqs)))))

(define s (list (list 1 2 3) (list 4 5 6) (list 7 8 9) (list 10 11 12)))
(accumulate-n + 0 s)``````

## Exercise 2.37

``````(define (dot-product v w)
(accumulate + 0 (map * v w)))

(define (matrix-*-vector m v)
(map (lambda (m-row) (dot-product m-row v)) m))

(matrix-*-vector (list (list 0 -1) (list 1 0)) (list 1 0))

(define (transpose mat)
(accumulate-n cons nil mat))

(define (matrix-*-matrix m n)
(let ((cols (transpose n)))
(map (lambda (m-row)
(map (lambda (n-col)
(dot-product m-row n-col)
)
cols
)
) m)))``````

## Exercise 2.38

I guess, if operation is commutative and associative, then it does not matter which fold to use, otherwise it matters.

## Exercise 2.39

``````(define (reverse sequence)
(fold-right (lambda (x y) (append y (list x))) nil sequence))
(define (reverse sequence)
(fold-left (lambda (x y) (cons y x)) nil sequence))``````

# Exercise 2.40

``````(define (enumerate-interval low high)
(if (> low high)
nil
(cons low (enumerate-interval (+ low 1) high))))

(define (flatmap proc seq)
(accumulate append nil (map proc seq)))

(define (unique-pairs n)
(flatmap (lambda (i)
(map (lambda (j) (list i j)) (enumerate-interval 1 (- i 1)))
) (enumerate-interval 2 n))
)
(unique-pairs 5)

(define (any l)
(if (null? l)
#f
(if (car l)
#t
(any (cdr l))
)
)
)
(define (prime? n)
(define (divisor? x) (= (remainder n x) 0))
(not (any (map divisor? (enumerate-interval 2 (truncate (/ n 2))))))
)
(define (test-prime)
(map (lambda (n) (list n (prime? n))) (enumerate-interval 1 20))
)
(test-prime)

(define (prime-sum-pairs n)
(define (prime-sum? pair)
(prime? (+ (car pair) (cadr pair))))

(define (make-pair-sum pair)

(map make-pair-sum
(filter prime-sum? (unique-pairs n))))
(prime-sum-pairs 6)``````

## Exercise 2.41

``````; 1 <= i < j < k <= n
; i + j + k = s
(define (triplets n s)
(define (build-triplet i j)
(let ((k (- s i j)))
(if (and (< j k) (<= k n))
(list i j k)
0
)
)
)
(flatmap (lambda (i)
(filter pair? (map (lambda (j)
(build-triplet i j)
) (enumerate-interval (+ i 1) (- n 1)))))
(enumerate-interval 1 (- n 2))
))
(triplets 4 6)``````

## Exercise 2.42

``````(define empty-board (list)) ; or nil
(cons new-row rest-of-queens)
)
; Check that predicate p(i, elem) is true at least for one of elements of list
(define (any p l)
(define (iter l i)
(if (null? l) #f
(if (p (car l) i)
#t
(iter (cdr l) (+ i 1))
)
)
)
(iter l 1)
)
(any = (list 3 2 1))
(any = (list 2 3 4))

(define (safe? k positions)
(let (
(row (car positions))
(d1 (+ (car positions) 1))
(d2 (- (car positions) 1))
)
(not (any (lambda (q i)
(or (= q row)
(= d1 (+ q i 1)) ; i should be increased by 1 because we are in cdr of board
(= d2 (- q i 1))
)
) (cdr positions)))
)
)
(safe? 0 (list 1 2))
(safe? 0 (list 1 1))
(safe? 0 (list 3 1 4 2))
(define (queens board-size)
(define (queen-cols k)
(if (= k 0)
(list empty-board)
(filter
(lambda (positions) (safe? k positions))
(flatmap
(lambda (rest-of-queens)
(map (lambda (new-row)
(enumerate-interval 1 board-size)))
(queen-cols (- k 1))))))
(trace queen-cols)
(queen-cols board-size))
(queens 6)

(define (display-board positions size)
(define (display-empty n)
(if (> n 0) (begin
(display " .")
(display-empty (- n 1))
))
)
(define (display-row q)
(display-empty (- q 1))
(display " Q")
(display-empty (- size q))
(newline)
)
(for-each display-row positions)
(newline)
)
(define (test-queens size)
(for-each
(lambda (b) (display-board b size))
(queens size)
)
)
(test-queens 6)

; Beautiful:
; . . . . Q .
; . . Q . . .
; Q . . . . .
; . . . . . Q
; . . . Q . .
; . Q . . . .
;
; . . . Q . .
; Q . . . . .
; . . . . Q .
; . Q . . . .
; . . . . . Q
; . . Q . . .
;
; . . Q . . .
; . . . . . Q
; . Q . . . .
; . . . . Q .
; Q . . . . .
; . . . Q . .
;
; . Q . . . .
; . . . Q . .
; . . . . . Q
; Q . . . . .
; . . Q . . .
; . . . . Q .``````

## Exercise 2.43

For size 0 basically running time is the same.

For size 1, we call `(quen-cols 0)` once, check position 1 and return, same for Louis.

For size 2, we call `(queen-cols 1)` once, check positions for next queen 1 and 2, and return. Louis calls (queen-cols 1) twice, because that is inside loop.

For size 3, we call `(queen-cols 2)` once, check positions 1, 2 and 3, and return. Louis calls `(queens-cols 2)` 3 times, each of which calls `(queens-cols 1)` 2 times.

So for us queens-cols is called `size` times, and for Louis `(factorial size)`. If our eight queens runs for time T, then his program will run 8!/8 T = 7! T = 5040T.