Function to add to Data.List

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

Function to add to Data.List

John Wiegley-3
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
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Function to add to Data.List -> Key.sort

Henning Thielemann-4
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.

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

Re: Function to add to Data.List

Niklas Haas
In reply to this post by John Wiegley-3
On Sat, 05 Apr 2014 17:53:04 -0400, John Wiegley <[hidden email]> 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
> [hidden email]
> http://www.haskell.org/mailman/listinfo/libraries

This already exists in the form of

sortBy . comparing

or

sortBy (comparing f)
_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Function to add to Data.List

Henning Thielemann-4
Am 06.04.2014 00:27, schrieb Niklas Haas:

> On Sat, 05 Apr 2014 17:53:04 -0400, John Wiegley <[hidden email]> 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
>> [hidden email]
>> 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.

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

Re: Function to add to Data.List

Niklas Haas
On Sun, 06 Apr 2014 00:33:34 +0200, Henning Thielemann <[hidden email]> 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?
_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Function to add to Data.List

Artyom Kazak-2
In reply to this post by Henning Thielemann-4


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.
_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Function to add to Data.List

Andreas Abel
In reply to this post by John Wiegley-3
-----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 [hidden email]
> 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

[hidden email]
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-----
_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Function to add to Data.List

Herbert Valerio Riedel
In reply to this post by Henning Thielemann-4
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"?
_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Function to add to Data.List

Andreas Abel
-----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

[hidden email]
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-----
_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Function to add to Data.List

Henning Thielemann-4
In reply to this post by Herbert Valerio Riedel
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.

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

Re: Function to add to Data.List

Daniel Trstenjak-2
In reply to this post by John Wiegley-3
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
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Function to add to Data.List

Jake McArthur
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 <[hidden email]> 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
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries


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

Re: Function to add to Data.List

Daniel Trstenjak-2
Am 06.04.2014 um 14:05 schrieb Jake McArthur <[hidden email]>:
> 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
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Function to add to Data.List

Niklas Haas
On Sun, 6 Apr 2014 14:34:49 +0200, Daniel Trstenjak <[hidden email]> wrote:
> Am 06.04.2014 um 14:05 schrieb Jake McArthur <[hidden email]>:
> > 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
> [hidden email]
> 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:sortWith

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.
_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Function to add to Data.List

Henning Thielemann-4
In reply to this post by Jake McArthur
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

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

Re: Function to add to Data.List

John Wiegley-2
In reply to this post by Niklas Haas
>>>>> Niklas Haas <[hidden email]> 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
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Function to add to Data.List

Evan Laforge

"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, <[hidden email]> wrote:
>>>>> Niklas Haas <[hidden email]> 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
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries

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

Re: Function to add to Data.List

Edward Kmett-2
In reply to this post by John Wiegley-2
There is some precedent for 'sortOn' as the naming convention should we choose to go ahead with it.


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, <[hidden email]> wrote:
>>>>> Niklas Haas <[hidden email]> 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
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries


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

Re: Function to add to Data.List

Carter Schonwald
+1 here, seems like a nice design 


On Sun, Apr 6, 2014 at 9:02 PM, Edward Kmett <[hidden email]> wrote:
There is some precedent for 'sortOn' as the naming convention should we choose to go ahead with it.


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, <[hidden email]> wrote:
>>>>> Niklas Haas <[hidden email]> 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
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries


_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries



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

Re: Function to add to Data.List

wren romano
On Sun, Apr 6, 2014 at 9:39 PM, Carter Schonwald
<[hidden email]> wrote:

> On Sun, Apr 6, 2014 at 9:02 PM, Edward Kmett <[hidden email]> 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
_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
12