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