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)
intial
(op (fold-left op intial (cdr seq)) (car seq))))

(define (fold-right op intial seq)
(if (null? seq)
intial
(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))
nil
(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


## Update

Some other interesting problems about fold in Haskell: