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
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
