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

[Dan Doel]

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