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