foldl vs foldl'

newer
How to getCh on MS Windows command...

older
Announce: Reactive library (FRP)...

Daryoush Mehrtash

4 Nov 2008 4 Nov '08

6:08 p.m.

Are there cases (function or list) where the result of foldl (or foldr)would be different that foldl' (or foldr')? thanks, daryoush

Attachments:

attachment.html (text/html — 174 bytes)

Show replies by date

Achim Schneider

4 Nov 4 Nov

6:31 p.m.

"Daryoush Mehrtash" wrote:

...

Are there cases (function or list) where the result of foldl (or foldr)would be different that foldl' (or foldr')?

Yes, in two cases folds can differ: a) You've got an infinite list, in which case you don't want to go to the end of it before starting to return values b) You don't have infinite memory and thus need things to be strict (or just don't want to pay the overhead of allocating millions of thunks for no good reason whatsoever, in case you're lucky enough to have enough memory for your data) -- (c) this sig last receiving data processing entity. Inspect headers for copyright history. All rights reserved. Copying, hiring, renting, performance and/or quoting of this signature prohibited.

Derek Elkins

6:33 p.m.

On Tue, 2008-11-04 at 15:08 -0800, Daryoush Mehrtash wrote:

...

Are there cases (function or list) where the result of foldl (or foldr)would be different that foldl' (or foldr')?

There is no foldr'. And yes, foldl and foldl' are different functions and thus return different results on some inputs; however, you almost always want foldl' (v. foldl). See http://www.haskell.org/haskellwiki/Stack_overflow

Daniel Fischer

6:37 p.m.

Am Mittwoch, 5. November 2008 00:08 schrieb Daryoush Mehrtash:

...

Are there cases (function or list) where the result of foldl (or foldr)would be different that foldl' (or foldr')?

thanks,

daryoush

Simple example: import Data.List weird :: Int -> Int -> Int weird _ 0 = 0 weird x y = x*y list :: [Int] list = [1, 2, 3, 4, undefined, 6, 7, 8, 9, 0] okey = foldl weird 1 list boom = foldl' weird 1 list *Main> okey 0 *Main> boom *** Exception: Prelude.undefined since foldl' evaluates strictly (to WHNF), it can die on encountering an undefined value in the list where foldl doesn't.

Nicolas Pouillard

5 Nov 5 Nov

8:10 a.m.

Excerpts from daniel.is.fischer's message of Wed Nov 05 00:37:47 +0100 2008:

...

Am Mittwoch, 5. November 2008 00:08 schrieb Daryoush Mehrtash:

...
Are there cases (function or list) where the result of foldl (or foldr)would be different that foldl' (or foldr')?

thanks,

daryoush

Simple example: import Data.List

weird :: Int -> Int -> Int weird _ 0 = 0 weird x y = x*y

list :: [Int] list = [1, 2, 3, 4, undefined, 6, 7, 8, 9, 0]

okey = foldl weird 1 list

boom = foldl' weird 1 list

*Main> okey 0 *Main> boom *** Exception: Prelude.undefined

since foldl' evaluates strictly (to WHNF), it can die on encountering an undefined value in the list where foldl doesn't.

Your example is a nice example of foldl over foldl', it would be nice to have it in the wiki page about the different folds[1]. Best regards, [1]: http://haskell.org/haskellwiki/Foldr_Foldl_Foldl%27 -- Nicolas Pouillard aka Ertai

Daryoush Mehrtash

1:01 p.m.

Lets assume we don't have undefined in the list, are there functions (or properties in the function) that would cause foldl to have different results than foldl'? daryoush On Tue, Nov 4, 2008 at 3:37 PM, Daniel Fischer wrote:

...

Am Mittwoch, 5. November 2008 00:08 schrieb Daryoush Mehrtash:

...
Are there cases (function or list) where the result of foldl (or foldr)would be different that foldl' (or foldr')?

thanks,

daryoush

Simple example: import Data.List

weird :: Int -> Int -> Int weird _ 0 = 0 weird x y = x*y

list :: [Int] list = [1, 2, 3, 4, undefined, 6, 7, 8, 9, 0]

okey = foldl weird 1 list

boom = foldl' weird 1 list

