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

Duncan Coutts duncan.coutts at worc.ox.ac.uk
Wed May 28 04:50:13 EDT 2008

On Wed, 2008-05-28 at 10:22 +0200, Henning Thielemann wrote:
> On Wed, 28 May 2008, Bulat Ziganshin wrote:
> > Hello Henning,
> >
> > Wednesday, May 28, 2008, 9:51:28 AM, you wrote:
> >
> >>    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. Whenever an element with an
> >> index beyond the cursor is requested, sufficiently many new elements are
> >> written to the array and the cursor is advanced. This would still allow
> >> the nice tricks for recursive Fibonacci sequence definition. This will
> >> obviously save memory, but can we also expect that it is noticeably faster
> >> than (StrictList a) ?
> >
> > 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.

How about a chunky lazy array? The problem with lazy bytestring is that
each chunk is strict but if you made each chunk a H98 lazy array that
might work nicely.


More information about the Haskell-Cafe mailing list