How lazy is DData.Seq?
cwitty at newtonlabs.com
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
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.
More information about the Libraries