[rkangel]

I don't know about Haskell particularly but the underlying implementation of data structures in pure languages is sometimes more complicated to enable this sort of thing. For example, the new updated copy of the map may refer to the "old" map for most of its data, thereby making it cheap to have both.

[api]

So copy-on-write basically?

[herbstein]

Yes, but with granularity at the "node" level instead of being across the whole container. Imagine a linked list.

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.

[arc-in-space]

Copy-on-write generally refers to copying everything on every write; this is a persistent data structure, which can do updates while only copying a small part of itself. Same purpose as COW, but more efficient for larger data structures we want to make lots of small updates on.

[Joker_vD]

Well, yeah, only there ain't any writes (and therefore, no copying).

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.

[rkangel]

No, because you don't copy the whole structure. You create a new partial structure.

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".

[hgsgm]

No, there is no "write" because the old value never chnages. It's "create an overlay on write"