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

[Ryan Ingram]

2009/3/11 R J <rj248842 at hotmail.com>:
> 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.

Don't be discouraged; this is far from a simple question.  I still
don't have an intuitive understanding of the "use functions"
definition of foldl-in-terms-of-foldr:

> foldl f z xs = foldr magic id xs z where
>    magic x k e = k (f e x)

"magic" just looks like a bunch of characters that somehow typechecks.
 This definition of "magic" is slightly more comprehensible to me:

>   magic x k = k . flip f x

The definition with reverse is easier to understand but seems less elegant:

> foldl f z xs = foldr (flip f) z (reverse xs)

But it does follow almost directly from these definitions for foldl
and foldr on finite lists:

foldr f z [x1, x2, x3, ..., xN] = x1 `f` (x2 `f` (x3 `f` ... (xN `f` z)...))
foldl f z [xN, ..., x3, x2, x1] = ((...(z `f` xN)... `f` x3) `f` x2) `f` x1

  -- ryan