How lazy is DData.Seq?

[Dylan Thurston]

On Sat, May 08, 2004 at 09:10:52PM +0200, Wolfgang Jeltsch wrote:
> Am Samstag, 8. Mai 2004 20:58 schrieben Sie:
> > Yes, it's necessary, if you want to maintain any sort of balanced tree
> > (which is crucial for efficiency).  In 'append as bs', you need to know
> > how large 'as' and 'bs' are in order to construct the balanced
> > structure.
> 
> 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.

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).

If you want unbalanced trees, go ahead and code it yourself; it's very
easy, much easier than doing balancing correctly.

Peace,
	Dylan
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: Digital signature
Url : http://www.haskell.org//pipermail/libraries/attachments/20040508/19087d1d/attachment.bin