How lazy is DData.Seq?

[Ross Paterson]

On Sat, May 08, 2004 at 03:18:46PM -0400, Dylan Thurston wrote:
> On Sat, May 08, 2004 at 09:10:52PM +0200, Wolfgang Jeltsch wrote:
> > For what do we need a balanced tree?  At least, O(1) concatenation and O(n) 
> > conversion to an ordinary list should also work with unbalanced trees.

You don't need a balanced tree, but the O(n) bound requires the invariant
that no proper subtree is empty.  Otherwise, a tree containing n elements
can be of unbounded size, and take an unbounded time to convert to a list.

> Yes, but DData.Seq is supposed to be a general-purpose library, and I,
> for one, want most operations (e.g., lookup) to be O(log n).

I suspect there is no satisfactory general-purpose sequence implementation
(DData.Seq isn't trying to be one -- it does no balancing.)  A balanced
tree would make most things O(log n), but other implementations give
you O(1) for various subsets of operations (and the smaller the subset,
the smaller the constant factor, as a rule of thumb).  It seems essential
to offer a range of implementations.