Re: How lazy is DData.Seq?

Am Samstag, 8. Mai 2004 20:58 schrieben Sie:

On Sat, May 08, 2004 at 08:28:37PM +0200, Wolfgang Jeltsch wrote:

...

Am Samstag, 8. Mai 2004 18:37 schrieben Sie:

...

--- Wolfgang Jeltsch wrote:

...

Hello,

I would suspect that in DData.Seq the result of head (singleton 'a' `append` undefined) is 'a' but instead it is _|_. Why is this the case?

I have the invariant that sublists are not empty. There is, for example:

append as None = as

Is this necessary/desirable? I have an application where I think that it can be important for efficiency that the above expression evaluates to 'a'. So I would like it to not result in _|_.

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.

[...]

Peace, Dylan

Wolfgang