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

[Henning Thielemann]

On Wed, 28 May 2008, Ketil Malde wrote:

> Ketil Malde <ketil at malde.org> writes:
>
>> You've lost me at least.
>
> ...but perhaps I can find my way back on my own?
>
> Today, you can choose between Array, with lazy elements, or UArray,
> with strict elements.

... and ByteStrings, where in principle the elements could be initialized 
in any order, but actually the ByteString functions prefer a left-to-right 
order. They are clearly intended as list replacement, so my proposed 
"cursor arrays" would do as well.

> Lazy arrays have the elements defined in advance, strict ones have
> them calculated in advance - with the tremendous advantage of being
> able to eliminate the pointer for each element.  Otherwise a pointer
> is needed to point to a potentially unevaluated thunk.
>
> Perhaps there is a middle ground here, if you add the restriction that
> the elements are generated in order?

Exactly. Thus I compared my suggestion with element-strict lists.

>  This way, you only need one pointer to an unevaluated thunk (which will 
> yield all remaining elements as needed), and an unboxed array can 
> contain the calculated values.

That's it!

> This would be very nice for e.g. sequence alignment, where the
> alignment matrix is self-referencing, but the pointers represent a
> very real cost to an already expensive (resource-intesive) solution.

I'm thinking about signal processing, where data is processed in time 
order in many cases.


Thank you for clarification!