What black magic is this? Is the article just glossing over the cost of a copy or does Haskell do something weird here to avoid the copy while retaining both versions?
Conversely, in the case where something like a list is modified in entirety (e.g. with a `map` function), if the compiler can determine that the original is no longer needed, it can run the map operation in place - much like you might do on an array in C - avoiding the need for a second copy of the structure in-memory.
From https://en.wikipedia.org/wiki/Persistent_data_structure
Clojure leverages the same data structure for (at least) four basic types; list, map, vector and set, and the following article explains it well with a pretty graph/picture too: https://practical.li/clojurescript/clojure-syntax/persistent...
The simplest example would be with linked lists, I suppose: you have a list A->B->C, then you take the B->C sublist and prepend X to it, so you now have X->B->C, but A->B->C is still around, and "B->C" part is shared between those.
If you add prepend an element to an existing list, no copy is necessary. It's just a new head with the tail being the original list. That's an easy case.
If you add a node in the middle of the list you can still share the unchanged tail between the two slightly different prefix sequences.
E.g. let's say you create a map with keys A and B. You then insert a new key C. In memory you might have two objects: One is the origi al map with A and B and the other has "Key C and a ref to the first map".
For example, in a basic binary search tree implementation of a map (using C-ish syntax for those who don't know a functional language):
struct Node {
String key;
int value;
Node left;
Node right;
}
Node set(Node n, String key, int value) {
if(n == null) {
return new Node { key = key, value = value, left = null, right = null };
}
if(key < n.key) {
return new Node {
key = n.key,
value = n.value,
left = set(n.left, key, value),
right = n.right
};
}
if(key > n.key) {
return new Node {
key = n.key,
value = n.value,
left = n.left,
right = set(n.right, key, value)
};
}
return new Node { key = key, value = value, left = n.left, right = n.right };
}
Of course, if this is your implementation of set(), the tree won't be perfectly-balanced, so a production implementation of a tree-based map needs tree-rebalancing (as well as memory-reordering and compacting for cache locality). These extra constraints typically mean less of the tree can be re-used, but the percentage of nodes which can be reused remains high.
You have an object. When you want to apply a patch, you create a new object that contains just your patch, plus a reference to the old obejct. DiffArray is the simple common example. It's fast enough when the diffs are small, but terrible when there are many diffs in series, creating a deep stack of references.
It's not obscure. $PATH and the /bin,/usr/bin, /usr/local/bin, $HOME/bin dirs on Linux work the same way.
And GHC exploits that liberty.