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?

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

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