How lazy is DData.Seq?

[Wolfgang Jeltsch]

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 <wolfgang at jeltsch.net> 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