Function to add to Data.List

John Wiegley

5 Apr 2014 5 Apr '14

5:53 p.m.

I heard a talk that mentioned this transform today at Hac NYC, and was surprised it wasn't already in Data.List: -- | Sort a list using a key on each element. This implements the -- decorate-sort-undecorate paradigm, also called a Schwarzian transform. sortByKey :: Ord b => (a -> b) -> [a] -> [a] sortByKey f = map snd . sortBy (comparing fst) . map (\x -> (f x, x)) I would like to propose adding it. John

Show replies by date

Henning Thielemann

5 Apr 5 Apr

5:58 p.m.

New subject: Function to add to Data.List -> Key.sort

Am 05.04.2014 23:53, schrieb John Wiegley:

...

I heard a talk that mentioned this transform today at Hac NYC, and was surprised it wasn't already in Data.List:

-- | Sort a list using a key on each element. This implements the -- decorate-sort-undecorate paradigm, also called a Schwarzian transform. sortByKey :: Ord b => (a -> b) -> [a] -> [a] sortByKey f = map snd . sortBy (comparing fst) . map (\x -> (f x, x))

I would like to propose adding it.

I have it as Data.List.Key.sort in utility-ht.

Niklas Haas

6:27 p.m.

On Sat, 05 Apr 2014 17:53:04 -0400, John Wiegley wrote:

...

I heard a talk that mentioned this transform today at Hac NYC, and was surprised it wasn't already in Data.List:

-- | Sort a list using a key on each element. This implements the -- decorate-sort-undecorate paradigm, also called a Schwarzian transform. sortByKey :: Ord b => (a -> b) -> [a] -> [a] sortByKey f = map snd . sortBy (comparing fst) . map (\x -> (f x, x))

I would like to propose adding it.

John _______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries

This already exists in the form of sortBy . comparing or sortBy (comparing f)

Henning Thielemann

6:33 p.m.

Am 06.04.2014 00:27, schrieb Niklas Haas:

...

On Sat, 05 Apr 2014 17:53:04 -0400, John Wiegley wrote:

...
I heard a talk that mentioned this transform today at Hac NYC, and was surprised it wasn't already in Data.List:

-- | Sort a list using a key on each element. This implements the -- decorate-sort-undecorate paradigm, also called a Schwarzian transform. sortByKey :: Ord b => (a -> b) -> [a] -> [a] sortByKey f = map snd . sortBy (comparing fst) . map (\x -> (f x, x))

I would like to propose adding it.

John _______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries

This already exists in the form of

sortBy . comparing

or

sortBy (comparing f)

Not exactly, because sortByKey memorizes the results of 'f' and (sortBy . comparing) recomputes 'f' all the time.

Niklas Haas

6:43 p.m.

On Sun, 06 Apr 2014 00:33:34 +0200, Henning Thielemann wrote:

...

Not exactly, because sortByKey memorizes the results of 'f' and (sortBy . comparing) recomputes 'f' all the time.

Ah, that occurred to me after reading through the original email again, sorry for replying prematurely. Would it be worthwhile to use a strict structure instead of ordinary 2-tuples?

Artyom Kazak

6:51 p.m.

On 04/06/2014 02:33 AM, Henning Thielemann wrote:

...

Not exactly, because sortByKey memorizes the results of 'f' and (sortBy . comparing) recomputes 'f' all the time.

Racket language (PLT Scheme) has both variants, and I think both are needed – e.g. `length` of strings should probably be memorized, while something like `snd` or `negate` shouldn't.

Herbert Valerio Riedel

6 Apr 6 Apr

4:09 a.m.

On 2014-04-06 at 00:33:34 +0200, Henning Thielemann wrote:

...

Am 06.04.2014 00:27, schrieb Niklas Haas:

[...]

...

...
This already exists in the form of

sortBy . comparing

or

sortBy (comparing f)

Not exactly, because sortByKey memorizes the results of 'f' and (sortBy . comparing) recomputes 'f' all the time.

