How lazy is DData.Seq?
dpt at exoskeleton.math.harvard.edu
Sat May 8 16:18:46 EDT 2004
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.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Size: 189 bytes
Desc: Digital signature
Url : http://www.haskell.org//pipermail/libraries/attachments/20040508/19087d1d/attachment.bin
More information about the Libraries