Hopefully laziness makes the complexity work out fine. Nonetheless I don't like relying on laziness for the correct complexity and it would still be nice to have an explicit version. On Wed, Sep 26, 2018 at 10:13:21AM -0400, Brandon Allbery wrote:

Not exactly that, but you can use groupBy fst . sort, then the head of the result list is your "minimumsBy" result.

On Wed, Sep 26, 2018 at 6:28 AM Tom Ellis < tom-lists-haskell-cafe-2017@jaguarpaw.co.uk> wrote:

...

Data.List.minimumBy :: Foldable t => (a -> a -> Ordering) -> t a -> a

https://www.stackage.org/haddock/lts-12.1/base-4.11.1.0/Data-List.html#v:min...

but there are many cases where that's quite unhelpful. Actually what we want is more like

minimumsBy :: ... => (a -> a -> Ordering) -> t a -> [a]

There can be many distinct minimizers. For example when I want to get the collection of the youngest people from [(Age, Person)] I want

minimumsBy (compare `on` fst) [(12, alice), (15, balaji), (12, cho)]

to return

[(12, alice), (12, cho)]

Does "minimumsBy" exist somewhere reasonably standard? Hoogle doesn't throw up anything obvious

https://www.stackage.org/lts-12.1/hoogle?q=%28a+-%3E+a+-%3E+Ordering%29+-%3E...

Haskell’s sort algorithm is linear complexity when only evaluating the front of the list. See also https://ro-che.info/articles/2016-04-02-descending-sort-haskell which includes some measurements. On Wed, Sep 26, 2018 at 10:30 David Feuer wrote:

Laziness does not make the complexity work out fine. Sorting is still O(n log n), which isn't needed here.

On Wed, Sep 26, 2018, 10:22 AM Tom Ellis < tom-lists-haskell-cafe-2017@jaguarpaw.co.uk> wrote:

...

Hopefully laziness makes the complexity work out fine. Nonetheless I don't like relying on laziness for the correct complexity and it would still be nice to have an explicit version.

...

Not exactly that, but you can use groupBy fst . sort, then the head of

On Wed, Sep 26, 2018 at 10:13:21AM -0400, Brandon Allbery wrote: the

...

result list is your "minimumsBy" result.

On Wed, Sep 26, 2018 at 6:28 AM Tom Ellis < tom-lists-haskell-cafe-2017@jaguarpaw.co.uk> wrote:

...

Data.List.minimumBy :: Foldable t => (a -> a -> Ordering) -> t a -> a

https://www.stackage.org/haddock/lts-12.1/base-4.11.1.0/Data-List.html#v:min...

...

but there are many cases where that's quite unhelpful. Actually what

we

...

want is more like

minimumsBy :: ... => (a -> a -> Ordering) -> t a -> [a]

There can be many distinct minimizers. For example when I want to get the collection of the youngest people from [(Age, Person)] I want

minimumsBy (compare `on` fst) [(12, alice), (15, balaji), (12, cho)]

to return

[(12, alice), (12, cho)]

Does "minimumsBy" exist somewhere reasonably standard? Hoogle doesn't throw up anything obvious

https://www.stackage.org/lts-12.1/hoogle?q=%28a+-%3E+a+-%3E+Ordering%29+-%3E...

---

Haskell-Cafe mailing list To (un)subscribe, modify options or view archives go to: http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe Only members subscribed via the mailman list are allowed to post.

_______________________________________________ Haskell-Cafe mailing list To (un)subscribe, modify options or view archives go to: http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe Only members subscribed via the mailman list are allowed to post.

That is interesting. Is anybody aware of a more detailed justification of how lazy evaluation makes this happen? - chris On 09/26/2018 11:38 PM, Bob Ippolito wrote:

Haskell’s sort algorithm is linear complexity when only evaluating the front of the list. See also  https://ro-che.info/articles/2016-04-02-descending-sort-haskell which includes some measurements. 

On Wed, Sep 26, 2018 at 10:30 David Feuer mailto:david.feuer@gmail.com> wrote:

Laziness does not make the complexity work out fine. Sorting is still O(n log n), which isn't needed here.

On Wed, Sep 26, 2018, 10:22 AM Tom Ellis mailto:tom-lists-haskell-cafe-2017@jaguarpaw.co.uk> wrote:

Hopefully laziness makes the complexity work out fine.  Nonetheless I don't like relying on laziness for the correct complexity and it would still be nice to have an explicit version.

On Wed, Sep 26, 2018 at 10:13:21AM -0400, Brandon Allbery wrote: > Not exactly that, but you can use groupBy fst . sort, then the head of the > result list is your "minimumsBy" result. > > On Wed, Sep 26, 2018 at 6:28 AM Tom Ellis < > tom-lists-haskell-cafe-2017@jaguarpaw.co.uk mailto:tom-lists-haskell-cafe-2017@jaguarpaw.co.uk> wrote: > > Data.List.minimumBy :: Foldable t => (a -> a -> Ordering) -> t a -> a > > > > > > https://www.stackage.org/haddock/lts-12.1/base-4.11.1.0/Data-List.html#v:min... > > > > but there are many cases where that's quite unhelpful.  Actually what we > > want is more like > > > >     minimumsBy :: ... => (a -> a -> Ordering) -> t a -> [a] > > > > There can be many distinct minimizers.  For example when I want to get the > > collection of the youngest people from [(Age, Person)] I want > > > >     minimumsBy (compare `on` fst) [(12, alice), (15, balaji), (12, cho)] > > > > to return > > > >     [(12, alice), (12, cho)] > > > > Does "minimumsBy" exist somewhere reasonably standard?  Hoogle doesn't > > throw > > up anything obvious > > > > > > https://www.stackage.org/lts-12.1/hoogle?q=%28a+-%3E+a+-%3E+Ordering%29+-%3E... _______________________________________________ Haskell-Cafe mailing list To (un)subscribe, modify options or view archives go to: http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe Only members subscribed via the mailman list are allowed to post.

