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

[Henning Thielemann]

On Wed, 28 May 2008, Duncan Coutts wrote:

> On Wed, 2008-05-28 at 10:22 +0200, Henning Thielemann wrote:
>> 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.
>
> How about a chunky lazy array? The problem with lazy bytestring is that
> each chunk is strict but if you made each chunk a H98 lazy array that
> might work nicely.

This would actually yield the intended result, but I'm afraid there are 
still too much pointers and allocations around. The nice thing about my 
suggestion is, that no allocation would be needed to construct new 
elements in the list, just running the function to evaluate the next 
elements and advance the cursor. It's a hack of course, like ByteString 
internally is, it's entirely for efficiency reasons.

I interpret your answers as "what you suggest is not obviuous and has 
probably not been proposed before" so I'll take some time for a 
demonstration implementation.