# Decision procedure for foldr/foldl/foldl'?

 Classic List Threaded
9 messages
Reply | Threaded
Open this post in threaded view
|
Report Content as Inappropriate

## Decision procedure for foldr/foldl/foldl'?

 Does anyone have a quick way to decide which of the fold functions to use in a given situation?  There are times when I would like to find out which to use in the quickest way possible, rather than reading a long explanation of why each one behaves the way it does. _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|
Report Content as Inappropriate

## Re: Decision procedure for foldr/foldl/foldl'?

 On Sunday 20 November 2011, 17:28:43, David Fox wrote: > Does anyone have a quick way to decide which of the fold functions to > use in a given situation?  There are times when I would like to find > out which to use in the quickest way possible, rather than reading a > long explanation of why each one behaves the way it does. > - foldl: In the rare cases where you need this, you'll probably know (I'm not aware of any real-world case where foldl is the correct choice) Rule of thumb: Can the result be determined/constructed (at least partially) before the end of the list has been reached?[*] Then foldr. Otherwise foldl'. Exceptions to the rule may exist. [*] That typically means the folded function is lazy in its second argument, like (:), (++), (&&), (||) ... _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|
Report Content as Inappropriate

## Re: Decision procedure for foldr/foldl/foldl'?

 On 11/20/11 11:58 AM, Daniel Fischer wrote: > On Sunday 20 November 2011, 17:28:43, David Fox wrote: >> Does anyone have a quick way to decide which of the fold functions to >> use in a given situation?  There are times when I would like to find >> out which to use in the quickest way possible, rather than reading a >> long explanation of why each one behaves the way it does. >> > > - foldl: In the rare cases where you need this, you'll probably know (I'm > not aware of any real-world case where foldl is the correct choice) If your folding function is a constructor, then the result will already be in WHNF, therefore foldl' is doing extra work (checking for WHNF) that it doesn't need to. If your folding function is (.), the foldl variant is superior to foldl' because it avoids making a bunch of unnecessary intermediate functions/closures. Those are the only notable real-world examples I can recall. -- Live well, ~wren _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|
Report Content as Inappropriate

## Re: Decision procedure for foldr/foldl/foldl'?

 In reply to this post by David Fox-7 I would say a good practice with folds (and maybe in Haskell in general) is that either all be strict or all be lazy.In the expression: foldXX f init list: Remember that foldr does: x `f` ( ... the accumulator ... ) and foldl: (... the accumulator ...) `f` x The accumulator has to match a non-strict argument of f, so that f will be able to return results even if the accumulator is not fully evaluated.More detailed:if f is lazy in its second argument, then use foldr. Everything is lazy, you build a very small thunk since nothing is evaluated. In the rare cases where f is (also) lazy in its first argument, you can use foldl.And of course, if f is strict in both its arguments, then use foldl'. Everything is then strict, you build no thunk. 2011/11/20 David Fox Does anyone have a quick way to decide which of the fold functions to use in a given situation?  There are times when I would like to find out which to use in the quickest way possible, rather than reading a long explanation of why each one behaves the way it does. _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|
Report Content as Inappropriate

