[Haskell-cafe] The difficulty of designing a sequence class

[Duncan Coutts]

On Tue, 2006-08-01 at 14:37 +0400, Bulat Ziganshin wrote:
> Hello Brian,
> 
> Tuesday, August 1, 2006, 4:23:53 AM, you wrote:
> 
> >> That's a tough call to make. Changing the kind of Sequence to * from *
> >> -> * means losing the Functor, Monad, and MonadPlus superclasses and
> >> all the various maps and zips.
> 
> > But there's no option if you want to be able to support non-polymorphic
> > sequences like Data.ByteString etc. I think the Functor class is just 
> > fundamentally too limited - it assumes the whole world is polymorphic and it
> > isn't.
> 
> it's possible, at least in principle, to make ByteString parametric
> class:
> 
> data PlainSequence a = ...
> 
> type ByteString = PlainSequence Word8
> 
> and then rewrite all ByteString functions so that they will work with
> elements of any type, not just Word8

Much of the performance advantages that we can get are due to the
special representation and knowing the types involved. This would not
work for arbitrary types.

For one thing all the performance advantages of using a packed
representation would be lost as we would have to use pointers to boxed
objects rather than flat arrays of bytes.

We can use low level standard C functions like memchr because we know
the representation.

There is certainly a place for a general strict sequence type but there
is also a need for efficient handling of big chunks of bytes. It'd be
even better if the special case representation collections could fit
into a general framework.

Duncan