...what about a RULE that replaces "sortBy . comparing" by an internal non-exported "sortByKey"?

Andreas Abel

4:33 a.m.

-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 On 06.04.2014 10:09, Herbert Valerio Riedel wrote:

...

On 2014-04-06 at 00:33:34 +0200, Henning Thielemann wrote:

...
Am 06.04.2014 00:27, schrieb Niklas Haas:

...
This already exists in the form of

sortBy . comparing

Not exactly, because sortByKey memorizes the results of 'f' and (sortBy . comparing) recomputes 'f' all the time.

...what about a RULE that replaces "sortBy . comparing" by an internal non-exported "sortByKey"?

How does GHC give evidence to the programmer that RULEs actually applied? How do you argue to the user of Data.List that there is no need to implement a (memoizing) sortByKey since GHC will do the right thing for him if he uses sortBy . comparing instead? As long as RULEs remain some (practically) invisible compiler magic, as long as I have a way to declare that in certain situations certain rules absolutely MUST fire, I can put no trust in the whole RULEs mechanism. Cheers, Andreas - -- Andreas Abel <>< Du bist der geliebte Mensch. Department of Computer Science and Engineering Chalmers and Gothenburg University, Sweden andreas.abel@gu.se http://www2.tcs.ifi.lmu.de/~abel/ -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.11 (GNU/Linux) Comment: Using GnuPG with Thunderbird - http://www.enigmail.net/ iEYEARECAAYFAlNBEVkACgkQPMHaDxpUpLPaIgCg1SuQLD9lHoVrGpgIcFipQ/9Q 7MUAn2C5w2/wgpvyGoJOEjg7hMeLNVrk =zunq -----END PGP SIGNATURE-----

Henning Thielemann

4:35 a.m.

Am 06.04.2014 10:09, schrieb Herbert Valerio Riedel:

...

On 2014-04-06 at 00:33:34 +0200, Henning Thielemann wrote:

...
Not exactly, because sortByKey memorizes the results of 'f' and (sortBy . comparing) recomputes 'f' all the time.

...what about a RULE that replaces "sortBy . comparing" by an internal non-exported "sortByKey"?

This might not always be an optimization, like a compiler cannot replace common sub-expressons by let in general.

Andreas Abel

3:41 a.m.

-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 +1 On 05.04.2014 23:53, John Wiegley wrote:

...

I heard a talk that mentioned this transform today at Hac NYC, and was surprised it wasn't already in Data.List:

-- | Sort a list using a key on each element. This implements the -- decorate-sort-undecorate paradigm, also called a Schwarzian transform. sortByKey :: Ord b => (a -> b) -> [a] -> [a] sortByKey f = map snd . sortBy (comparing fst) . map (\x -> (f x, x))

I would like to propose adding it.

John _______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries

- -- Andreas Abel <>< Du bist der geliebte Mensch. Department of Computer Science and Engineering Chalmers and Gothenburg University, Sweden andreas.abel@gu.se http://www2.tcs.ifi.lmu.de/~abel/ -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.11 (GNU/Linux) Comment: Using GnuPG with Thunderbird - http://www.enigmail.net/ iEYEARECAAYFAlNBBUUACgkQPMHaDxpUpLOqPgCffZM+OVZjGR59UoRJGHKJGNDP SKwAniDCMgEVOmk4ILOV2GOnKmVOU5VB =jUNT -----END PGP SIGNATURE-----

Daniel Trstenjak

6:48 a.m.

Hi John, I only somehow dislike the name 'sortByKey', because 'Key' feels a bit generic, without giving that much of a hint, perhaps something like 'sortMapped' could be a bit more telling. Greetings, Daniel

Jake McArthur

8:05 a.m.

