RE: How lazy is DData.Seq?

On 10 May 2004 14:56, JP Bernardy wrote:

--- 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.

True, thanks for pointing it out.

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.

O(number of elements) is a tighter constraint than O(number of subtrees). If you build a list with 10 elements using 100 appends, then toList will only require O(10) rather than O(100). If you do more than one toList on the same Seq, you'll notice the difference. But, the tradeoff is strictness in append. It may be that we need multiple versions of Seq, but I suspect that not much would be gained by having all three: 1. ordinary lists with lazy append 2. Seq with O(1) lazy append 3. Seq with O(1) strict append and O(n) toList If we have 1 & 3, then I'm guessing that 2 would be very rarely required. Cheers, Simon