[Haskell-cafe] A systematic method for deriving a defintion of
foldl using foldr?
ryani.spam at gmail.com
Wed Mar 11 17:11:36 EDT 2009
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
More information about the Haskell-Cafe