[Haskell-cafe] Where is "minimumsBy"?

[Christian Sternagel]

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 <david.feuer at gmail.com
> <mailto:david.feuer at 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
>     <tom-lists-haskell-cafe-2017 at jaguarpaw.co.uk
>     <mailto:tom-lists-haskell-cafe-2017 at 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 at jaguarpaw.co.uk
>         <mailto:tom-lists-haskell-cafe-2017 at 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:minimumBy
>         > >
>         > > 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+t+a+-%3E+%5Ba%5D
>         _______________________________________________
>         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.
>