[Haskell-cafe] Structural sharing in haskell data structures?
wren ng thornton
wren at freegeek.org
Wed May 13 00:19:23 EDT 2009
Don Stewart wrote:
> > > Purity allows our data structures to have a lot of sharing.
> > > This is separate to laziness.
> > Ah, so haskell does do it. Interesting that it so rarely comes up, whereas it's
> > frequently mentioned in clojure.
> I think it is just assumed, since that's been the case for 20 years or
> more now. Sharing is kind of exciting to the ex-Java people looking at
> Clojure, I guess, since it's a new idea. So they talk about it.
So far as I know, all immutable languages do it. Like Don, I think the
reason it's emphasized so much in Clojure is because of trying to
convert the Java crowd and introducing them to immutability. With
mutable languages you have to clone _everything_ for fear of later
changes affecting earlier copies. Because of this, folks used to mutable
languages often erroneously suppose that immutable languages do the same
thing. There's a lot of FUD in the mainstream about
declarative/immutable/functional languages and their performance behavior.
The idea is simple and you can do it in mutable languages perfectly well
(clone the changed part of the spine, point to old substructure) so long
as you're careful not to do mutation, e.g. by marking everything
"final". You don't see it as much in mutable languages because people
get squeamish about the first step: clone the changed spine; they'd much
rather mutate it. In heavily GCed languages like Haskell allocation and
collection is cheap, so we don't mind too much; but in Java and the
like, both allocation and collection are expensive so the idea of cheap
throwaway objects is foreign.
More information about the Haskell-Cafe