_______________________________________________ Haskell-Cafe mailing list To (un)subscribe, modify options or view archives go to: http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe Only members subscribed via the mailman list are allowed to post.

_______________________________________________ Haskell-Cafe mailing list To (un)subscribe, modify options or view archives go to: http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe Only members subscribed via the mailman list are allowed to post.

You can read a recent implementation of sortBy at https://github.com/ghc/ghc/blob/ghc-8.6.1-release/libraries/base/Data/OldLis... It often helps to work with a concrete example, such as: head (sort [5, 4, 6, 3, 7, 1]) Expanding that a bit we get: head (mergeAll (sequences [5, 4, 6, 3, 7, 1])) sequences is linear time, it breaks the list up into monotonically increasing sublists (up to n/2 of them) with pairwise comparisons. It doesn't all get evaluated right away, but nothing "interesting" is happening there so let's show it fully evaluated. head (mergeAll [[4, 5], [3, 6], [1, 7]]) Expanding that we get head (mergeAll (mergePairs [[4, 5], [3, 6], [1, 7]]))) head (mergeAll (merge [4, 5] [3, 6] : [1, 7] : [])) head (mergeAll (mergePairs (merge [4, 5] [3, 6] : [1, 7] : []))) head (mergeAll (merge (merge [4, 5] [3, 6]) [1, 7] : []))) head (merge (merge [4, 5] [3, 6]) [1, 7]) head (merge (3 : merge [4, 5] [6]) [1, 7]) head (1 : merge (3 : merge [4, 5] [6]) [7]) 1 This phase is linear time in the worst case, we only compare the first element of each sublist once to find the least element. Having a constant number of phases that are linear (two in this case) is still linear. It would be linearithmic time if we were to fully evaluate the whole sort, but laziness gets to leave a lot of that work unevaluated. -bob On Thu, Sep 27, 2018 at 10:16 PM Christian Sternagel wrote:

That is interesting. Is anybody aware of a more detailed justification of how lazy evaluation makes this happen? - chris

On 09/26/2018 11:38 PM, Bob Ippolito wrote:

...

Haskell’s sort algorithm is linear complexity when only evaluating the front of the list. See also https://ro-che.info/articles/2016-04-02-descending-sort-haskell which includes some measurements.

On Wed, Sep 26, 2018 at 10:30 David Feuer mailto:david.feuer@gmail.com> wrote:

Laziness does not make the complexity work out fine. Sorting is still O(n log n), which isn't needed here.

On Wed, Sep 26, 2018, 10:22 AM Tom Ellis mailto:tom-lists-haskell-cafe-2017@jaguarpaw.co.uk> wrote:

Hopefully laziness makes the complexity work out fine. Nonetheless I don't like relying on laziness for the correct complexity and it would still be nice to have an explicit version.

On Wed, Sep 26, 2018 at 10:13:21AM -0400, Brandon Allbery wrote: > Not exactly that, but you can use groupBy fst . sort, then the head of the > result list is your "minimumsBy" result. > > On Wed, Sep 26, 2018 at 6:28 AM Tom Ellis < > tom-lists-haskell-cafe-2017@jaguarpaw.co.uk mailto:tom-lists-haskell-cafe-2017@jaguarpaw.co.uk> wrote: > > Data.List.minimumBy :: Foldable t => (a -> a -> Ordering) -> t a -> a > > > > > >

https://www.stackage.org/haddock/lts-12.1/base-4.11.1.0/Data-List.html#v:min...

...

> > > > but there are many cases where that's quite unhelpful. Actually what we > > want is more like > > > > minimumsBy :: ... => (a -> a -> Ordering) -> t a -> [a] > > > > There can be many distinct minimizers. For example when I want to get the > > collection of the youngest people from [(Age, Person)] I want > > > > minimumsBy (compare `on` fst) [(12, alice), (15, balaji), (12, cho)] > > > > to return > > > > [(12, alice), (12, cho)] > > > > Does "minimumsBy" exist somewhere reasonably standard? Hoogle doesn't > > throw > > up anything obvious > > > > > >

https://www.stackage.org/lts-12.1/hoogle?q=%28a+-%3E+a+-%3E+Ordering%29+-%3E...

...

_______________________________________________ Haskell-Cafe mailing list To (un)subscribe, modify options or view archives go to: http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe Only members subscribed via the mailman list are allowed to post.

_______________________________________________ Haskell-Cafe mailing list To (un)subscribe, modify options or view archives go to: http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe Only members subscribed via the mailman list are allowed to post.

_______________________________________________ Haskell-Cafe mailing list To (un)subscribe, modify options or view archives go to: http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe Only members subscribed via the mailman list are allowed to post.

_______________________________________________ Haskell-Cafe mailing list To (un)subscribe, modify options or view archives go to: http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe Only members subscribed via the mailman list are allowed to post.