Proposal: export more Data.Sequence internals

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

Proposal: export more Data.Sequence internals

David Feuer
I'd like containers to export more Data.Sequence internals, and to do
so in a way that allows external users to rely on them. I propose the
following:

1. Add a module, Data.FingerTree.IntPlus, abstractly exporting the
finger trees used to represent sequences. These can also be used for
other finger trees with measurements in the (Int, +) monoid. This
would include various basic operations for cons, snoc, and splitting,
with most names the same as for sequences.
2. Add a module, Data.FingerTree.IntPlus.Unsafe, exporting efficient
mapping/traversing functions that rely on specific preconditions to
maintain the internal fingertree annotation invariant.
3. Add a module, Data.Sequence.StableInternal, exporting the internal
structure of sequences and also some internal functions that may be
useful elsewhere (I'm particularly interested in the `splitMap`
function and future variants thereof). Unlike the `.Internal` module,
this module would be subject to the package version policy, and would
therefore be more suitable for use by other packages.

I am very open to suggestions for modifications to the module names.
One option might be to put all the FingerTree.IntPlus stuff in the
Data.Sequence.StableInternal hierarchy, if folks think it should be
buried a bit.

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

Re: Proposal: export more Data.Sequence internals

Zemyla
I was sort of thinking of something similar, but what I would want to export would be constructors for it:

