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

Don Stewart dons at galois.com
Wed May 28 13:50:05 EDT 2008

> I wonder whether the following idea has been investigated or implemented 
> somewhere:
>   We could simulate a list with strict elements, i.e.
>     data StrictList a = Elem !a (StrictList a) | End

I've used the above structure itself, as a useful alternative to fully
lazy lists.
>  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) ?

That sounds a lot like the semi-eager structure, Lazy ByteStrings,
which do cache sized chunks of evaluation before suspending.
With the cursor in place, it would behave more like the buffer
abstraction to lazy bytestrings in Data.Binary?

-- Don

More information about the Haskell-Cafe mailing list