Updated at Feb 1, 2017

My friend asked me an interesting problem related to SICP this day (I still don’t know if it is one of the exercises):

If you have the usual definition of fold-left, can you define the fold-right using fold-left? And vice versa?

The fold-left and fold-right mentioned appeared in SICP exercise 2.38.

The usual definitions of fold-left and fold-right:

(define (fold-left op intial seq)
    (if (null? seq)
        (op (fold-left op intial (cdr seq)) (car seq))))

(define (fold-right op intial seq)
    (if (null? seq)
        (op (car seq) (fold-right op intial (cdr seq)))))

What is the problem?

I found that it has a very strong mathematical property, defined as below:

Assuming $a \in \mathbb A, b \in \mathbb B$, we define functions $opr, opl$ \(opr(a, b) = a' \in A\) \(opl(a, b) = b' \in B\)

and functions $opra, oprb, opla, oplb$ satisfying: \(opr(opra(a), oprb(a)) = a, \forall a \in \mathbb A\) \(opl(opla(b), oplb(b)) = b, \forall b \in \mathbb B\)

We call the function pair $opr, opl$ complementary.

In scheme, we have:

(define (opr a b) (append a (list b)))
(define (opl a b) (cons b a))
(define (opla a) (car a))
(define (oplb a) (cdr a))
(define (opra a) (get-seq-except-last-one a))
(define (oprb a) (get-last-one a))

(define (get-seq-except-last-one a)
    (if (null? (cdr a))
        (cons (car a) (get-seq-except-last-one (cdr a)))))

(define (get-last-one a)
    (if (null? (cdr a))
        (car a)
        (get-last-one (cdr a))))

How we solve the problem?

In SICP exercise 2.39, we can construct the reverse as:

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

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

You can see that in fold-right and fold-left, we use “complementary” functions as the first argument op.

So back to the question, how could we construct fold-left with fold-right and vice versa?

Assuming we have a find-com-op which returns the complementary function for us, then we can write:

(define (fold-left op initial seq)
    (fold-right (find-com-op op) initial seq))

(define (fold-right op initial seq)
    (fold-left (find-com-op op) initial seq))

Did we finish?

But, how could we find a function generator that will help us do such thing?

My friend actually saw this in Real World Haskell exercises, and one possible answer would be (in Haskell):

foldl2 f z xs = foldr (\x g a -> g (f a x)) id xs z

Similarly, we can define:

foldr2 f z xs = foldl (\g x a -> g (f x a)) id xs z


Some other interesting problems about fold in Haskell: