I'm super-confused here. It is claimed that the Haskell 98 Report requires List.minimumBy and List.maximumBy to be lazy, but the sample implementations given there use foldl1 ( https://www.haskell.org/onlinereport/list.html) and I can't find anyplace in the report where that's explicitly said to be wrong. What am I missing? On Thu, Oct 29, 2015 at 11:15 AM David Feuer wrote:

I think it would be very nice to offer a few folds tailored to specific strictness patterns. I'm not sure of the best interface, however. On Oct 29, 2015 2:07 PM, "Joachim Breitner" wrote:

...

Hi,

Am Donnerstag, den 29.10.2015, 17:34 +0200 schrieb Roman Cheplyaka:

...

I just realized (thanks to this reddit thread[1]) that minimumBy is now implemented through foldr1. Previously (before FTP), minimumBy from Data.List used foldl1, while minimumBy from Data.Foldable used foldr1.

I think that the way these were merged was a mistake.

this has also been raised by Neil at https://ghc.haskell.org/trac/ghc/ticket/10830

Also note https://ghc.haskell.org/trac/ghc/ticket/3416 where it is stated that the report demands minimum (and hence minimumBy) to be lazy.

Ignoring that argument, and that of not changing libraries light- harted, I do think that foldl1' would be the better choice here; users who rely on laziness here are likely in the minority and it would be reasonable to expect them to manually use foldl1 or foldr1.

BTW, why is there no fold' method in Foldable that leaves the associativity (left, right, or mixed in case of a tree) to the Foldable instance?

Greetings, Joachim

-- Joachim “nomeata” Breitner mail@joachim-breitner.de • http://www.joachim-breitner.de/ Jabber: nomeata@joachim-breitner.de • GPG-Key: 0xF0FBF51F Debian Developer: nomeata@debian.org

_______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

Oh, right: I missed the prime. Apologies for cluttering the discussion. On Thu, Oct 29, 2015 at 11:31 AM Sumit Sahrawat, Maths & Computing, IIT (BHU) wrote:

foldl1 is lazy, whereas foldl1' is strict. The primes are usually used to indicate strictness.

On 29 October 2015 at 23:59, Bart Massey wrote:

...

I'm super-confused here. It is claimed that the Haskell 98 Report requires List.minimumBy and List.maximumBy to be lazy, but the sample implementations given there use foldl1 ( https://www.haskell.org/onlinereport/list.html) and I can't find anyplace in the report where that's explicitly said to be wrong. What am I missing?

On Thu, Oct 29, 2015 at 11:15 AM David Feuer wrote:

...

I think it would be very nice to offer a few folds tailored to specific strictness patterns. I'm not sure of the best interface, however. On Oct 29, 2015 2:07 PM, "Joachim Breitner" wrote:

...

Hi,

Am Donnerstag, den 29.10.2015, 17:34 +0200 schrieb Roman Cheplyaka:

...

I just realized (thanks to this reddit thread[1]) that minimumBy is now implemented through foldr1. Previously (before FTP), minimumBy from Data.List used foldl1, while minimumBy from Data.Foldable used foldr1.

I think that the way these were merged was a mistake.

this has also been raised by Neil at https://ghc.haskell.org/trac/ghc/ticket/10830

Also note https://ghc.haskell.org/trac/ghc/ticket/3416 where it is stated that the report demands minimum (and hence minimumBy) to be lazy.

Ignoring that argument, and that of not changing libraries light- harted, I do think that foldl1' would be the better choice here; users who rely on laziness here are likely in the minority and it would be reasonable to expect them to manually use foldl1 or foldr1.

BTW, why is there no fold' method in Foldable that leaves the associativity (left, right, or mixed in case of a tree) to the Foldable instance?

Greetings, Joachim

-- Joachim “nomeata” Breitner mail@joachim-breitner.de • http://www.joachim-breitner.de/ Jabber: nomeata@joachim-breitner.de • GPG-Key: 0xF0FBF51F Debian Developer: nomeata@debian.org

_______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

-- Regards

Sumit Sahrawat

I'd definitely like a fold' , it'd have more laws / be more portable than the others, at least for associative computations. Would that be a strict version of fold map? On Sunday, February 7, 2016, Joachim Breitner wrote:

Dear List,

the following discussion stalled:

...

I just realized (thanks to this reddit thread[1]) that minimumBy is now implemented through foldr1. Previously (before FTP), minimumBy from Data.List used foldl1, while minimumBy from Data.Foldable used foldr1.

I think that the way these were merged was a mistake.

Let's admit that the absolute majority of use cases for minimumBy are numbers, for which the comparison functions are strict in both arguments. Even for something like Bool, where comparison could potentially be in one of the arguments, the standard compare method is derived and is strict.

Now, for Foldable, there isn't necesarily a connection between the

...

the way fold is performed. For example, for Data.Map.Map both folds are tail-recursive. Yet foldr is non-tail-recursive at least for:

- good old lists - anything that uses the same convention for foldl/foldr as lists - anything that defines its foldable instance through conversion to lists - anything that uses the default implementation of foldr/foldr1

I also put a simple microbenchmark[2] to show the difference in

Am Donnerstag, den 29.10.2015, 17:34 +0200 schrieb Roman Cheplyaka: direction and performance;

...

on it, the proposed implementation is more than 20x faster than the current one.

[1]: https://www.reddit.com/r/haskell/comments/3qpefo/a_very_unfortunate_error_me... [2]: http://lpaste.net/714261956202070016

see https://mail.haskell.org/pipermail/libraries/2015-October/026430.html and https://ghc.haskell.org/trac/ghc/ticket/10830.

It seems we have the choice of either 1 keeping this as they are, with Data.List.maximumBy having changed behaviour for the worse from 7.8 to 7.10 2 changing the behavior of Foldable.maximumBy (from foldr to foldl) and changing the behavior of Data.List.maximumBy back to what it was before, and arguably the “better” definition. 3 adding minimumBy/maximumBy as a class method and changing only the list instance.

This also raises the question of whether using foldl over foldl' is the right thing to do, as I was under the impression that foldl will (at least for lists) always just accumulate a large heap of thunks, and one would always want to use foldl' instead. I postulate that if foldl' had been in the report, then it would have been used for maximumBy.

So this yields option 4:

4 changing maximumBy to use foldl'

BTW, why is there no fold' method in Foldable that leaves the associativity (left, right, or mixed in case of a tree) to the Foldable instance, and just implements the “best” strictly accumulating fold for the given data structure?

Greetings, Joachim

-- Joachim “nomeata” Breitner mail@joachim-breitner.de javascript:; • http://www.joachim-breitner.de/ Jabber: nomeata@joachim-breitner.de javascript:; • GPG-Key: 0xF0FBF51F Debian Developer: nomeata@debian.org javascript:;

Hi, Am Mittwoch, den 10.02.2016, 20:07 +0000 schrieb Lana Black:

I tested maximumBy with foldl, and it runs in constant memory for lists, so extra strictness won't have any benefits in this particular case. The following snippet clearly shows it.

----- main = print $ maximumBy compare [1..100000000000]

-- Copied from Data.Foldable with foldl1 replacing foldr1. maximumBy :: Foldable t => (a -> a -> Ordering) -> t a -> a maximumBy cmp = foldl1 max'   where max' x y = case cmp x y of                           GT -> x                           _  -> y

