[Haskell-cafe] Lazy lists simulated by unboxed mutable arrays
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.
> 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