[Haskell-cafe] A systematic method for deriving a defintion of foldl using foldr?
R J
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?
2. I believe that the reverse implementation--namely, implementing foldr in terms of foldl--is impossible. What's the proof of that?
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.
Express your personality in color! Preview and select themes for Hotmail®. See how.
Adrian Neumann
http://www.cs.nott.ac.uk/~gmh/fold.pdf
Am 11.03.2009 um 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?
>
> 2. I believe that the reverse implementation--namely, implementing
> foldr in terms of foldl--is impossible. What's the proof of that?
>
> 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.
>
> Express your personality in color! Preview and select themes for
> Hotmail®. See how.
> _______________________________________________
> Haskell-Cafe mailing list
> Haskel...@haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
Max Rabkin
> 2. I believe that the reverse implementation--namely, implementing foldr in
> terms of foldl--is impossible. What's the proof of that?
That's correct. Consider their behaviour on infinite lists.
--Max
Dan Doel
> 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
Daniel Fischer
> 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.
Ryan Ingram
> 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
Henning Thielemann
On Wed, 11 Mar 2009, 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?
You are lucky, I recently wrote
http://haskell.org/haskellwiki/Foldl_as_foldr
wren ng thornton
> 2. I believe that the reverse implementation--namely, implementing
> foldr in terms of foldl--is impossible. What's the proof of that?
As others have said, foldr in terms of foldl is impossible when infinite
lists are taken into account. For finite lists it's easy though:
(\f z xs -> foldl (\yz y -> yz . f y) id xs z)
> 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.
The solutions to this problem, while "seemingly simple", is not so
simple that a newbie should get discouraged, IMO.
The essential trick here is to come up with the idea of using the fold
to build a function, which in turn actually does what you want--- rather
than trying to do anything "useful" with the fold itself. This idea
comes in two parts: implementation indirection (let another function do
the real work) and continuation-passing (to build the other function).
Both of those tricks are ones we use all the time, but the foldr/foldl
problem weds them together in a particularly perverse (though
deliciously elegant) manner.
In order to develop an intuition for the interplay of CPS and recursion,
consider this exercise: You have a type for binary trees and you have
this function for getting the size of a tree:
> size (Leaf _) = 1
> size (Branch l r) = size l + size r
Unfortunately you have very deep trees and so this function gives
stack-overflow errors. Rewrite it to be tail recursive.
That one's not too hard because the order of recursion doesn't matter
(addition is associative and commutative). Now, you have a similar
function and you're worried about the fact that repeated list
concatenation can take O(n^2) time. Rewrite this one so it's tail
recursive--- making sure that the leaves still come out in the right
order. If you're familiar with the difference list trick[1] then also
rewrite it so you only take O(n) time building the list.
> toList (Leaf x) = [x]
> toList (Branch l r) = toList l ++ toList r
[1] See http://hackage.haskell.org/cgi-bin/hackage-scripts/package/dlist
or look at the ShowS type used in the Prelude for the shows function.
--
Live well,
~wren