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

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

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!

More information about the Haskell-Cafe mailing list