[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 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
 See http://hackage.haskell.org/cgi-bin/hackage-scripts/package/dlist
or look at the ShowS type used in the Prelude for the shows function.
More information about the Haskell-Cafe