[Haskell-cafe] Where is "minimumsBy"?

[David Feuer]

Ah, right... Sorry.

On Wed, Sep 26, 2018, 10:38 AM Bob Ippolito <bob at redivi.com> 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> 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> 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> 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.
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/haskell-cafe/attachments/20180926/3b73c091/attachment.html>