[Haskell-cafe] Large data structures

Matthew Brecknell haskell at brecknell.org
Mon Dec 11 20:53:54 EST 2006


> > No.  Haskell's lists are linked lists, enlarge creates a single new link
> > without modifying (and copying) the original.
>
> Thanks. Is there a way to mimic this behaviour with my own code?

Yes. Take a look at Data.Map. This data structure provides various
operations which create a new map from an old one in O(log n) time, by
splicing bits of the old map into the new one. Importantly, performing
any of these operations does not destroy the old map if your code still
references it. On the other hand, if your code drops references to the
old map, then the garbage collector can reclaim any branches of the old
map not used in the new one. You may also be interested in this paper:

http://www.cs.cmu.edu/~rwh/theses/okasaki.pdf



More information about the Haskell-Cafe mailing list