SICP. 2.2.3
2023-05-17 Wed

Sequences as Conventional Interfaces

Data abstraction permits us to: i) design programs without dealing with details of data representation; ii) experiment with alternative representations. This section introduces another powerful design principle fro working with data structures: conventional interfaces.

The authors presents two procedures that, on the surface, seem very difference. However, they notice, when looking at them more carefully, one can see great similarity. The first one computes the sum of the squares of the odd leaves of a tree. The second one constructs a list of all the even Fibonacci numbers up to n.

(define (sum-odd-squares tree)
  (cond ((null? tree) 0)
        ((not (pair? tree))
         (if (odd? tree) (square tree) 0))
        (else (+ (sum-odd-squares
                  (car tree))
                 (sum-odd-squares
                  (cdr tree))))))

(define (even-fibs n)
  (define (next k)
    (if (> k n)
        nil
        (let ((f (fib k)))
          (if (even? f)
              (cons f (next (+ k 1)))
              (next (+ k 1))))))
  (next 0))

Although those two functions don't look very similar, at a certain level of abstraction, they are.

The first procedure:

enumerates the leaves of a tree;
filters them, selecting the odd ones;
squares each of the selected ones; and
accumulates the result using +, starting with 0.

The second procedure:

enumerates the integers from 0 to n;
computes the Fibonacci number for each integer;
filters them, selecting the even ones; and
accumulates the result using cons, starting with the empty list.

These processes can be described in terms of ``signals flowing through a cascade of stages''.

  +-------------+   +-------------+   +-------------+   +-------------+
  | enumerate:  |-->| filter:     |-->| map:        |-->| accumulate: |
  | tree leaves |   | odd?        |   | square      |   | +, 0        |
  +-------------+   +-------------+   +-------------+   +-------------+

  +-------------+   +-------------+   +-------------+   +-------------+
  | enumerate:  |-->| map:        |-->| filter:     |-->| accumulate: |
  | integers    |   | fib         |   | even?       |   | cons, ()    |
  +-------------+   +-------------+   +-------------+   +-------------+

(Figure from SICP Unofficial Texinfo Format version 2.neilvandyke4 (January 10, 2007))

However, our two procedures fail to exhbit the signal-flow structure just described. If they did show such a structure, then we would achieve greater conceptual clarity. The authors show how to do it. Filter, accumulate, (and enumerate-tree and even-fibs) are therefore introduced.

The key to organizing programs so as to more clearly reflect the signal-flow structure is to concentrate on the “signals” that flow from one stage in the process to the next. If we represent these signals as lists, then we can use list operations to implement the processing at each of the stages (p. 115)

The value of expressing programs as sequence operations is that this helps us make program designs that are modular, that is, designs that are constructed by combining relatively independent pieces. (p. 117)

(define (filter predicate sequence)
  (cond ((null? sequence) nil)
        ((predicate (car sequence))
         (cons (car sequence)
               (filter predicate 
                       (cdr sequence))))
        (else  (filter predicate 
                       (cdr sequence)))))

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

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

(define (enumerate-tree tree)
  (cond ((null? tree) nil)
        ((not (pair? tree)) (list tree))
        (else (append 
               (enumerate-tree (car tree))
               (enumerate-tree (cdr tree))))))

(define (sum-odd-squares tree)
  (accumulate 
   +
   0
   (map square
        (filter odd?
                (enumerate-tree tree)))))

(define (list-fib-squares n)
  (accumulate 
   cons
   nil
   (map square
        (map fib
             (enumerate-interval 0 n)))))

(define 
  (product-of-squares-of-odd-elements sequence)
  (accumulate 
   *
   1
   (map square (filter odd? sequence))))

Modular construction is a powerful strategy for controlling complexity in engineering design. (p. 117)

Sequences, implemented here as lists, serve as a conventional interface that permits us to combine processing modules. (p. 118)

The authors then present nested mappings as an example of extending ``the sequence paradigm to include many computation that are commonly expressed using nested loops''.

Exercise 2.33

Exercise:

Fill in the missing expressions to complete the following definitions of some basic list-manipulation operations as accumulations:

(define (map p sequence)
  (accumulate (lambda (x y) ⟨??⟩) 
              nil sequence))

