Proposal: export more Data.Sequence internals

David Feuer david.feuer at
Sat Feb 6 00:13:16 UTC 2021

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 <zemyla at> 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 <david.feuer at> 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
>> Libraries at
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <>

More information about the Libraries mailing list