How lazy is DData.Seq?

[Simon Marlow]

On 18 May 2004 09:24, Robert Will wrote:

> On Tue, 11 May 2004, Simon Marlow wrote:
> 
>> 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.
> 
> Well, Dessy has only 1 and 3 and that for good reason.
> 
> In fact, this discussion does somehow miss the point, since none of
> these three are most "general-purpose Sequences", with a lot of
> unnecessary O(N) operations (e.g. for 'last' and (!!)).

The reason to prefer a sequence with an O(N) 'last' over one with O(log
N) 'last' would be if the O(N) version had lower constant factor
overhead and you didn't need to use the O(N) operations.

Measurements please!

Cheers,
	Simon