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

[Henning Thielemann]

On Wed, 28 May 2008, Don Stewart wrote:

>>  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?

Can you code
    fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
   with hte 'buffer'? I'm afraid you cannot simultaneously read and write 
from 'buffer', cannot 'drop' and so on, right? What I have in mind is some 
combination of a 'Data.Stream' for generating the data (playing the role 
of the unevaluated thunk), a memory chunk for buffering calculated data 
and a wrapper which provides a view on a sub-array.

Ideally 'fibs' would be translated to something like

    int *p = malloc ...;
    int *p0 = p; *p = 0; p++;
    int *p1 = p; *p = 1; p++;
    int *p2 = p;
    int i=n;
    while (i>0) {
       *p2 = *p0 + *p1;
       p0++; p1++; p2++;
       i--;
    }

I'm not sure, whether the compiler can eliminate the last bit of laziness 
that would remain in a 'cursor array'.