#3271: New methods for Data.Sequence
-----------------------------+----------------------------------------------
Reporter: LouisWasserman | Owner:
Type: proposal | Status: new
Priority: normal | Component: libraries/base
Version: 6.10.2 | Severity: normal
Keywords: | Testcase:
Os: Unknown/Multiple | Architecture: Unknown/Multiple
-----------------------------+----------------------------------------------
`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.
--
Ticket URL: <http://hackage.haskell.org/trac/ghc/ticket/3271>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler
_______________________________________________
Glasgow-haskell-bugs mailing list
Glasgow-haskell-bugs@haskell.org
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
