How lazy is DData.Seq?
wolfgang at jeltsch.net
Sat May 8 22:10:52 EDT 2004
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
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.
More information about the Libraries