data Seq a
  = Empty
  | Single a
  | More {-# UNPACK #-} !(Seq2 a)

where a Seq2 is basically the Deep constructor as a type, and represents a Seq with 2 or more values in it. Though I expect this won't happen until we start using dependent types to express the difference between possibly-empty and nonempty sequences.

On Fri, Feb 5, 2021, 15:22 David Feuer <[hidden email]> wrote:
I'd like containers to export more Data.Sequence internals, and to do
so in a way that allows external users to rely on them. I propose the
following:

1. Add a module, Data.FingerTree.IntPlus, abstractly exporting the
finger trees used to represent sequences. These can also be used for
other finger trees with measurements in the (Int, +) monoid. This
would include various basic operations for cons, snoc, and splitting,
with most names the same as for sequences.
2. Add a module, Data.FingerTree.IntPlus.Unsafe, exporting efficient
mapping/traversing functions that rely on specific preconditions to
maintain the internal fingertree annotation invariant.
3. Add a module, Data.Sequence.StableInternal, exporting the internal
structure of sequences and also some internal functions that may be
useful elsewhere (I'm particularly interested in the `splitMap`
function and future variants thereof). Unlike the `.Internal` module,
this module would be subject to the package version policy, and would
therefore be more suitable for use by other packages.

I am very open to suggestions for modifications to the module names.
One option might be to put all the FingerTree.IntPlus stuff in the
Data.Sequence.StableInternal hierarchy, if folks think it should be
buried a bit.

David
_______________________________________________
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: Proposal: export more Data.Sequence internals

David Feuer
That's not the current representation of sequences, and making that change would be a significant project I can't undertake at the moment. I'm not proposing to freeze the sequence representation solid; just to bring it under PVP and make it more accessible/usable to other packages. I also want the (Int,+) finger trees for a currently-toy project playing with incremental quicksort for sequences.

On Fri, Feb 5, 2021, 7:07 PM Zemyla <[hidden email]> wrote:
I was sort of thinking of something similar, but what I would want to export would be constructors for it:

data Seq a
  = Empty
  | Single a
  | More {-# UNPACK #-} !(Seq2 a)

where a Seq2 is basically the Deep constructor as a type, and represents a Seq with 2 or more values in it. Though I expect this won't happen until we start using dependent types to express the difference between possibly-empty and nonempty sequences.

On Fri, Feb 5, 2021, 15:22 David Feuer <[hidden email]> wrote:
I'd like containers to export more Data.Sequence internals, and to do
so in a way that allows external users to rely on them. I propose the
following:

1. Add a module, Data.FingerTree.IntPlus, abstractly exporting the
finger trees used to represent sequences. These can also be used for
other finger trees with measurements in the (Int, +) monoid. This
would include various basic operations for cons, snoc, and splitting,
with most names the same as for sequences.
2. Add a module, Data.FingerTree.IntPlus.Unsafe, exporting efficient
mapping/traversing functions that rely on specific preconditions to
maintain the internal fingertree annotation invariant.
3. Add a module, Data.Sequence.StableInternal, exporting the internal
structure of sequences and also some internal functions that may be
useful elsewhere (I'm particularly interested in the `splitMap`
function and future variants thereof). Unlike the `.Internal` module,
this module would be subject to the package version policy, and would
therefore be more suitable for use by other packages.

I am very open to suggestions for modifications to the module names.
One option might be to put all the FingerTree.IntPlus stuff in the
Data.Sequence.StableInternal hierarchy, if folks think it should be
buried a bit.

David
_______________________________________________
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: Proposal: export more Data.Sequence internals

George Wilson
In reply to this post by David Feuer
Sounds reasonable to me.
I don't have any particular input on the module names or hierarchy.

Cheers,
George

On Sat, 6 Feb 2021, 07:22 David Feuer, <[hidden email]> wrote:
I'd like containers to export more Data.Sequence internals, and to do
so in a way that allows external users to rely on them. I propose the
following:

1. Add a module, Data.FingerTree.IntPlus, abstractly exporting the
finger trees used to represent sequences. These can also be used for
other finger trees with measurements in the (Int, +) monoid. This
would include various basic operations for cons, snoc, and splitting,
with most names the same as for sequences.
2. Add a module, Data.FingerTree.IntPlus.Unsafe, exporting efficient
mapping/traversing functions that rely on specific preconditions to
maintain the internal fingertree annotation invariant.
3. Add a module, Data.Sequence.StableInternal, exporting the internal
structure of sequences and also some internal functions that may be
useful elsewhere (I'm particularly interested in the `splitMap`
function and future variants thereof). Unlike the `.Internal` module,
this module would be subject to the package version policy, and would
therefore be more suitable for use by other packages.

I am very open to suggestions for modifications to the module names.
One option might be to put all the FingerTree.IntPlus stuff in the
Data.Sequence.StableInternal hierarchy, if folks think it should be
buried a bit.

David
_______________________________________________
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: Proposal: export more Data.Sequence internals

Carter Schonwald
In reply to this post by David Feuer
What are some down sides that exposing these could entail?  Like, what are data structure changes in implementation that are worth exploring that suddenly become major version bumps whereas before they’d be invisible improvements 

Is there any way backpack and or cabals multi library package support can help here ?

On Fri, Feb 5, 2021 at 4:22 PM David Feuer <[hidden email]> wrote:
I'd like containers to export more Data.Sequence internals, and to do
so in a way that allows external users to rely on them. I propose the
following:

1. Add a module, Data.FingerTree.IntPlus, abstractly exporting the
finger trees used to represent sequences. These can also be used for
other finger trees with measurements in the (Int, +) monoid. This
would include various basic operations for cons, snoc, and splitting,
with most names the same as for sequences.
2. Add a module, Data.FingerTree.IntPlus.Unsafe, exporting efficient
mapping/traversing functions that rely on specific preconditions to
maintain the internal fingertree annotation invariant.
3. Add a module, Data.Sequence.StableInternal, exporting the internal
structure of sequences and also some internal functions that may be
useful elsewhere (I'm particularly interested in the `splitMap`
function and future variants thereof). Unlike the `.Internal` module,
this module would be subject to the package version policy, and would
therefore be more suitable for use by other packages.

I am very open to suggestions for modifications to the module names.
One option might be to put all the FingerTree.IntPlus stuff in the
Data.Sequence.StableInternal hierarchy, if folks think it should be
buried a bit.

David
_______________________________________________
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: Proposal: export more Data.Sequence internals

Haskell - Libraries mailing list
In reply to this post by David Feuer
Hi David, and apologies for the late response!

I don't have much to add to this discussion since I'm rather
unfamiliar with the Data.Sequence internals and fingertrees in
general. Since this code is pretty stable AFAIK, I don't see a problem
with exposing it under the PVP.

My only suggestion would be to find a slightly better name than
Data.Sequence.StableInternal. Something like Data.Sequence.Core
perhaps?!

Cheers!
Simon

Am Fr., 5. Feb. 2021 um 22:22 Uhr schrieb David Feuer <[hidden email]>:

>
> I'd like containers to export more Data.Sequence internals, and to do
> so in a way that allows external users to rely on them. I propose the
> following:
>
> 1. Add a module, Data.FingerTree.IntPlus, abstractly exporting the
> finger trees used to represent sequences. These can also be used for
> other finger trees with measurements in the (Int, +) monoid. This
> would include various basic operations for cons, snoc, and splitting,
> with most names the same as for sequences.
> 2. Add a module, Data.FingerTree.IntPlus.Unsafe, exporting efficient
> mapping/traversing functions that rely on specific preconditions to
> maintain the internal fingertree annotation invariant.
> 3. Add a module, Data.Sequence.StableInternal, exporting the internal
> structure of sequences and also some internal functions that may be
> useful elsewhere (I'm particularly interested in the `splitMap`
> function and future variants thereof). Unlike the `.Internal` module,
> this module would be subject to the package version policy, and would
> therefore be more suitable for use by other packages.
>
> I am very open to suggestions for modifications to the module names.
> One option might be to put all the FingerTree.IntPlus stuff in the
> Data.Sequence.StableInternal hierarchy, if folks think it should be
> buried a bit.
>
> David
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries