<div><div dir="auto">Haskell’s sort algorithm is linear complexity when only evaluating the front of the list. See also <div><a href="https://ro-che.info/articles/2016-04-02-descending-sort-haskell">https://ro-che.info/articles/2016-04-02-descending-sort-haskell</a> which includes some measurements. </div></div></div><div><br><div class="gmail_quote"><div dir="ltr">On Wed, Sep 26, 2018 at 10:30 David Feuer <<a href="mailto:david.feuer@gmail.com">david.feuer@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="auto"><div>Laziness does not make the complexity work out fine. Sorting is still O(n log n), which isn't needed here.</div></div><div dir="auto"><div dir="auto"><br><div class="gmail_quote" dir="auto"><div dir="ltr">On Wed, Sep 26, 2018, 10:22 AM Tom Ellis <<a href="mailto:tom-lists-haskell-cafe-2017@jaguarpaw.co.uk" target="_blank">tom-lists-haskell-cafe-2017@jaguarpaw.co.uk</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Hopefully laziness makes the complexity work out fine.  Nonetheless I don't<br>
like relying on laziness for the correct complexity and it would still be<br>
nice to have an explicit version.<br>
<br>
On Wed, Sep 26, 2018 at 10:13:21AM -0400, Brandon Allbery wrote:<br>
> Not exactly that, but you can use groupBy fst . sort, then the head of the<br>
> result list is your "minimumsBy" result.<br>
> <br>
> On Wed, Sep 26, 2018 at 6:28 AM Tom Ellis <<br>
> <a href="mailto:tom-lists-haskell-cafe-2017@jaguarpaw.co.uk" rel="noreferrer" target="_blank">tom-lists-haskell-cafe-2017@jaguarpaw.co.uk</a>> wrote:<br>
> > Data.List.minimumBy :: Foldable t => (a -> a -> Ordering) -> t a -> a<br>
> ><br>
> ><br>
> > <a href="https://www.stackage.org/haddock/lts-12.1/base-4.11.1.0/Data-List.html#v:minimumBy" rel="noreferrer noreferrer" target="_blank">https://www.stackage.org/haddock/lts-12.1/base-4.11.1.0/Data-List.html#v:minimumBy</a><br>
> ><br>
> > but there are many cases where that's quite unhelpful.  Actually what we<br>
> > want is more like<br>
> ><br>
> >     minimumsBy :: ... => (a -> a -> Ordering) -> t a -> [a]<br>
> ><br>
> > There can be many distinct minimizers.  For example when I want to get the<br>
> > collection of the youngest people from [(Age, Person)] I want<br>
> ><br>
> >     minimumsBy (compare `on` fst) [(12, alice), (15, balaji), (12, cho)]<br>
> ><br>
> > to return<br>
> ><br>
> >     [(12, alice), (12, cho)]<br>
> ><br>
> > Does "minimumsBy" exist somewhere reasonably standard?  Hoogle doesn't<br>
> > throw<br>
> > up anything obvious<br>
> ><br>
> ><br>
> > <a href="https://www.stackage.org/lts-12.1/hoogle?q=%28a+-%3E+a+-%3E+Ordering%29+-%3E+t+a+-%3E+%5Ba%5D" rel="noreferrer noreferrer" target="_blank">https://www.stackage.org/lts-12.1/hoogle?q=%28a+-%3E+a+-%3E+Ordering%29+-%3E+t+a+-%3E+%5Ba%5D</a><br>
_______________________________________________<br>
Haskell-Cafe mailing list<br>
To (un)subscribe, modify options or view archives go to:<br>
<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe" rel="noreferrer noreferrer" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe</a><br>
Only members subscribed via the mailman list are allowed to post.</blockquote></div></div></div>
_______________________________________________<br>
Haskell-Cafe mailing list<br>
To (un)subscribe, modify options or view archives go to:<br>
<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe" rel="noreferrer" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe</a><br>
Only members subscribed via the mailman list are allowed to post.</blockquote></div></div>