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

On Wed, 28 May 2008, Ketil Malde wrote:

Ketil Malde 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!