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

[wren ng thornton]

Don Stewart wrote:
> wagner.andrew:
> > > 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.

-- 
Live well,
~wren