[Haskell-cafe] A systematic method for deriving a defintion of foldl using foldr?

wren ng thornton wren at freegeek.org
Sun Mar 15 01:50:34 EDT 2009

```R J wrote:
> 2.  I believe that the reverse implementation--namely, implementing
> foldr in terms of foldl--is impossible.  What's the proof of that?

As others have said, foldr in terms of foldl is impossible when infinite
lists are taken into account. For finite lists it's easy though:

(\f z xs -> foldl (\yz y -> yz . f y) id xs z)

> 3.  Any advice on how, aside from tons of practice, to develop the
> intuition for rapidly seeing solutions to questions like these would
> be much appreciated.  The difficulty a newbie faces in answering
> seemingly simple questions like these is quite discouraging.

The solutions to this problem, while "seemingly simple", is not so
simple that a newbie should get discouraged, IMO.

The essential trick here is to come up with the idea of using the fold
to build a function, which in turn actually does what you want--- rather
than trying to do anything "useful" with the fold itself. This idea
comes in two parts: implementation indirection (let another function do
the real work) and continuation-passing (to build the other function).
Both of those tricks are ones we use all the time, but the foldr/foldl
problem weds them together in a particularly perverse (though
deliciously elegant) manner.

In order to develop an intuition for the interplay of CPS and recursion,
consider this exercise: You have a type for binary trees and you have
this function for getting the size of a tree:

> size (Leaf _)     = 1
> size (Branch l r) = size l + size r

Unfortunately you have very deep trees and so this function gives
stack-overflow errors. Rewrite it to be tail recursive.

That one's not too hard because the order of recursion doesn't matter
(addition is associative and commutative). Now, you have a similar
function and you're worried about the fact that repeated list
concatenation can take O(n^2) time. Rewrite this one so it's tail
recursive--- making sure that the leaves still come out in the right
order. If you're familiar with the difference list trick[1] then also
rewrite it so you only take O(n) time building the list.

> toList (Leaf x)     = [x]
> toList (Branch l r) = toList l ++ toList r