Persistence is defined in terms of the interface to an abstract data type. When I do a write operation on a data structure, I get a new version back, and all re

Persistence is defined in terms of the interface to an abstract data type. When I do a write operation on a data structure, I get a new version back, and all read operations on the old version still return the same values. version1 = make_record(x = 10) v1_x = get_x(version1) ; 10 version2 = update(version1, x = 20) v2_x = get_x(version2) ; 20 get_x(version1) == v1_x ; true The update operation is free to mutate the original data structure however it likes, so long as from the outside the read operations look the same. This freedom to mutate is often used to make efficient persistent data structures by re-using the same memory but tagging different parts of it with a version. version1 = make_record(x = 10) +--------+--------+ +-----+ +--------+---------+--------+ version1 ->| tag: 1 | data: -+----->| x: -+-->| tag: 1 | val: 10 | next: -+---| +--------+--------+ +-----+ +--------+---------+--------+ version2 = update(version1, x = 20) +--------+--------+ +-----+ +--------+---------+--------+ +--------+---------+--------+ version1 ->| tag: 1 | data: -+--+-->| x: -+-->| tag: 1 | val: 10 | next: -+-->| tag: 2 | val: 20 | next: -+---| +--------+--------+ | +-----+ +--------+---------+--------+ +--------+---------+--------+ +--------+--------+ | version2 ->| tag: 2 | data: -+--+ +--------+--------+ When version2 is created, it really just appends to the same data structure as version1, but tags the cell as a new version. When you do get_x(version1) it follows down the list, finds the cell with tag 1, and returns it's value. When you do get_x(version2) it follows down the list until the cell with tag 2 and returns it's value. From the outside, get_x(version1) still returns the same value before and after the update, but the data structure it refers to has been mutated underneath it. There are also ways to use structural sharing in persistent data structures where the you don't do any mutation of the old versions. For examples of this, see the linked article. Functional data structures forbid mutation. This means they must be persistent, because update operations have to return new data structures, and the old data structures aren't allowed to be mutated so by definition all read operations on them still return the same values. Functional data structures end up forming a subset of fully persistent data structures. They're a useful category for a lot of the same reasons people are touting pure functional languages are useful. For instance, you never have to worry about locks when you have concurrent access. With the mutating example above, if one thread does update(version1, x = 20) and another does update(version1, x = 30) I need to coordinate which one gets tag 2 and which one gets tag 3. Persistent data structures are the more general concept, functional data structures are a specialized subset.