How lazy is DData.Seq?
ross at soi.city.ac.uk
Sun May 9 02:41:09 EDT 2004
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.
More information about the Libraries