Where is "minimumsBy"?

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
12 messages Options
Reply | Threaded
Open this post in threaded view
|

Where is "minimumsBy"?

Tom Ellis-5
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

Thanks,

Tom
_______________________________________________
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.
Reply | Threaded
Open this post in threaded view
|

Re: Where is "minimumsBy"?

Brandon Allbery
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 <[hidden email]> 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

Thanks,

Tom
_______________________________________________
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.


--
brandon s allbery kf8nh

_______________________________________________
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.
Reply | Threaded
Open this post in threaded view
|

Re: Where is "minimumsBy"?

Tom Ellis-5
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 <
> [hidden email]> 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.
Reply | Threaded
Open this post in threaded view
|

Re: Where is "minimumsBy"?

David Feuer
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 <[hidden email]> 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 <
> [hidden email]> 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.
Reply | Threaded
Open this post in threaded view
|

Re: Where is "minimumsBy"?

Bob Ippolito
Haskell’s sort algorithm is linear complexity when only evaluating the front of the list. See also 

On Wed, Sep 26, 2018 at 10:30 David Feuer <[hidden email]> 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 <[hidden email]> 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 <
> [hidden email]> 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.
Reply | Threaded
Open this post in threaded view
|

Re: Where is "minimumsBy"?

David Feuer
Ah, right... Sorry.

On Wed, Sep 26, 2018, 10:38 AM Bob Ippolito <[hidden email]> wrote:
Haskell’s sort algorithm is linear complexity when only evaluating the front of the list. See also 

On Wed, Sep 26, 2018 at 10:30 David Feuer <[hidden email]> 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 <[hidden email]> 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 <
> [hidden email]> 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.
Reply | Threaded
Open this post in threaded view
|

Re: Where is "minimumsBy"?

Hiromi ISHII
In reply to this post by Tom Ellis-5
Not just a one-shot function, but you can do it with monoids:

```
import Data.Semigroup (Option(..), Semigroup(..))
import Data.DList

maximumsOn :: Ord b => (a -> b) -> [a] -> Maybe [a]
maximumsOn f = fmap (toList . elts) . getOption . foldMap (\a -> Option $ Just $ MaxAll (f a) $ pure a)
-- You don't need `Option`s since GHC 8.4

data MaxAll a b = MaxAll { weight :: a, elts :: DList b }
instance Ord a => Semigroup (MaxAll a b) where
  MaxAll l ls <> MaxAll r rs =
    case compare l r of
      EQ -> MaxAll l (ls <> rs)
      LT -> MaxAll l rs
      GT -> MaxAll r ls
```

> 2018/09/26 19:27、Tom Ellis <[hidden email]>のメール:
>
> 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
>
> Thanks,
>
> Tom
> _______________________________________________
> 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.
----- 石井 大海 ---------------------------
[hidden email]
筑波大学数理物質科学研究科
数学専攻 博士後期課程三年
----------------------------------------------


_______________________________________________
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.

signature.asc (499 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Where is "minimumsBy"?

Viktor Dukhovni
In reply to this post by Tom Ellis-5
> On Sep 26, 2018, at 6:27 AM, Tom Ellis <[hidden email]> wrote:
>
>  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)]

It is a rather elementary function:

import Data.Foldable
import Data.Ord

-- Stable version that keeps the input order for elements that are
-- equal.  If this were to be a library function, I'd drop the
-- 'reverse' post-processing step, and leave the choice of stability
-- to the caller.
--
minimumsBy :: Foldable t => (a -> a -> Ordering) -> t a -> [a]
minimumsBy cmp xs = reverse $ foldl' acc [] xs
  where
    acc [] x = [x]
    acc mins@(m:_) x = case cmp m x of
        LT -> mins
        EQ -> x:mins
        GT -> [x]

--
        Viktor.

_______________________________________________
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.
Reply | Threaded
Open this post in threaded view
|

Re: Where is "minimumsBy"?

David Feuer
That's exactly the approach I was thinking of. Leaving off the
`reverse` saves some time in cases where it's not required. Of course,
there's also a perfectly reasonable version using foldr', in case the
data structure leans the other way. One variation or another of this
approach should be a decent constant factor faster than partially
sorting the list.

On Wed, Sep 26, 2018 at 11:03 AM, Viktor Dukhovni
<[hidden email]> wrote:

>> On Sep 26, 2018, at 6:27 AM, Tom Ellis <[hidden email]> wrote:
>>
>>  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)]
>
> It is a rather elementary function:
>
> import Data.Foldable
> import Data.Ord
>
> -- Stable version that keeps the input order for elements that are
> -- equal.  If this were to be a library function, I'd drop the
> -- 'reverse' post-processing step, and leave the choice of stability
> -- to the caller.
> --
> minimumsBy :: Foldable t => (a -> a -> Ordering) -> t a -> [a]
> minimumsBy cmp xs = reverse $ foldl' acc [] xs
>   where
>     acc [] x = [x]
>     acc mins@(m:_) x = case cmp m x of
>         LT -> mins
>         EQ -> x:mins
>         GT -> [x]
>
> --
>         Viktor.
>
> _______________________________________________
> 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.
Reply | Threaded
Open this post in threaded view
|

Re: Where is "minimumsBy"?

Christian Sternagel
In reply to this post by Bob Ippolito
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 <[hidden email]
> <mailto:[hidden email]>> 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
>     <[hidden email]
>     <mailto:[hidden email]>> 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 <
>         > [hidden email]
>         <mailto:[hidden email]>> 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.
>
_______________________________________________
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.
Reply | Threaded
Open this post in threaded view
|

Re: Where is "minimumsBy"?

Frank Staals
Christian Sternagel <[hidden email]> writes:

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

There might be a more formal argument written down somewhere, but the
gist of it should be:

Think of the recursion tree of merge sort; leaves correspond to
singleton lists, internal nodes correspond to merges of two sorted
lists. To determine the minimum element of the merged result you need to
consider only the first elements of both these lists. Hence, every node
can be charged at most O(1) times. Since the tree has size O(n) the
running time is linear.

--

- Frank
_______________________________________________
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.
Reply | Threaded
Open this post in threaded view
|

Re: Where is "minimumsBy"?

Bob Ippolito
In reply to this post by Christian Sternagel

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 <[hidden email]> 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 <[hidden email]
> <mailto:[hidden email]>> 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
>     <[hidden email]
>     <mailto:[hidden email]>> 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 <
>         > [hidden email]
>         <mailto:[hidden email]>> 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.
>
_______________________________________________
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.