2009/3/11 R J
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