Re: How lazy is DData.Seq?

--- Wolfgang Jeltsch wrote:

Am Montag, 10. Mai 2004 15:56 schrieb JP Bernardy:

...

--- Simon Marlow 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?

To be precise: Making fromList guarantee that "the Many constructor never has [] as argument" is a part of an implementation that gives the O(n) behaviour for toList. It does not make append strict. A strict append is necessary, in any case, for the O(n) behaviour.

...

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.

Yet, toList might be evaluated more than once for a given sequence. Cheers, JP. __________________________________ Do you Yahoo!? Win a $20,000 Career Makeover at Yahoo! HotJobs http://hotjobs.sweepstakes.yahoo.com/careermakeover