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

[wren ng thornton]

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


[1] 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.

-- 
Live well,
~wren