Proposal #3271: new methods for Data.Sequence

[Louis Wasserman]

As a final addition to Data.Sequence, I've
added<http://hackage.haskell.org/trac/ghc/attachment/ticket/3271/new-methods-for-data_sequence.5.dpatch>the
following methods.  Possibly debatable design decisions are
highlighted.

   - mapWithIndex :: (Int -> a -> b) -> Seq a -> Seq b.  (This is based on
   mapAccumL, which is slightly suboptimal [as the full mapping must be done
   before the last element can be examined], but acceptable given the tiny code
   investment.)
   - elemIndex, elemIndices, findIndex, findIndices, all as in Data.List.
   - elemLastIndex, findLastIndex, elemIndicesDesc, findIndicesDesc, all
   working from right-to-left but otherwise analogous.
**Note:**findIndicesDesc and elemIndicesDesc return lists, not
Sequences, so as to
   permit maximum laziness.  Moreover, both of those methods fuse well.
   - takeWhileEnd, dropWhileEnd, spanEnd, breakEnd, all of which work from
   right-to-left but otherwise perform as their Data.List analogues.  *
   *Note:** spanEnd p xs, in particular, returns *first* the longest *suffix
   * of xs of elements satisfying p, and then the remaining prefix.

All but mapWithIndex take O(i) time, where i is the appropriate breakpoint
-- that is, they don't necessarily search the entire sequence.  (Each of the
xxxEnd methods take O(n-i).)

None of these methods are particularly code-intensive, save for some
rewrite-rules-based code that lets most of those methods be defined in terms
of findIndex, without any performance loss.  (In the absence of rewrite
rules, the additional overhead is small.)

Louis Wasserman
wasserman.louis at gmail.com
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/libraries/attachments/20090720/337564ba/attachment.html