## Re: Decision procedure for foldr/foldl/foldl'?

 Yves Parès: if f is lazy in its second argument, then use foldr. Everything is lazy, you build a very small thunk since nothing is evaluated. In the rare cases where f is (also) lazy in its first argument, you can use foldl. ... I have the impression that this is not the most useful advice possible. 1. "Nothing is evaluated"?? Look, foldr is designed to consume incrementally the list argument, and to produce, also incrementally the result ; it may stop in the middle if f is lazy, but if you organize badly your program, you will pollute your memory. You might wish to process the whole of the list as fast as possible, and then foldr may be dangerous. You may build a veeery big thunk before its reduction. 2. This is not only the issue: "f x z" versus "f z x". foldl is iterative (tail-recursive) and the reduction proceeds until all the source list is consumed. foldl works better with strict functions, not lazy. (of course, unless I am mistaken...) == In general, sorry for the cynism, but when I read: "There are times when I would like to find out which to use in the quickest way possible, rather than reading a long explanation of why each one behaves the way it does" of David Fox, I compare it with a question of a young army officer, addressed to his elders: "Tell me how to win the war in the quickest way possible, rather than boring me with the explanations behind all those complicated strategies". Jerzy Karczmarczuk Caen, Normandy, France (William the Conqueror, who lived here, had a reputation of a strategist who tried to understand his enemies. 350 years later, the French didn't try to understand anything, they just wanted to win the battle of Azincourt as quick as possible). _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|
Report Content as Inappropriate

## Re: Decision procedure for foldr/foldl/foldl'?

 On Mon, Nov 21, 2011 at 4:44 AM, Jerzy Karczmarczuk <[hidden email]> wrote: > In general, sorry for the cynism, but when I read: > > "There are times when I would like to find out which to use in the quickest > way possible, rather than reading a long explanation of why each one behaves > the way it does" of David Fox, I compare it with a question of a young army > officer, addressed to his elders: > > "Tell me how to win the war in the quickest way possible, rather than boring > me with the explanations behind all those complicated strategies". I'm not trying to avoid learning the differences between the different folds, but I am looking for a mnemonic device that will allow me to proceed more quickly towards my goal.  My ultimate goal is to write software, not to understand folds.   Just as it is inappropriate for a young officer to even contemplate an overall strategy for winning the war, it would be inappropriate for a general to spend more time than necessary on the minute details of military tactics, as vital as they are. _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|
Report Content as Inappropriate

## Re: Decision procedure for foldr/foldl/foldl'?

 David Fox reacts to my criticism of his attitude towards "the meaning of folds": > I'm not trying to avoid learning the differences between the different > folds, but I am looking for a mnemonic device that will allow me to > proceed more quickly towards my goal.  My ultimate goal is to write > software, not to understand folds.   Just as it is inappropriate for a > young officer to even contemplate an overall strategy for winning the > war, it would be inappropriate for a general to spend more time than > necessary on the minute details of military tactics, as vital as they > are. David, cynism or not, you might have found in my post some concrete remarks, about incrementality, about tail-recursion... Not a single comment of your part. No comment addressed to other people who tried also to help you (whether we really help you in such a way is subject to discussion...) I am sorry, but saying that your goal is to write software is not even funny. The relatively modern science of programming evolves for the last 60 years, and the progress in writing software NEVER came out of kitchen recipes, on the contrary ! The laziness is not a "trick to avoid computation", but a methodology of ordering the operations, and if you are unable to order them in your head, you won't be able to exploit this or that "design pattern". OK, you gather some patterns, and you apply them. Once. And then, you will be helpless, when the need for refactoring arrives. You will never be able to teach those patterns to your younger colleagues. And finally, your last remarks might be less relevant than you wish. A general gets his stars usually after several years of demonstrating that he UNDERSTANDS the minute details of military tactics, so he can consciously choose those who will implement them. Jerzy Karczmarczuk _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|
Report Content as Inappropriate

## Re: Decision procedure for foldr/foldl/foldl'?

 On Tue, Nov 22, 2011 at 5:04 AM, Jerzy Karczmarczuk <[hidden email]> wrote: > David Fox reacts to my criticism of his attitude towards "the meaning of > folds": >> >> I'm not trying to avoid learning the differences between the different >> folds, but I am looking for a mnemonic device that will allow me to >> proceed more quickly towards my goal.  My ultimate goal is to write >> software, not to understand folds.   Just as it is inappropriate for a >> young officer to even contemplate an overall strategy for winning the >> war, it would be inappropriate for a general to spend more time than >> necessary on the minute details of military tactics, as vital as they >> are. > > David, cynism or not, you might have found in my post some concrete remarks, > about incrementality, about tail-recursion... Not a single comment of your > part. No comment addressed to other people who tried also to help you > (whether we really help you in such a way is subject to discussion...) > > I am sorry, but saying that your goal is to write software is not even > funny. The relatively modern science of programming evolves for the last 60 > years, and the progress in writing software NEVER came out of kitchen > recipes, on the contrary ! The laziness is not a "trick to avoid > computation", but a methodology of ordering the operations, and if you are > unable to order them in your head, you won't be able to exploit this or that > "design pattern". > OK, you gather some patterns, and you apply them. Once. And then, you will > be helpless, when the need for refactoring arrives. You will never be able > to teach those patterns to your younger colleagues. And finally, your last > remarks might be less relevant than you wish. A general gets his stars > usually after several years of demonstrating that he UNDERSTANDS the minute > details of military tactics, so he can consciously choose those who will > implement them. I think the other replies in this thread speak for themselves - i found them very helpful. _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|
Report Content as Inappropriate

## Re: Decision procedure for foldr/foldl/foldl'?

 On Tue, Nov 22, 2011 at 09:10, David Fox wrote: I think the other replies in this thread speak for themselves - i found them very helpful.That would be because they mostly back-doored around your stated intent. -- brandon s allbery                                      [hidden email] wandering unix systems administrator (available)     (412) 475-9364 vm/sms _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Loading...