*Main> okey 0 *Main> boom *** Exception: Prelude.undefined

since foldl' evaluates strictly (to WHNF), it can die on encountering an undefined value in the list where foldl doesn't.

Jonathan Cast

1:06 p.m.

On Wed, 2008-11-05 at 10:01 -0800, Daryoush Mehrtash wrote:

...

Lets assume we don't have undefined in the list, are there functions (or properties in the function) that would cause foldl to have different results than foldl'?

If the function is partial on some elements of the list. (3 /), for example, if the list contains 0. If f is total over the elements of the list (whether the elements of the list are partial or total) and f z /= _|_, then foldl' f z = foldl f z. jcc

Derek Elkins

5:48 p.m.

On Wed, 2008-11-05 at 10:01 -0800, Daryoush Mehrtash wrote:

...

Lets assume we don't have undefined in the list, are there functions (or properties in the function) that would cause foldl to have different results than foldl'?

The only difference in the definition of foldl and foldl' is a seq so it can only differ due to bottoms as far as semantics is concerned.

Achim Schneider

6 Nov 6 Nov

3:15 a.m.

Derek Elkins wrote:

...

On Wed, 2008-11-05 at 10:01 -0800, Daryoush Mehrtash wrote:

...
Lets assume we don't have undefined in the list, are there functions (or properties in the function) that would cause foldl to have different results than foldl'?

The only difference in the definition of foldl and foldl' is a seq so it can only differ due to bottoms as far as semantics is concerned.

Denotational semantics that is, isn't it? -- (c) this sig last receiving data processing entity. Inspect headers for copyright history. All rights reserved. Copying, hiring, renting, performance and/or quoting of this signature prohibited.

Bas van Dijk

4 Nov 4 Nov

6:43 p.m.

2008/11/5 Daryoush Mehrtash :

...

Are there cases (function or list) where the result of foldl (or foldr)would be different that foldl' (or foldr')?

Maybe this wiki article I wrote some time ago will answer your question: http://haskell.org/haskellwiki/Foldr_Foldl_Foldl' regards, Bas

Bas van Dijk

6:45 p.m.

On Wed, Nov 5, 2008 at 12:43 AM, Bas van Dijk wrote:

...

2008/11/5 Daryoush Mehrtash :

...
Are there cases (function or list) where the result of foldl (or foldr)would be different that foldl' (or foldr')?

Maybe this wiki article I wrote some time ago will answer your question:

http://haskell.org/haskellwiki/Foldr_Foldl_Foldl'

Oops that link should be: http://haskell.org/haskellwiki/Foldr_Foldl_Foldl%27

Simon Richard Clarkstone

9 Nov 9 Nov

7:24 p.m.

Bas van Dijk wrote:

...

On Wed, Nov 5, 2008 at 12:43 AM, Bas van Dijk wrote:

...
2008/11/5 Daryoush Mehrtash :

...
Are there cases (function or list) where the result of foldl (or foldr)would be different that foldl' (or foldr')? Maybe this wiki article I wrote some time ago will answer your question:

http://haskell.org/haskellwiki/Foldr_Foldl_Foldl'

Oops that link should be:

http://haskell.org/haskellwiki/Foldr_Foldl_Foldl%27

I have an idea for the foldl diagram. If you rotate the RHS 90deg clockwise, it slopes the same way as the original list, but the 'f's are still rotated sideways to signify which their inputs are. That makes the relationship between imperative accumulator loops and foldl a bit clearer to me, as well as the relationship between the list and the recursion structure. -- src/

6036

Age (days ago)

6042

Last active (days ago)

List overview

Download

11 comments

8 participants

participants (8)

Achim Schneider
Bas van Dijk
Daniel Fischer
Daryoush Mehrtash
Derek Elkins
Jonathan Cast
Nicolas Pouillard
Simon Richard Clarkstone

foldl vs foldl'

Daryoush Mehrtash

Achim Schneider

Derek Elkins

Daniel Fischer

Nicolas Pouillard

Daryoush Mehrtash

Jonathan Cast

Derek Elkins

Achim Schneider

Bas van Dijk

Bas van Dijk

Simon Richard Clarkstone

tags

participants (8)