Bob Ippolito bob at redivi.com
Wed Sep 26 14:38:42 UTC 2018

```Haskellâ€™s sort algorithm is linear complexity when only evaluating the
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 <
>
>> 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
>> > >
>> > >
>> > >
>> > >
>> > > 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
>> _______________________________________________
>> To (un)subscribe, modify options or view archives go to:
>> Only members subscribed via the mailman list are allowed to post.
>
> _______________________________________________