4 ms·
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
by rkangel 4y ago
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 4y agoSo copy-on-write basically?
- hgsgm 4y agoNo, there is no "write" because the old value never chnages. It's "create an overlay on write"
- deleted 4y ago[deleted]
- arc-in-space 4y agoCopy-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 4y agoWell, 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.
- herbstein 4y agoYes, 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.
- rkangel 4y agoNo, 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".