Proposal #3271: new methods for Data.Sequence

[Louis Wasserman]

(Thanks to Isaac for the n00b-friendly instruction link!)

http://hackage.haskell.org/trac/ghc/ticket/3271

Data.Sequence is meant as a general-purpose implementation of finite
sequences. The range of methods it offers, however, is considerably more
constrained than Data.List, even allowing for the constraint that sequences
are finite.

The following methods cannot be efficiently implemented based on currently
exported methods from Data.Sequence.

   - zipWith and its variants. Note: it suffices to define zipWith alone.
   - replicate. (This can be implemented in O(log n) time with node
   sharing.)

The following methods are relatively simple extensions of already-exported
methods. It may be more appropriate to allow library users to reimplement
them themselves.

   - scanl, scanr, and variants. This is relatively straightforward using
   methods borrowed from the Traversable instance.
   - tails and inits. tails is equivalent to scanr (<|) empty; inits is
   similar.
   - takeWhile, dropWhile, span, break (and perhaps from-the-end
   variations). Finding a breakpoint index can be done as efficiently on lists
   as on sequences; find the appropriate breakpoint index after converting to a
   list and use splitAt.
   - unfoldr and iterate, though the latter would require a finite number of
   iterations to perform.
   - partition. I can conceive of a slightly more efficient implementation
   than the trivial one, but the gains may be minimal.

Discussion deadline: two weeks from today (June 16).

Of these, I have implemented the first three bullets.

Louis Wasserman
wasserman.louis at gmail.com


On Mon, Jun 1, 2009 at 9:52 PM, Isaac Dupree <ml at isaac.cedarswampstudios.org
> wrote:

> Louis Wasserman wrote:
>
>> This patch contains several methods for Data.Sequence I've always thought
>> were long missing:
>>
>
> Excellent! Can you make an official "library proposal"? It's not hard.
> http://www.haskell.org/haskellwiki/Library_submissions
>
> Basically, see section 2: make a Trac ticket; choose a discussion deadline
> (perhaps, 2 weeks from now); and then post back on this mailing-list
> including a link to the ticket, a copy of the description, and stating the
> end-of-discussion date.
>
> -Isaac
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/libraries/attachments/20090602/32cc673b/attachment.html