How lazy is DData.Seq?

Simon Marlow simonmar at
Wed May 19 11:26:30 EDT 2004

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!


More information about the Libraries mailing list