RFC: general sequences

[Ross Paterson]

On Mon, May 23, 2005 at 01:29:34PM -0700, John Meacham wrote:
> I would much prefer if all of the data structures had their own
> interface in addition to being instances of a common class. so we could
> have
> 
> import Data.GenSeq -- get the general interface
> import Data.Sequence(Seq) -- all we need is the type name (and the implicitly imported instance)
> 
> This would nicely decouple the development of the general class from
> particular data structures, since they can stand on their own if needed.

This double-barrelled approach (if I've understood you correctly)
is what Edison does.  Actually, the type name isn't quite enough:
if you're using a sequence locally in a function, you need something
more to select the instance you want.  You can't use a type signature,
because you want to specify the type constructor, not its argument.
One possibility is to add a specialized identity:

	idSeq :: Seq a -> Seq a

I proposed a similar large class (though with lots of defaults), last
time this was discussed:

http://www.haskell.org//pipermail/libraries/2004-April/001978.html

At the time, I thought the class was necessary, despite the extra
complications, because none of the available sequence implementations
dominated all the others.  The question is whether we want more than one
instance, now that we have finger trees.  Finger trees seem to dominate
the persistent queue and deque implementations.  They're a little
slower at lookup than skew binary random access lists, but not by much.
Their append is theoretically slower than the O(1) implementations,
but it's very hard to construct an example that shows the difference,
since you have to consume the sequence to make the appends happen.
Non-persistent implementations (e.g. the old 2-list queue) can be a bit
faster, but you have to be very careful how you use them to preserve
their performance.