How lazy is DData.Seq?

Carl Witty cwitty at
Mon May 10 18:02:17 EDT 2004

On Mon, 2004-05-10 at 12:46, Wolfgang Jeltsch wrote:
> > 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.

If we're talking about "theoretically possible": it's also possible that
somebody converts to a list multiple times, or converts multiple
subtrees to lists.

Carl Witty

More information about the Libraries mailing list