# How to implement `foldr` with `foldl` and vice versa

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$

and functions $opra, oprb, opla, oplb$ satisfying:

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: