Decision procedure for foldr/foldl/foldl'?

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
9 messages Options
Reply | Threaded
Open this post in threaded view
|

Decision procedure for foldr/foldl/foldl'?

David Fox-7
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
|

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

Daniel Fischer
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
|

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

wren ng thornton
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
|

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

Yves Parès
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 <[hidden email]>
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
|

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

Jerzy Karczmarczuk
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
|

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

David Fox-7
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
|

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

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.

Jerzy Karczmarczuk




_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

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

David Fox-7
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
|

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

Brandon Allbery
On Tue, Nov 22, 2011 at 09:10, David Fox <[hidden email]> 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