sequences (was Re: Specify array or list size?)

[Ross Paterson]

On Sat, May 07, 2005 at 10:56:11PM +0200, Benjamin Franksen wrote:
> It would be a great improvement if Haskell's standard library (including the 
> Prelude) would provide a uniform framework for collections, and in particular 
> sequences (linear collections, indexed by natural numbers), and there should 
> be standard implementations that don't favour operations on the left end over 
> those on the right end. It is a shame that a language like Haskell doesn't 
> even have a Deque (double ended queue) in the its standard library.
>
> Robert Will has proposed a new unified standard for collections (as well as 
> some default implementations) with above properties (and a lot more). IMHO, 
> his work is (at least) a very good starting point and deserves more 
> attention.

There was some discussion of this on the libraries list last year:

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

(look for "sequences").  The background was that most people (Robert was
an exception) thought that a general collection framework wasn't the way
to go, partly because the proposals needed non-H98 features but mainly
because there was no clear best choice, so a few concrete implementations
(Data.Set, Data.Map, Data.IntSet and Data.IntMap) were added.  However
sequences can be described by a H98 class, and are also the area where
a class with several instances is most useful.