On Wednesday 11 March 2009 2:24:55 pm R J wrote:
foldl and foldr are defined as follows:
foldr :: (a -> b -> b) -> b -> [a] -> b foldr f e [] = e foldr f e (x : xs) = f x (foldr f e xs)
foldl :: (b -> a -> b) -> b -> [a] -> b foldl f e [] = e foldl f e (x : xs) = foldl f (f e x) xs
1. I understand how these definitions work, and yet I'm unable to implement foldl in terms of foldr. What's a systematic approach to identifying such an implementation, and what is the implementation?
This is a bit tricky, because although the base cases of the two line up, the inductive cases do not. When that sort of thing happens, and you can't find a tweaking of the function that brings it into line with foldr, what one has to do is to start looking for definitions like: foldl'aux [] = e'aux foldl'aux (x:xs) = g x (foldl'aux xs) where you can get foldl from foldl'aux by applying some post-processing. In this case, you might fool around with foldl a bit: foldl f e [] = id e foldl f e (x:xs) = (\e -> foldl f (f e x) xs) e Noticing this, we might try factoring out the 'e' parameter, and building a function to apply it to... foldl' f [] = id foldl' f (x:xs) = \e -> foldl' f xs (f e x) = (\x e -> foldl' f xs (f e x)) x = (\x k e -> k (f e x)) x (foldl' f xs) And now this is in the correct form for implementation with foldr: foldl' f = foldr (\x k e -> k (f e x)) id And: foldl f e l = foldl' f l e = foldr (\x k e -> k (f e x)) id l e
2. I believe that the reverse implementation--namely, implementing foldr in terms of foldl--is impossible. What's the proof of that?
This isn't a proof, but "foldl f z l" is bottom when l is an infinite list, regardless of f and z, whereas foldr works fine on infinite lists. This is at least a clue that implementing foldr in terms of foldl is a problem. Note that foldr *can* be implemented with foldl if you restrict yourself to finite lists. The definition is similar to the reverse.
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.
I recommend the paper Adrian Neumann linked to. :) -- Dan