[Haskell-cafe] Structural sharing in haskell data structures?
dons at galois.com
Tue May 12 17:33:32 EDT 2009
> So I've been reading a lot about a (relatively) new language called Clojure.
> One of its goals is to make concurrency easier via a built-in home-grown STM.
> Anyway, one of the ways it tries to do this is to have completely immutable
> data structures. Every time I read a tutorial about this in Clojure, it says
> "...yes, it sounds awful to think that your whole data structure gets copied
> every time you want to make a change to it, but it's sane because of a
> technique called structural sharing". Yet every time I hear immutability talked
> about in Haskell, what I hear is "...yes, it sounds awful to think that your
> whole data structure gets copied every time you want to make a change to it,
> but it's sane because of laziness...unless you need the whole data
> structure...". So I'm just curious, does GHC use structural sharing or
> something similar? Do other implementations? Does it matter?
Purity allows our data structures to have a lot of sharing.
This is separate to laziness.
Laziness lets us build up interesting structures that have unusual
Actually, what kind of persistant structures does Clojure have at this
stage? I was under the impression they were reusing Java data
structures. E.g. some of the nicer ones on hackage are zippers, patricia
tries, finger trees, which I can't imaging have been ported.
More information about the Haskell-Cafe