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

Ketil Malde ketil at malde.org
Wed May 28 04:40:41 EDT 2008

Henning Thielemann <lemming at henning-thielemann.de> writes:

>>>    We could simulate a list with strict elements, i.e.
>>>      data StrictList a = Elem !a (StrictList a) | End
>>>   by an unboxed array with a cursor to the next element to be evaluated and
>>> a function that generates the next element. [...]

>> looks like lazy.bytestring generalized to any a

> As far as I know, ByteString.Lazy is chunky, that is laziness occurs
> only every 1000th byte or so. My suggestion aims at laziness at
> element level but still more efficiency than a list.

You've lost me at least.

Presumably, you don't want single-element UArrays, so you want a
chunky data structure, but fine-grained laziness.

As far as I can tell, this implies that the UArray is split (at the
position indicated by the cursor?) into an evaluated part, and an
unevaluated part.  Now, if you evaluate one more element, you need to
calculate its value and create a new UArray (and cursor) to replace
the old one(s).  Unless you do the whole thing in the ST or IO monads,
I can't see how you can implement this efficiently. 

Where did I misunderstand you?  Perhaps you can sketch some code?

If I haven't seen further, it is by standing in the footprints of giants

More information about the Haskell-Cafe mailing list