(define (append seq1 seq2)
  (accumulate cons ⟨??⟩ ⟨??⟩))

(define (length sequence)
  (accumulate ⟨??⟩ 0 sequence))

Answer:

To warmup, here is how you can use accumulate to return the list itself:

(define (list-identity sequence)
  (accumulate (lambda (x y) (cons x y)) nil sequence))

Given list-identity, it's easy to write map:

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

Append:

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

Length:

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

Exercise 2.35

Exercise:

Redefine count-leaves from 2.2.2 as an accumulation:

(define (count-leaves t)
  (accumulate <??>
              <??>
              (map <??> <??>)))

Answer:

The following solution uses map to fringe each member of t which is a pair, producing a list of atoms and one-level-lists; then it uses accumulate to sum each member treated as a 1 if it's an atom or as the length of itself if it's a list.

(define (map proc items)
  (if (null? items)
      nil
      (cons (proc (car items))
            (map proc (cdr items)))))

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

(define (append list1 list2)
  (if (null? list1)
      list2
      (cons (car list1)
            (append (cdr list1)
                    list2))))
(define (fringe x)
  (cond ((null? x) nil)
        ((not (pair? x)) (list x))
        (else (append (fringe (car x))
                      (fringe (cdr x))))))

(define (length l)
  (if (null? l)
      0
      (+ 1 (length (cdr l)))))

(define (gp-length l)
  (if (not (pair? l))
      1
      (length l)))

(define (gp-count-leaves t)
  (accumulate (lambda (a b)
                (+ (gp-length a)
                   b))
              0
              (map fringe t)))

(gp-count-leaves '(1 (2) (((3 4 5)) 4)))

This above was my solution. I've been told another, better, solution:

(define (dean-count-leaves t)
  (accumulate +
              0
              (map
               (lambda (x) (if (pair? x)
                               (dean-count-leaves x)
                               1)) t)))

Exercise 2.36

Exercise:

The procedure accumulate-n is similar to accumulate except that it takes as its third argument a sequence of sequences, which are all assumed to have the same number of elements. It applies the designated accumulation procedure to combine all the first elements of the sequences, all the second elements of the sequences, and so on, and returns a sequence of the results. For instance, if s is a sequence containing four sequences, ((1 2 3) (4 5 6) (7 8 9) (10 11 12)), then the value of (accumulate-n + 0 s) should be the sequence (22 26 30). Fill in the missing expressions in the following definition of accumulate-n:
(define (accumulate-n op init seqs)
  (if (null? (car seqs))
      nil
      (cons (accumulate op init ⟨??⟩)
            (accumulate-n op init ⟨??⟩))))

Answer:

(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)))))

Exercise 2.38

Exercise:

The accumulate procedure is also known as fold-right, because it combines the first element of the sequence with the result of combining all the elements to the right. There is also a fold-left, which is similar to fold-right, except that it combines elements working in the opposite direction:
(define (fold-left op initial sequence)
  (define (iter result rest)
    (if (null? rest)
        result
        (iter (op result (car rest))
              (cdr rest))))
  (iter initial sequence))
What are the values of
(fold-right / 1 (list 1 2 3))
(fold-left  / 1 (list 1 2 3))
(fold-right list nil (list 1 2 3))
(fold-left  list nil (list 1 2 3))
Give a property that op should satisfy to guarantee that fold-right and fold-left will produce the same values for any sequence.

Answer:

(define (fold-right op initial sequence)
  (if (null? sequence)
      initial
      (op (car sequence)
          (fold-right op initial (cdr sequence)))))

(fold-right / 1 (list 1 2 3))
;; (/ 1 (/ 2 (/ 3 1)))

(fold-right list nil (list 1 2 3))
;; (list 1 (list 2 (list 3 nil)))

(define (fold-left op initial sequence)
  (define (iter result rest)
    (if (null? rest)
        result
        (iter (op result (car rest))
              (cdr rest))))
  (iter initial sequence))

(fold-left / 1 (list 1 2 3))
(/ (/ (/ 1 1) 2) 3)

(fold-left list nil (list 1 2 3))
;; (list (list (list nil 1) 2) 3)

Exercise 2.39

Exercise:

Complete the following definitions of reverse (Exercise 2.18) in terms of fold-right and fold-left from Exercise 2.38:
(define (reverse sequence)
  (fold-right 
   (lambda (x y) ⟨??⟩) nil sequence))