I've always called my local definitions of this function `sortOn`. I also frequently define `groupOn`. I dislike the suggestion to use rewrite rules. It's not always an optimization to memoize the key to sort on. For example, `sortOn id` is probably slower than `sortBy (comparing id)`. Also, if the key is very large, it could be a pretty bad regression. On Sun, Apr 6, 2014 at 6:48 AM, Daniel Trstenjak

...

wrote:

...

Hi John,

I only somehow dislike the name 'sortByKey', because 'Key' feels a bit generic, without giving that much of a hint, perhaps something like 'sortMapped' could be a bit more telling.

Greetings, Daniel _______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries

Daniel Trstenjak

8:34 a.m.

Am 06.04.2014 um 14:05 schrieb Jake McArthur :

...

I've always called my local definitions of this function `sortOn`. I also frequently define `groupOn`.

Oh yes, 'sortOn' is a really nice name. :)

Niklas Haas

8:43 a.m.

On Sun, 6 Apr 2014 14:34:49 +0200, Daniel Trstenjak wrote:

...

Am 06.04.2014 um 14:05 schrieb Jake McArthur :

...
I've always called my local definitions of this function `sortOn`. I also frequently define `groupOn`.

Oh yes, 'sortOn' is a really nice name. :) _______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries

Huh, that name just reminded me of GHC.Exts.sortWith: http://hackage.haskell.org/package/base-4.6.0.1/docs/GHC-Exts.html#v:sortWit... Which actually has the right type signature, but it's still implemented as compare (f x) (f y), and for good reasons too in this case.

johnw＠newartisans.com

4:34 p.m.

...

...
...
...
...
Niklas Haas writes:

...

...
Oh yes, 'sortOn' is a really nice name. :)

...

Huh, that name just reminded me of GHC.Exts.sortWith:

Either of the names sortOn, or sortWith, sound good. I think I prefer sortWith. John

Evan Laforge

7:06 p.m.

"On" has some precedent in Function.on, i.e. sortOn k = sortBy (compare `on` k) Of course that's the "cheap key" version, I guess you're discussing adding the expensive key version. On Apr 6, 2014 1:34 PM, wrote:

...

...
...
...
...
...
Niklas Haas writes:

...
...
Oh yes, 'sortOn' is a really nice name. :)

...
Huh, that name just reminded me of GHC.Exts.sortWith:

Either of the names sortOn, or sortWith, sound good. I think I prefer sortWith.

John _______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries

Edward Kmett

9:02 p.m.

There is some precedent for 'sortOn' as the naming convention should we choose to go ahead with it. http://lukepalmer.wordpress.com/2009/07/01/on-the-by-functions/ Having some mechanism by which we can explicitly request the Schwartzian transform like that as opposed to 'element by element' By functions strikes me personally as a good idea and sufficiently non-trivial to pass the "Fairbairn threshold" in my book. +1 from me. -Edward On Sun, Apr 6, 2014 at 4:34 PM, wrote:

...

...
...
...
...
...
Niklas Haas writes:

...
...
Oh yes, 'sortOn' is a really nice name. :)

...
Huh, that name just reminded me of GHC.Exts.sortWith:

Either of the names sortOn, or sortWith, sound good. I think I prefer sortWith.

John _______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries

Carter Schonwald

9:39 p.m.

+1 here, seems like a nice design On Sun, Apr 6, 2014 at 9:02 PM, Edward Kmett wrote:

...

There is some precedent for 'sortOn' as the naming convention should we choose to go ahead with it.

http://lukepalmer.wordpress.com/2009/07/01/on-the-by-functions/

Having some mechanism by which we can explicitly request the Schwartzian transform like that as opposed to 'element by element' By functions strikes me personally as a good idea and sufficiently non-trivial to pass the "Fairbairn threshold" in my book.

+1 from me.

-Edward

On Sun, Apr 6, 2014 at 4:34 PM, wrote:

...
...
...
...
...
> Niklas Haas writes:

...
...
Oh yes, 'sortOn' is a really nice name. :)

...
Huh, that name just reminded me of GHC.Exts.sortWith:

