[Haskell-cafe] Lazy lists simulated by unboxed mutable arrays

Henning Thielemann lemming at henning-thielemann.de
Wed May 28 04:22:54 EDT 2008

On Wed, 28 May 2008, Bulat Ziganshin wrote:

> Hello Henning,
> Wednesday, May 28, 2008, 9:51:28 AM, you wrote:
>>    We could simulate a list with strict elements, i.e.
>>      data StrictList a = Elem !a (StrictList a) | End
>>   by an unboxed array with a cursor to the next element to be evaluated and
>> a function that generates the next element. Whenever an element with an
>> index beyond the cursor is requested, sufficiently many new elements are
>> written to the array and the cursor is advanced. This would still allow
>> the nice tricks for recursive Fibonacci sequence definition. This will
>> obviously save memory, but can we also expect that it is noticeably faster
>> than (StrictList a) ?
> looks like lazy.bytestring generalized to any a

As far as I know, ByteString.Lazy is chunky, that is laziness occurs only 
every 1000th byte or so. My suggestion aims at laziness at element level 
but still more efficiency than a list.

More information about the Haskell-Cafe mailing list