[Haskell-cafe] Structural sharing in haskell data structures?

[Don Stewart]

wagner.andrew:
> 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
sharing.

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.

-- Don