How lazy is DData.Seq?

[Wolfgang Jeltsch]

Am Montag, 10. Mai 2004 15:56 schrieb JP Bernardy:
> --- Simon Marlow <simonmar at microsoft.com> wrote:
> > Ross's point about requiring append to be strict in order to guarantee
> > O(n) toList is a good one.  In fact, the current implementation isn't
> > quite correct: either fromList should be strict, or append should check
> > for an empty Many constructor.
>
> That's what exists in the current published version (on my "web page"):
> fromList guarantees that the Many constructor never has [] as argument.

Is it right that making this guarantee results in the strictness I would like 
to avoid?

> Anyways, 'toList' will still be O(m) where m = number of subtrees. Moreover,
> I hardly expect more that O(n) empty subtrees in a sequence.

It's theoretically possible that m is much larger than n.  But since you need 
at least O(m) time to construct a Seq with m subtrees¹) the total time of Seq 
construction plus conversion is asymptotically the same as without full 
lazyness.
__________
¹) Well, exceptions could be cases like fix ([] `append`) which might be 
constructable in constant time.

> [...]

Wolfgang