Consider adding `classify`.

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

Consider adding `classify`.

Ignat Insarov
Hello.

There has been [a question on Stack Overflow][1] asking for a way to group a
list by an equivalence relation. Several answers were proposed over time, and I
too [have offered a variant][2]. [I also wrote a benchmark.][3]

I propose that the function be added to the standard libraries.

[1]: https://stackoverflow.com/q/8262179
[2]: https://stackoverflow.com/a/57761458
[3]: https://github.com/kindaro/classify-benchmark.git
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Consider adding `classify`.

Georgi Lyubenov
Hi!

I strongly support adding this to base, I personally have had to use something like this quite often.
One suggestion I have though is to use [NonEmpty a] as the return type, as NonEmpty is already in base and it is a more accurate type.

======
Georgi

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Consider adding `classify`.

Andreas Abel
In reply to this post by Ignat Insarov
This cannot be done efficiently.  I'd extend the equivalence relation to
a total order and then use sort and group.

-1 to adding to the standard libraries.  How about publishing this as a
(well discoverable) package on hackage and see how popular it gets?

On 2020-08-20 19:59, Ignat Insarov wrote:

> Hello.
>
> There has been [a question on Stack Overflow][1] asking for a way to group a
> list by an equivalence relation. Several answers were proposed over time, and I
> too [have offered a variant][2]. [I also wrote a benchmark.][3]
>
> I propose that the function be added to the standard libraries.
>
> [1]: https://stackoverflow.com/q/8262179
> [2]: https://stackoverflow.com/a/57761458
> [3]: https://github.com/kindaro/classify-benchmark.git
> _______________________________________________
> Libraries mailing list
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Consider adding `classify`.

Ignat Insarov
Andreas, then how do you feel about adding that one?

    classifyByProjection ∷ Ord π ⇒ (a → π) → [a] → [[a]]
    classifyByProjection f = List.groupBy ((==) `on` f) . List.sortBy
(compare `on` f)

Having thought about it, I have come to agree that it is usually not
hard to define a suitable projection function.

On Mon, 24 Aug 2020 at 12:39, Andreas Abel <[hidden email]> wrote:

>
> This cannot be done efficiently.  I'd extend the equivalence relation to
> a total order and then use sort and group.
>
> -1 to adding to the standard libraries.  How about publishing this as a
> (well discoverable) package on hackage and see how popular it gets?
>
> On 2020-08-20 19:59, Ignat Insarov wrote:
> > Hello.
> >
> > There has been [a question on Stack Overflow][1] asking for a way to group a
> > list by an equivalence relation. Several answers were proposed over time, and I
> > too [have offered a variant][2]. [I also wrote a benchmark.][3]
> >
> > I propose that the function be added to the standard libraries.
> >
> > [1]: https://stackoverflow.com/q/8262179
> > [2]: https://stackoverflow.com/a/57761458
> > [3]: https://github.com/kindaro/classify-benchmark.git
> > _______________________________________________
> > Libraries mailing list
> > [hidden email]
> > http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
> >
> _______________________________________________
> Libraries mailing list
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Consider adding `classify`.

Roel van Dijk-3
I think your function is a possible candidate for the decorate-sort-undecorate paradigm, like sortOn in base [1].

classifyByProjection ∷ Ord π ⇒ (a → π) → [a] → [[a]]
classifyByProjection f = (map . map) snd . List.groupBy ((==) `on` fst) . List.sortBy (comparing fst) . map (\x -> let y = f x in y `seq` (y, x))

That way the function f is only evaluated once for each element in the input list.
I have not benchmarked this.


Op ma 24 aug. 2020 om 14:49 schreef Ignat Insarov <[hidden email]>:
Andreas, then how do you feel about adding that one?

    classifyByProjection ∷ Ord π ⇒ (a → π) → [a] → [[a]]
    classifyByProjection f = List.groupBy ((==) `on` f) . List.sortBy
(compare `on` f)

Having thought about it, I have come to agree that it is usually not
hard to define a suitable projection function.

On Mon, 24 Aug 2020 at 12:39, Andreas Abel <[hidden email]> wrote:
>
> This cannot be done efficiently.  I'd extend the equivalence relation to
> a total order and then use sort and group.
>
> -1 to adding to the standard libraries.  How about publishing this as a
> (well discoverable) package on hackage and see how popular it gets?
>
> On 2020-08-20 19:59, Ignat Insarov wrote:
> > Hello.
> >
> > There has been [a question on Stack Overflow][1] asking for a way to group a
> > list by an equivalence relation. Several answers were proposed over time, and I
> > too [have offered a variant][2]. [I also wrote a benchmark.][3]
> >
> > I propose that the function be added to the standard libraries.
> >
> > [1]: https://stackoverflow.com/q/8262179
> > [2]: https://stackoverflow.com/a/57761458
> > [3]: https://github.com/kindaro/classify-benchmark.git
> > _______________________________________________
> > Libraries mailing list
> > [hidden email]
> > http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
> >
> _______________________________________________
> Libraries mailing list
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries