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-left? And vice versa?
fold-right mentioned appeared in SICP exercise 2.38.
The usual definitions of
(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
(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-left, we use “complementary” functions as the first argument
So back to the question, how could we construct
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: