[Haskell-cafe] Suitable structure to represents lots of similar lists

Ketil Malde ketil at malde.org
Thu Apr 8 10:43:48 EDT 2010

Dan Piponi <dpiponi at gmail.com> writes:

> I have a situation where I have a bunch of lists and I'll frequently
> be making new lists from the old ones by applying map and filter.

(While keeping the old ones around, I presume?)

One option (or source of inspiration) might be lazy bytestrings, which
are stored as lists of chunks, each chunk being a strict bytesting.  A
strict bytestring is a pointer to an array, an offset and a length.

Thus, your initial lists could be contigous arrays, derivied list would
be a sequence of chunks, each chunk either containing substrings of the
original list or modified elements.  So if f is id for positions 0..3
and 9..10, you could have:

  orig = Chunk (PS v 0 10) Empty
  map' f orig 
  => Chunk (PS v 0 3) (Chunk (PS w 0 4) (Chunk (PS v 9 10) Empty))

Possibly vector generalizes this to datatypes beyond Word8, I haven't

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

More information about the Haskell-Cafe mailing list