[Haskell-cafe] A systematic method for deriving a defintion of
foldl using foldr?
Daniel Fischer
daniel.is.fischer at web.de
Wed Mar 11 15:09:36 EDT 2009
Am Mittwoch, 11. März 2009 19:24 schrieb R J:
> 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?
Implementation:
myfoldl f e xs = foldr (flip f) e (reverse xs)
Systematic approach:
Assume you have an implementation.
From considering simple cases, derive necessary conditions for the
implementation.
When the necessary conditions have narrowed the possibilities far enough down,
check which of the remaining possibilities solve the problem.
Here:
foldl f e === foldr g v . h
where h should be a simple polymorphic function on lists,
h :: [a] -> [a]
foldl f e [] = e,
foldr g v (h []) = if null (h []) then v else g (h []) v
since h should be generic, h [] can't be anything but [] or _|_, h [] = _|_
won't work with strict functions, so h [] = [] and v = e
foldl f e [x] = f e x,
foldr g e (h [x]) = if null (h [x]) then e else g (h [x]) e
h [x] = [] would break for many f, as would h [x] = _|_, so h [x] can only be
one of [x], [x,x], [x,x,x], ..., repeat x
If h [x] = [x], we have foldr g e (h [x]) = g x e, and we must have
forall x, e. f e x === g x e
, hence g = flip f.
If h [x] = [x,x] or [x,x,x] or ..., we would have to have
f e x == x `g` (x `g` (... e))
pick a few simple examples which don't allow that,
say f = (+), e = (0 :: Int), x = 1
f = (+), e = (1 :: Int), x = 1
foldl f e [x,y] = (e `f` x) `f` y
foldr (flip f) e (h [x,y]) = ?
foldr g e [u,v] = u `g` (v `g` e)
with g = flip f, that reduces to (e `f` v) `f` u,
so for [u,v] = [y,x] we have what we want, and our candidate is
foldl f e =?= foldr (flip f) e . reverse
The rest is tedious verification.
>
> 2. I believe that the reverse implementation--namely, implementing foldr
> in terms of foldl--is impossible. What's the proof of that?
foldr (++) [] (infinite list)
that delivers something (unless all lists inside the infinite list are empty),
but reverse (infinite list) never returns.
>
> 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.
>
Sorry, can't offer anything but practice.
More information about the Haskell-Cafe
mailing list