Either of the names sortOn, or sortWith, sound good. I think I prefer sortWith.

John _______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries

_______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries

wren romano

9 Apr 9 Apr

6:08 p.m.

On Sun, Apr 6, 2014 at 9:39 PM, Carter Schonwald wrote:

...

On Sun, Apr 6, 2014 at 9:02 PM, Edward Kmett wrote:

...
There is some precedent for 'sortOn' as the naming convention should we choose to go ahead with it.

http://lukepalmer.wordpress.com/2009/07/01/on-the-by-functions/

Having some mechanism by which we can explicitly request the Schwartzian transform like that as opposed to 'element by element' By functions strikes me personally as a good idea and sufficiently non-trivial to pass the "Fairbairn threshold" in my book.

+1 from me.

+1 here, seems like a nice design

+1 for adding the decorate-sort-undecorate function to the API. -1 for adding RULES, since this transformation is not always an optimization. +1 for the name sortOn. Luke Palmer discusses the *On naming scheme, and I've seen/used it elsewhere. -0 for the name sortWith. I think "with" is too generic a preposition; it works best as a two-place predicate imo (e.g., fooWithKey) -- Live well, ~wren

John Lato

7:39 p.m.

+1 regardless of name -1 for adding RULEs I think the documentation should note how this function differs from 'sortBy (comparing f)' (apologies if this has already been discussed, I don't see it). On Sun, Apr 6, 2014 at 6:02 PM, Edward Kmett wrote:

...

There is some precedent for 'sortOn' as the naming convention should we choose to go ahead with it.

http://lukepalmer.wordpress.com/2009/07/01/on-the-by-functions/

Having some mechanism by which we can explicitly request the Schwartzian transform like that as opposed to 'element by element' By functions strikes me personally as a good idea and sufficiently non-trivial to pass the "Fairbairn threshold" in my book.

+1 from me.

-Edward

On Sun, Apr 6, 2014 at 4:34 PM, wrote:

...
...
...
...
...
> Niklas Haas writes:

...
...
Oh yes, 'sortOn' is a really nice name. :)

...
Huh, that name just reminded me of GHC.Exts.sortWith:

Either of the names sortOn, or sortWith, sound good. I think I prefer sortWith.

John _______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries

_______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries

Henning Thielemann

6 Apr 6 Apr

8:45 a.m.

Am 06.04.2014 14:05, schrieb Jake McArthur:

...

I've always called my local definitions of this function `sortOn`. I also frequently define `groupOn`.

The are also Key.group and other counterparts of "*By" functions in http://hackage.haskell.org/package/utility-ht-0.0.10/docs/Data-List-Key.html

Herbert Valerio Riedel

10 Apr 10 Apr

5:37 a.m.

On 2014-04-05 at 23:53:04 +0200, John Wiegley wrote:

...

I heard a talk that mentioned this transform today at Hac NYC, and was surprised it wasn't already in Data.List:

-- | Sort a list using a key on each element. This implements the -- decorate-sort-undecorate paradigm, also called a Schwarzian transform. sortByKey :: Ord b => (a -> b) -> [a] -> [a] sortByKey f = map snd . sortBy (comparing fst) . map (\x -> (f x, x))

I would like to propose adding it.

+1 with a preference on naming it 'Data.List.sortOn' (and I retract my suggestion of using RULES) PS: Btw, I'd suggest making 'Schwarzian transform' in the docstring into a Haddock link: <http://en.wikipedia.org/wiki/Schwartzian_transform Schwartzian transform>

4059

Age (days ago)

4064

Last active (days ago)

List overview

Download

21 comments

14 participants

participants (14)

Andreas Abel
Artyom Kazak
Carter Schonwald
Daniel Trstenjak
Edward Kmett
Evan Laforge
Henning Thielemann
Herbert Valerio Riedel
Jake McArthur
John Lato
John Wiegley
johnw＠newartisans.com
Niklas Haas
wren romano