(define (reverse sequence)
  (fold-left 
   (lambda (x y) ⟨??⟩) nil sequence))

Answer:

(define (reverse seq)
  (fold-right (lambda (x y) (append y (list x)))
              nil
              seq))

(define (reverse seq)
  (fold-left (lambda (x y) (append (list y) x))
             nil
             seq))

Exercise 2.40

Exercise:

Define a procedure unique-pairs that, given an integer n, generates the sequence of pairs (i,j) with \(1 \leq j < i \leq n\). Use unique-pairs to simplify the definition of prime-sum-pairs given above.

Answer:

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

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

Exercise 2.41

Exercise:

Write a procedure to find all ordered triples of distinct positive integers i, j, and k less than or equal to a given integer n that sum to a given integer s.

Answer:

We can:
- enumerate all ordered triples (see below how);
- filter them;
In order to enumerate all triples:
- for each element e, enumerate all the possible pairs from 1 to n without using e, and then adjoin e to the front of each pair.
In order to enumerate all possible pairs from 1 to n:
- for each element e of the range from 1 to n, enumerate all other elements of the range, and for each of those other elements create the list (e other-element).

(define (accumulate op initial seq)
  (if (null? seq)
      initial
      (op (car seq)
          (accumulate op initial (cdr seq)))))

(define (filter predicate seq)
  (cond ((null? seq) nil)
        ((predicate (car seq))
         (cons (car seq) (filter predicate (cdr seq))))
        (else (filter predicate (cdr seq)))))

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

(define (enumerate-interval-except low high not-allowed)
  (filter (lambda (x) (not (= x not-allowed)))
          (enumerate-interval low high)))

;; create a list of all possible pairs given a sequence
(define (all-pairs seq)
  (accumulate
   append
   nil
   (map (lambda (x)
          (map (lambda (y)
                 (cons x (list y)))
               (filter (lambda (e) (not (= e x))) seq)))
        seq)))

;; all triples from 1 to n
(define (all-triples n)
  (accumulate
   append
   nil
   (map (lambda (x)
          (map (lambda (y) (cons x y))
               (all-pairs (enumerate-interval-except 1 n x))))
        (enumerate-interval 1 n))))

(define (all-triples-sum n sum)
  (filter (lambda (x)
            (= (+ (car x)
                  (car (cdr x))
                  (car (cdr (cdr x))))
               sum))
          (all-triples n)))

(all-triples-sum 56 8)
;; => ((1 2 5) (1 3 4) (1 4 3) (1 5 2) (2 1 5) (2 5 1) (3 1 4) (3 4 1) (4 1 3) (4 3 1) (5 1 2) (5 2 1))

Exercise 2.42

Answer:

(define (filter pred seq)
  (cond ((null? seq) nil)
        ((pred (car seq)) (cons (car seq) (filter pred (cdr seq))))
        (else (filter pred (cdr seq)))))

(define (accumulate op initial seq)
  (if (null? seq)
      initial
      (op (car seq)
          (accumulate op initial (cdr seq)))))

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

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

(define (safe? k poss)
  (let ((queen (car (filter
                     (lambda (q)
                       (= (car (cdr q)) k))
                     poss))))
    (if (> (length
            (filter
             (lambda (p)
               (or (= (car queen)
                      (car p))
                   (= (- (car p) (car queen))
                      (- (car (cdr p)) (car (cdr queen))))
                   (= (- (car p) (car queen))
                      (- (car (cdr queen)) (car (cdr p))))))
             poss))
           1)
        #f
        #t)))

(define (adjoin-position nr k rq)
  (cons (list nr k) rq))

(define empty-board nil)

(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)
                   (adjoin-position new-row k rest-of-queens))
                 (enumerate-interval 1 board-size)))
          (queen-cols (- k 1))))))
  (queen-cols board-size))

←

SICP. 2.2.3 2023-05-17 Wed

Sequences as Conventional Interfaces

Exercise 2.33

Exercise 2.35

Exercise 2.36

Exercise 2.38

Exercise 2.39

Exercise 2.40

Exercise 2.41

Exercise 2.42

SICP. 2.2.3
2023-05-17 Wed