How lazy is DData.Seq?

[Simon Marlow]

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

> --- Simon Marlow <simonmar at microsoft.com> 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