[Haskell-cafe] A systematic method for deriving a defintion of
foldl using foldr?
Dan Doel
dan.doel at gmail.com
Wed Mar 11 15:02:29 EDT 2009
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
More information about the Haskell-Cafe
mailing list