I'm moving my blog and code over to GitHub. I like the way that lets me keep all my blog posts, essays, and code in a single versioned repository. It's also easier to author and edit. Please visit the new site.

Exercises 2.38 & 2.39: fold-left and fold-right

These exercises didn't take too long to complete, but I'm still not sure I understand the implications of it, so I'm going to work through it here.

The accumulate procedure in the text is the same as a Scheme procedure called fold-right. There's a similar procedure called fold-left that can be defined like this:

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

The first exercise has you work through some sample expressions to see how the two differ. Here are my expansions, using the substitution model we've been using in the text so far.

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


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

;; or:
(/ (/ (/ 1 1) 2) 3)

Just in case having the initial parameter the same as the first term of the list (i.e., the two 1's) is hiding an error, I'm going to do it again with my own list where every number is unique.

(fold-right / 1 (list 2 3 4))
(/ 2 (fold-right / 1 (list 3 4)))
(/ 2 (/ 3 (/ 4 (fold-right / 1 (list)))))
(/ 2 (/ 3 (/ 4 1)))
(/ 2 (/ 3 4))
(/ 2 3/4)
8/3


(fold-left / 1 (list 2 3 4))
(iter 1 (list 2 3 4))
(iter (/ 1 2) (list 3 4))
(iter 1/2 (list 3 44))
(iter (/ 1/2 3) (list 4))
(iter 1/6 (list 4))
(iter (/ 1/6 4) (list))
(iter 1/24 (list))
1/24

;; or:
(/ (/ (/ 1 2) 3) 4)

With infix notation I could describe these as:

(((1 ÷ 2) ÷ 3) ÷ 4) for fold-left and

(2 ÷ (3 ÷ (4 ÷ 1))) for fold-right.

For the mathematical operators above, fold-left conforms to what you would get if you were to work your way through the list from left to right with a calculator, as 1 ÷ 2 ÷ 3 ÷ 4 =.

Moving on to the list operator:

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

;;fold-left
(fold-left list nil (list 1 2 3))
(iter nil (list 1 2 3))
(iter (list nil 1) (list 2 3))
(iter (() 1) (list 2 3))
(iter (list (() 1) 2) (list 3))
(iter ((() 1) 2) (list 3))
(iter (list ((() 1) 2) 3) (list))
(iter (((() 1) 2) 3) (list))
(((() 1) 2) 3)
;; or:
(list (list (list nil 3) 2) 1)

fold-right seems clear as a recursive process. You take the first item from the list and apply the operator to it and the fold-right of the remainder of the list. One confusing thing is that the initial term provided to the procedure feels like a terminal term when I work through the substitution: it's the last thing the operator works on when it reaches the end of the list. It is, I suppose, the first thing the get evaluated in the chain of deferred recursive expressions.

I have a harder time describing fold-left. As noted above, it feels natural with mathematical operators and conforms to what I get from a calculator. As explained in this Stack Exchange question, these operators are left-associative, so fold-left feels natural. With other operators (like cons), fold-right starts feeling more natural. If your operator is commutative, like addition and multiplication, your result will be the same with either fold-left or fold-right.

Exercise 2.39 has you define reverse in terms of both fold-left and fold-right. First, fold-right:

Given a list (1 2 3), you need an operator (I'll call it op) such that

(op 1 (op 2 (op 3 nil)))

results in

(3 2 1)

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

For fold-left, you need an operator such that, given a list (1 2 3),

(op (op (op nil 3) 2) 1)

Evaluates to

(3 2 1)

(define (reverse sequence)
  (fold-left (lambda (x y) (cons y x)) nil sequence))

It was easiest to look at the innermost expression and figure out a way to build the term I want.

Working through these definitely helped my understanding, but it would take a lot more practice before either fold-left or fold-right feels natural, and before it's immediately obvious whether a left fold or right fold is the best fit for a given operation.

Sequences as Conventional Interfaces

map can be combined with other procedures accumulate and filter to build up a conventional way of dealing with sequenced data. Two examples from the text:

Example 1 This program takes a tree, goes through it to find all leaves containing an odd number, and squares those odd leaves, and adds the squares together.

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

Program 2 This procedure takes a number n and produces a list of even Fibonacci numbers equal to or less than Fib(n).

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

The programs don't seem to have a lot in common, but they can be understood like this:

Program 1
Enumerate tree leaves -> Filter odd leaves -> map square procedure -> Accumulate with +

Program 2
Enumerate integers -> map fib procdure -> filter even results -> accumulate with cons.

Seen this way you can abstact out the notions of filtering and accumulating, and the two actually look very similar.

To filter we can define

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

(filter odd? (list 1 2 3 4 5))
;Value: (1 3 5)

and to accumulate

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

(accumulate + 0 (list 1 2 3 4 5))
;Value: 15

(accumulate * 1 (list 1 2 3 4 5))
;Value: 120

(accumulate cons nil (list 1 2 3 4 5))
;Value: (1 2 3 4 5)

We can now define the above procedures in terms of map, filter, and accumulate.

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

(define (even-fibs n)
  (accumulate cons
              nil
              (filter even?
                      (map fib
                           (enumerate-interval 0 n)))))

Mapping Over Lists and Trees

The procedure map takes a procedure and a list, applies the procedure to each element of the list, and returns a list of the results. One way to define map could be

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

(map square (list 1 2 3 4))
;; (1 4 9)

You can also pass anonymous functions with lambda:

(map (lambda (x) (* x 2)) (list 1 2 3))
;Value 7: (2 4 6)

Then use this for more general procedures.

(define (scale-list items factor)
  (map (lambda (x) (* x factor))
       items))

(scale-list (list 1 2 3) 10)
;Value 8: (10 20 30)

You can use recursion to map over trees. Check for leaves as the terminating condition.

(define (scale-tree tree factor)
  (map (lambda (sub-tree)
         (if (pair? sub-tree)
             (scale-tree sub-tree factor)
             (* sub-tree factor)))
       tree))

(scale-tree (list 1 2 (list 4 5) 5) 10)

;Value 15: (10 20 (40 50) 50)

The built-in map is more general. If the procedure passed in takes multiple arguments, you can also supply multiple lists. The procedure is applied to all the first elements of the lists, then all the second elements of the list, and so on.

(map + (list 1 2 3 4) (list 10 20 30 40))
;Value 3: (11 22 33 44)

Exercise 2.30 Implement square-tree both directly and by using map and recursion.

;;Direct implementation
(define (square-tree tree)
  (cond ((null? tree) nil)
        ((not (pair? (car tree))) (cons (square (car tree))
                                        (square-tree (cdr tree))))
        (else (cons (square-tree (car tree))
                    (square-tree (cdr tree))))))

;;Using map
(define (square-tree tree)
  (map (lambda (x)
  (if (pair? x)
      (square-tree x)
      (square x)))
       tree))

The version using map is much shorter and easier to grok.

Exercise 2.31 Abstract previous exercise to use a procedure tree-map.

(define (tree-map proc tree)
  (map (lambda (x)
         (if (pair? x)
         (tree-map proc x)
         (proc x)))
   tree))

(define (square-tree tree) (tree-map square tree))

Return

I haven't posted in a while for a few reasons. One was that I needed to rest my brain after wrestling with the Church numerals exercise. When I came back to SICP, I worked through the "extended exercise" on interval arithmetic. I found that stupefyingly dull. Exercise 2.11 did me in. It involved building a complicated system of nested condition-checking. It reminded me of the CS courses I took in school that sapped my will to code. That's perhaps a bit harsh, but it did feel like a pedestrian exercise after the eye-opening new ideas that preceded it. So I bailed on the section and moved on to Section 2.2.

I also decided to take a different tack on my posts. If I cruise through an exercise without much difficulty, I'm not going to document it here. The Scheme Wiki has a good set of solutions if that's what you're looking for. Instead, I'm going to document the major points that I need to reiterate to fully digest, or any sections that I find difficult to grasp. I've worked through much of Chapter 2, so I should have more posts up. I need to review accumulation, folding, the picture language.

Exercise 2.6: Church Numerals

Exercise 2.6 Define one and two directly (not in terms of zero and add-1).

The exercise gives the following definitions of zero and add-1

(define zero (lambda (f) (lambda (x) x)))

(define (add-1 n)
  (lambda (f) (lambda (x) (f ((n f) x)))))

OK. Not that I understand how these represent zero and add-1, because trying to evaluate them just returns a procedure.

zero

;Value 22: #[compound-procedure 22 zero]

(add-1 zero)

;Value 23: #[compound-procedure 23]

Still, I'll play along. I'll use the substitution rules to figure out one and two.

(add-1 zero)
(lambda (f) (lambda (x) (f ((zero f) x))))
(lambda (f) (lambda (x) (f (lambda (x1) x1) x)))
(lambda (f) (lambda (x) (f x)))

(define one
  (lambda (f) (lambda (x) (f x)))

(add-1 one)
(lambda (f) (lambda (x) (f ((one f) x))))
(lambda (f) (lambda (x) (f ((lambda (x) f x) x))))
(lambda (f) (lambda (x) (f (f x))))

(define two
    (lambda (f) (lambda (x) (f (f x))))

At this point i can see a pattern emerge. I'm going to venture a guess that three would look like this:

(define three
    (lambda (f) (lambda (x) (f (f (f x)))))

So I don't really know what I did or how to verify whether its right. A little googling reveals a great page on this exercise by Bill the Lizard. And (surprise!) it looks like my substitutions above came out OK.

Reading over Bill's solution, I realize I forgot to define add. So I try not to look at Bill's solution, and work on my own. I do crib Bill's suggestion on how to test these numbers with inc.

So, I start looking at the pattern closer. I know that

(add zero one)

should result in

(lambda (f) (lambda (x) (f x)))

and that

(add one one)

should result in

(lambda (f) (lambda (x) (f (f x))))

And just to make sure I understand what's going on, I define add-2

(define (add-2 n)
  (lambda (f) (lambda (x) (f (f ((n f) x))))))

This seems to work based on my
inc test.

(((add-2 zero) inc) 0)

;Value: 2

I have a procedure to increase the value of a number. I need to generalize it so that I can increase it value of a number a b times. As it turns out, this "number" b is a procedure which repeats another procedure. So I'll just apply b to (a f) like this.

(define (add a b)
  (lambda (f)
    (lambda (x)
      (f ((b (a f)) x)))))

This look promising at first, but, until I get to adding two and two.

(((add zero one) inc) 0)

;Value: 1

(((add one one) inc) 0)

;Value: 2

(((add one two) inc) 0)

;Value: 3

(((add two two) inc) 0)

;Value: 5

(((add two zero) inc) 0)

;Value: 1

(((add two one) inc) 0)

;Value: 3

So I played around with it until my head hurt. In the end, I read the end of Bill's article. The final solution is this.

(define (add a b)
  (lambda (f)
    (lambda (x)
      ((b f) ((a f) x)))))

Now that I see it, it makes sense. I need b applications of f to ((a f) x), and the way to do this is with the procedure(b f), which will result in the application of procedure f b times. The repeated application of this procedure should be applied to ((a f) x).

Definitely one of the hardest problems I've encountered. I'll have to do some study on church numbers and come back to it.

Exercise 2.5: Yet another definition of cons, car, cdr

Exercise 2.5. Show that we can represent pairs of nonnegative integers using only numbers and arithmetic operations if we represent the pair a and b as the integer that is the product 2^a3^b. Give the corresponding definitions of the procedures cons, car, and cdr.

This is possible because any number 2ⁿ will not contain 3 as a factor. Similarly, any number 3ⁿ will not contain 2 as a factor.

cons is a straightforward application of what the exercise describes.

(define (cons3 a b)
  (* (expt 2 a) (expt 3 b)))

car and cdr just repeatedly divide by 2 (car) or 3 (cdr) until the number no longer divides evenly. Count the number of even divisions, and return the count as the result.

(define (cdr3 c)
  (define (helper x count)
    (if (= 0 (remainder x 3))
        (helper (/ x 3) (+ 1 count))
        count))
  (helper c 0))

(define (car3 c)
  (define (helper x count)
    (if (= 0 (remainder x 2))
        (helper (/ x 2) (+ 1 count))
        count))
  (helper c 0))

;;tests
(car3 (cons3 23 67))
;Value: 23

(cdr3 (cons3 23 67))
;Value: 67