[Haskell-cafe] Very large data structures in the heap

Joachim Breitner mail at joachim-breitner.de
Tue Feb 17 13:45:08 UTC 2015

Hallo Olaf,

Am Dienstag, den 17.02.2015, 11:05 +0100 schrieb Dr. Olaf Klinke:
> I have a function that builds a (cyclic) data structure for searching 
> text. The resulting object can be serialized and re-built. Real-world 
> problems would, however, result in a tree with about 10^9 nodes. I take it 
> that standard data type declarations are not very memory-efficient, so my 
> (fully evaluated) search tree would not fit into memory as a heap object. 
> Its serialised form should be of tractable size, e.g. by storing an array 
> of labels and the tree structure as a bit array of parentheses.

you say cyclic, but you also say it is a tree. Do you mean that it
locally looks like a tree, but is in fact a graph, due to

> I'd like to separate serialization (IO) from traversal of the stucture 
> (pure), but how can one avoid the entire heap object from being built? 
> Can lazyness be exploited?

I would say „yes“, but need more information for a more concrete
answer :-)

Grüße aus Karlsruhe,

Joachim “nomeata” Breitner
  mail at joachim-breitner.dehttp://www.joachim-breitner.de/
  Jabber: nomeata at joachim-breitner.de  • GPG-Key: 0xF0FBF51F
  Debian Developer: nomeata at debian.org

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 819 bytes
Desc: This is a digitally signed message part
URL: <http://mail.haskell.org/pipermail/haskell-cafe/attachments/20150217/eb935a70/attachment.sig>

More information about the Haskell-Cafe mailing list