Proposal: Add // for Data.Sequence

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

Proposal: Add // for Data.Sequence

Alan Isaac
BACKGROUND
----------

Data.Array provides (//) for incremental array updates.
Data.Sequence lacks this useful functionality.


SCOPE
-----

Doing this efficiently may require that Data.Sequence
access Data.IntMap. (It currently does not.)

David Feuer commented:
We may need to add some more splitting functions to Data.IntMap,
if it supports them, but we probably want to do so anyway to
match up with Data.Map.


SOLUTIONS
-----------

David Feuer offered the following implementation sketch.
(See https://github.com/haskell/containers/issues/262)

Collect all requested changes into an IntMap,
then use something similar to Data.Sequence.splitMap
with Data.IntMap.split to spread them through the tree.

David Feuer commented: splitMap itself is overkill,
because we'll likely be able to preserve whole subtrees.


WHAT MIGHT BREAK
----------------

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

Request: Add sortOn to Data.Sequence

Alan Isaac
REQUEST
-------

The request is to add `sortOn` to Data.Sequence.
`sortOn f` would be equivalent to `sortBy . comparing f`,
but would offer a performance advantage by using a Schwartzian
transform to only evaluate `f` once for each element
in the input sequence.


BACKGROUND
----------

Adding `sortOn` to `Data.List` was proposed at least as early as 2008:
http://www.haskell.org/pipermail/libraries/2008-October/010797.html
It was added in 2014, in response to this feature request:
https://ghc.haskell.org/trac/ghc/ticket/9004


RATIONALES
----------

- convenience
- performance: faster than `sortBy`
- safety: encourages (although does not require) reliance on existing instances of Ord
- interface consistency (specifically, when comparing to Data.List)

Comment: it is certainly possible to pick at each of these rationales.
See the discussion here:
http://stackoverflow.com/questions/37691898/why-is-sortby-so-oddly-unconstrained-and-why-no-general-sorton/37735121


SCOPE
-----

Introduces no new dependencies except possibly on `Data.Ord.comparing`.


SOLUTIONS
-----------

The implementation in Data.List is::

         sortOn :: Ord b => (a -> b) -> [a] -> [a]
         sortOn f = map snd . sortBy (comparing fst)
                            . map (\x -> let y = f x in y `seq` (y, x))

An analogous implementation is possible for Data.Sequence.
However, this request does not propose a specific implementation.


WHAT MIGHT BREAK
----------------

No anticipated breakage.

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

Re: Request: Add sortOn to Data.Sequence

David Feuer

I think thIs is an interesting idea, generally. There seem to be two situations that may call for separate functions. If the "key" type can be stored in an unboxed mutable array, then it seems likely desirable to sort using such an array. Otherwise, we can use the existing sortBy as suggested.

On Jun 10, 2016 12:30 PM, "Alan Isaac" <[hidden email]> wrote:
REQUEST
-------

The request is to add `sortOn` to Data.Sequence.
`sortOn f` would be equivalent to `sortBy . comparing f`,
but would offer a performance advantage by using a Schwartzian
transform to only evaluate `f` once for each element
in the input sequence.


BACKGROUND
----------

Adding `sortOn` to `Data.List` was proposed at least as early as 2008:
http://www.haskell.org/pipermail/libraries/2008-October/010797.html
It was added in 2014, in response to this feature request:
https://ghc.haskell.org/trac/ghc/ticket/9004


RATIONALES
----------

- convenience
- performance: faster than `sortBy`
- safety: encourages (although does not require) reliance on existing instances of Ord
- interface consistency (specifically, when comparing to Data.List)

Comment: it is certainly possible to pick at each of these rationales.
See the discussion here:
http://stackoverflow.com/questions/37691898/why-is-sortby-so-oddly-unconstrained-and-why-no-general-sorton/37735121


SCOPE
-----

Introduces no new dependencies except possibly on `Data.Ord.comparing`.


SOLUTIONS
-----------

The implementation in Data.List is::

        sortOn :: Ord b => (a -> b) -> [a] -> [a]
        sortOn f = map snd . sortBy (comparing fst)
                           . map (\x -> let y = f x in y `seq` (y, x))

An analogous implementation is possible for Data.Sequence.
However, this request does not propose a specific implementation.


WHAT MIGHT BREAK
----------------

No anticipated breakage.

_______________________________________________
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: Request: Add sortOn to Data.Sequence

Edward Kmett-2
We've already accepted a similar addition to Data.List, so I see no harm in having an implementation for Data.Sequence.

-Edward

On Fri, Jun 10, 2016 at 12:45 PM, David Feuer <[hidden email]> wrote:

I think thIs is an interesting idea, generally. There seem to be two situations that may call for separate functions. If the "key" type can be stored in an unboxed mutable array, then it seems likely desirable to sort using such an array. Otherwise, we can use the existing sortBy as suggested.

On Jun 10, 2016 12:30 PM, "Alan Isaac" <[hidden email]> wrote:
REQUEST
-------

The request is to add `sortOn` to Data.Sequence.
`sortOn f` would be equivalent to `sortBy . comparing f`,
but would offer a performance advantage by using a Schwartzian
transform to only evaluate `f` once for each element
in the input sequence.


BACKGROUND
----------

Adding `sortOn` to `Data.List` was proposed at least as early as 2008:
http://www.haskell.org/pipermail/libraries/2008-October/010797.html
It was added in 2014, in response to this feature request:
https://ghc.haskell.org/trac/ghc/ticket/9004


RATIONALES
----------

- convenience
- performance: faster than `sortBy`
- safety: encourages (although does not require) reliance on existing instances of Ord
- interface consistency (specifically, when comparing to Data.List)

Comment: it is certainly possible to pick at each of these rationales.
See the discussion here:
http://stackoverflow.com/questions/37691898/why-is-sortby-so-oddly-unconstrained-and-why-no-general-sorton/37735121


SCOPE
-----

Introduces no new dependencies except possibly on `Data.Ord.comparing`.


SOLUTIONS
-----------

The implementation in Data.List is::

        sortOn :: Ord b => (a -> b) -> [a] -> [a]
        sortOn f = map snd . sortBy (comparing fst)
                           . map (\x -> let y = f x in y `seq` (y, x))

An analogous implementation is possible for Data.Sequence.
However, this request does not propose a specific implementation.


WHAT MIGHT BREAK
----------------

No anticipated breakage.

_______________________________________________
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