A systematic method for deriving a defintion of foldl using foldr?
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®. http://www.windowslive-hotmail.com/LearnMore/personalize.aspx?ocid=TXT_MSGTX...
Read this excellent paper: 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 Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
On Wednesday 11 March 2009 2:24:55 pm 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?
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
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.
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
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
R J wrote:
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
participants (8)
-
Adrian Neumann -
Dan Doel -
Daniel Fischer -
Henning Thielemann -
Max Rabkin -
R J -
Ryan Ingram -
wren ng thornton