2010/8/17 Johan Tibell <johan.tibell@gmail.com>
The second question is this: say I have some functions working with a data type, say a graph.

Some of them might want to change the graph and return a new graph as a result.
If they change say only one graph node, it would be extremely bad for performance if the whole graph got copied
any time such a change takes place. Is the compiler smart enough to make the code only copy the parts
that have changed (copying lazily, so to speak)? Is that even possible?

Since the graph is immutable most of the nodes in the new graph are shared with nodes in the old graph. This is know as path copying and is everywhere persistent ("immutable") data structures are used. Updating a data structure (e.g. a tree) typically requires O(log n) nodes to be copied.

So that means the compiler figures this out for my own data structures, or do I have to take care that copying is done this way?
Sorry for my ignorance, I'm still learning :)