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.
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 (:), (++), (&&), (||) ...
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
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 Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
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).
On Mon, Nov 21, 2011 at 4:44 AM, Jerzy Karczmarczuk
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.
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
On Tue, Nov 22, 2011 at 5:04 AM, Jerzy Karczmarczuk
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.
On Tue, Nov 22, 2011 at 09:10, David Fox
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 allbery.b@gmail.com wandering unix systems administrator (available) (412) 475-9364 vm/sms
participants (6)
-
Brandon Allbery -
Daniel Fischer -
David Fox -
Jerzy Karczmarczuk -
wren ng thornton -
Yves Parès