Thanks for testing, but I’d be careful with small examples. It is not unlikely that GHC can “fully grasp” them and do wonders, possibly even fusing the lists, but with larger examples we’d get bad behavior. And indeed, with "-O0", or with NOINLINE maximumBy, I very quickly fill my memory. Too bad there is no foldl1' to easily verify that with that, we get the desired behavior even without -O. Now this gets interesting. I’m wondering if there is a good way of implementing foldl1', so I looked at the default implementation of foldl1, which is:     foldl1 :: (a -> a -> a) -> t a -> a     foldl1 f xs = fromMaybe (error "foldl1: empty structure")                     (foldl mf Nothing xs)       where         mf m y = Just (case m of                          Nothing -> y                          Just x  -> f x y) This implements foldl1 via foldl and an accumulator _wrapped in a Maybe and case-analized in every step_. I sincerely hope that every instance overrides this by an more efficient version. And at least those Foldable instances with more than one element in Data.Foldable do... Nevertheless, for the question of memory usage, a generic definition will do. And indeed, using foldl1' :: Foldable t => (a -> a -> a) -> t a -> a foldl1' f xs = fromMaybe (error "foldl1': empty structure")                 (foldl' mf Nothing xs)   where     mf Nothing y = Just y     mf (Just x) y = x `seq` Just (f x y) in your example, I get constant memory consumption as expected. Greetings, Joachim -- Joachim “nomeata” Breitner   mail@joachim-breitner.de • https://www.joachim-breitner.de/   XMPP: nomeata@joachim-breitner.de • OpenPGP-Key: 0xF0FBF51F   Debian Developer: nomeata@debian.org

The extra members that were added to the class weren't an exhaustive selection -- it is more that the proponents that were pushing them forward at the time stopped when they themselves got exhausted. Having the option for tree-based vs. foldl' based accumulation would give the best of both worlds in one respect: O(log n) time bounds for some containers, much better constants for others. The downside would be re-opening old wounds on the FTP front. -Edward On Sun, Feb 7, 2016 at 5:44 AM, Joachim Breitner wrote:

Dear List,

the following discussion stalled:

...

I just realized (thanks to this reddit thread[1]) that minimumBy is now implemented through foldr1. Previously (before FTP), minimumBy from Data.List used foldl1, while minimumBy from Data.Foldable used foldr1.

I think that the way these were merged was a mistake.

Let's admit that the absolute majority of use cases for minimumBy are numbers, for which the comparison functions are strict in both arguments. Even for something like Bool, where comparison could potentially be in one of the arguments, the standard compare method is derived and is strict.

Now, for Foldable, there isn't necesarily a connection between the

...

the way fold is performed. For example, for Data.Map.Map both folds are tail-recursive. Yet foldr is non-tail-recursive at least for:

- good old lists - anything that uses the same convention for foldl/foldr as lists - anything that defines its foldable instance through conversion to lists - anything that uses the default implementation of foldr/foldr1

I also put a simple microbenchmark[2] to show the difference in

Am Donnerstag, den 29.10.2015, 17:34 +0200 schrieb Roman Cheplyaka: direction and performance;

...

on it, the proposed implementation is more than 20x faster than the current one.

[1]: https://www.reddit.com/r/haskell/comments/3qpefo/a_very_unfortunate_error_me... [2]: http://lpaste.net/714261956202070016

see https://mail.haskell.org/pipermail/libraries/2015-October/026430.html and https://ghc.haskell.org/trac/ghc/ticket/10830.

It seems we have the choice of either 1 keeping this as they are, with Data.List.maximumBy having changed behaviour for the worse from 7.8 to 7.10 2 changing the behavior of Foldable.maximumBy (from foldr to foldl) and changing the behavior of Data.List.maximumBy back to what it was before, and arguably the “better” definition. 3 adding minimumBy/maximumBy as a class method and changing only the list instance.

This also raises the question of whether using foldl over foldl' is the right thing to do, as I was under the impression that foldl will (at least for lists) always just accumulate a large heap of thunks, and one would always want to use foldl' instead. I postulate that if foldl' had been in the report, then it would have been used for maximumBy.

So this yields option 4:

4 changing maximumBy to use foldl'

BTW, why is there no fold' method in Foldable that leaves the associativity (left, right, or mixed in case of a tree) to the Foldable instance, and just implements the “best” strictly accumulating fold for the given data structure?

Greetings, Joachim

-- Joachim “nomeata” Breitner mail@joachim-breitner.de • http://www.joachim-breitner.de/ Jabber: nomeata@joachim-breitner.de • GPG-Key: 0xF0FBF51F Debian Developer: nomeata@debian.org

_______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries