Persistent data structure

2775: 2682: 3005: 2701: 263:

function. The potential function will only drop, however, if the old node isn't reachable in the new tree. But it is known that it isn't reachable in the new tree—the next step in the algorithm will be to modify the node's parent to point at the copy. Finally, it is known that the copy's modification box is empty. Thus, replaced a full live node has been replaced with an empty live node, and ϕ goes down by one.) The final step fills a modification box, which costs O(1) time and increases ϕ by one.

3301:. The Redux library is inspired by the state management pattern used in the Elm programming language, meaning that it mandates that users treat all data as persistent. As a result, the Redux project recommends that in certain cases users make use of libraries for enforced and efficient persistent data structures. This reportedly allows for greater performance than when comparing or making copies of regular JavaScript objects. 236:

modification is performed directly on the new node, without using the modification box. (One of the new node's fields is overwritten and its modification box stays empty.) Finally, this change is cascaded to the node's parent, just like path copying. (This may involve filling the parent's modification box, or making a copy of the parent recursively. If the node has no parent—it's the root—it is added the new root to a

3236: 3305:

similar to those in Clojure to JavaScript. Immer.js brings an interesting approach where one "creates the next immutable state by mutating the current one". Immer.js uses native JavaScript objects and not efficient persistent data structures and it might cause performance issues when data size is big.

160:

fields as an ephemeral node, along with space for an arbitrary number of extra field values. Each extra field value has an associated field name and a version stamp which indicates the version in which the named field was changed to have the specified value. Besides, each fat node has its own version

3304:

One such library of persistent data structures Immutable.js is based on the data structures made available and popularized by Clojure and Scala. It is mentioned by the documentation of Redux as being one of the possible libraries that can provide enforced immutability. Mori.js brings data structures

3125:

and therefore does not allow for mutation. Therefore, all data structures in the language are persistent, as it is impossible to not preserve the previous state of a data structure with functional semantics. This is because any change to a data structure that would render previous versions of a data

207:

time. Modification time and space are bounded by the size of the longest path in the data structure and the cost of the update in the ephemeral data structure. In a Balanced Binary Search Tree without parent pointers the worst case modification time complexity is O(log n + update cost). However, in

161:

stamp, indicating the version in which the node was created. The only purpose of nodes having version stamps is to make sure that each node only contains one value per field name per version. In order to navigate through the structure, each original field value in a node has a version stamp of zero.

3317:

Some Prolog systems nevertheless do provide destructive operations like setarg/3, which might come in different flavors, with/without copying and with/without backtracking of the state change. There are cases where setarg/3 is used to the good of providing a new declarative layer, like a constraint

2627:

There also exist persistent data structures which use destructive operations, making them impossible to implement efficiently in purely functional languages (like Haskell outside specialized monads like state or IO), but possible in languages like C or Java. These types of data structures can often

235:

Modifying a node works like this. (It is assumed that each modification touches one pointer or similar field.) If the node's modification box is empty, then it is filled with the modification. Otherwise, the modification box is full. A copy of the node is made, but using only the latest values. The

1493:

We can notice that what really takes time in the data structure used in the naïve method is that whenever we move from a strip to the next, we need to take a snap shot of whatever data structure we are using to keep things in sorted order. We can notice that once we get the segments that intersect

1264:

in a dictionary. When the vertical line sweeps the line segments, whenever it passes over the left endpoint of a segment then we add it to the dictionary. When it passes through the right endpoint of the segment, we remove it from the dictionary. At every endpoint, we save a copy of the dictionary

1189:

end points. No segment begins and ends in the strip. Every segment either it doesn't touch the strip or it completely crosses it. We can think of the segments as some objects that are in some sorted order from top to bottom. What we care about is where the point that we are looking at fits in this

227:

In each node, one modification box is stored. This box can hold one modification to the node—either a modification to one of the pointers, or to the node's key, or to some other piece of node-specific data—and a timestamp for when that modification was applied. Initially, every node's modification

247:, given any time t, at most one modification box exists in the data structure with time t. Thus, a modification at time t splits the tree into three parts: one part contains the data from before time t, one part contains the data from after time t, and one part was unaffected by the modification. 3145:

family, Clojure contains an implementation of a linked list, but unlike other dialects its implementation of a linked list has enforced persistence instead of being persistent by convention. Clojure also has efficient implementations of persistent vectors, maps, and sets based on persistent hash

262:

Each modification involves some number of copies, say k, followed by 1 change to a modification box. Consider each of the k copies. Each costs O(1) space and time, but decreases the potential function by one. (First, the node to be copied must be full and live, so it contributes to the potential

124:

The size of this data structure is bounded by the number of elements stored in the structure that is O(m). The insertion of a new maximal element is done in constant O(1) expected and amortized time. Finally query to find an element can be done in this structure in O(log(log n)) worst-case time.

3313:

Prolog terms are naturally immutable and therefore data structures are typically persistent data structures. Their performance depends on sharing and garbage collection offered by the Prolog system. Extensions to non-ground Prolog terms are not always feasible because of search space explosion.

3221:

is not particularly functional. Despite this, the core JDK package java.util.concurrent includes CopyOnWriteArrayList and CopyOnWriteArraySet which are persistent structures, implemented using copy-on-write techniques. The usual concurrent map implementation in Java, ConcurrentHashMap, is not

549:

The credit scheme should always satisfy the following invariant: Each row of each active table stores one credit and the table has the same number of credits as the number of rows. Let us confirm that the invariant applies to all the three operations CREATE-NODE, CHANGE-EDGE and CHANGE-LABEL.

231:

Whenever a node is accessed, the modification box is checked, and its timestamp is compared against the access time. (The access time specifies the version of the data structure being considered.) If the modification box is empty, or the access time is before the modification time, then the

274:

Path copying is one of the simple methods to achieve persistency in a certain data structure such as binary search trees. It is nice to have a general strategy for implementing persistence that works with any given data structure. In order to achieve that, we consider a directed graph

3064:

where "Insert, search and delete times are small and constant, independent of key set size, operations are O(1). Small worst-case times for insert, search and removal operations can be guaranteed and misses cost less than successful searches". This data structure was then modified by

557:

CHANGE-EDGE: There are two cases to consider. The first case occurs when there is still at least one empty row in the table. In this case one credit is used to the newly inserted row. The second case occurs when the table is full. In this case the old table becomes inactive and the

1449:. In this data structure, the space is the issue since if we assume that we have the segments structured in a way such that every segment starts before the end of any other segment, then the space required for the structure to be built using the naïve method would be 259:ϕ, where ϕ(T) is the number of full live nodes in T . The live nodes of T are just the nodes that are reachable from the current root at the current time (that is, after the last modification). The full live nodes are the live nodes whose modification boxes are full. 1116:

We start with a vertical line segment that starts off at infinity and we sweep the line segments from the left to the right. We take a pause every time we encounter an end point of these segments. The vertical lines split the plane into vertical strips. If there are

155:

The fat node method is to record all changes made to node fields in the nodes themselves, without erasing old values of the fields. This requires that nodes be allowed to become arbitrarily “fat”. In other words, each fat node contains the same information and

3099:

Most implementations of persistent hash array mapped tries use a branching factor of 32 in their implementation. This means that in practice while insertions, deletions, and lookups into a persistent hash array mapped trie have a computational complexity of

182:, the right version at each node must be found as the structure is traversed. If "m" modifications were to be made, then each access operation would have O(log m) slowdown resulting from the cost of finding the nearest modification in the array. 2585:, and new nodes can be added in front of it. The tail will not be duplicated, instead becoming shared between both the old list and the new list. So long as the contents of the tail are immutable, this sharing will be invisible to the program. 146:

for any updates to the data structure. This is an inefficient technique because the entire backing data structure must be copied for each write, leading to worst case O(n·m) performance characteristics for m modifications of an array of size n.

534:

In order to find the efficiency of the scheme proposed above, we use an argument defined as a credit scheme. The credit represents a currency. For example, the credit can be used to pay for a table. The argument states the following:

232:

modification box is ignored and only the normal part of the node is considered. On the other hand, if the access time is after the modification time, then the value in the modification box is used, overriding that value in the node.

96:. In addition, a data structure can be referred to as confluently persistent if, in addition to being fully persistent, two versions of the same data structure can be combined to form a new version which is still fully persistent. 2760:

that all subnodes contained in the left subtree have a value that is less than or equal to the value stored in the node, and subnodes contained in the right subtree have a value that is greater than the value stored in the node.

3326:

The Scala programming language promotes the use of persistent data structures for implementing programs using "Object-Functional Style". Scala contains implementations of many persistent data structures including linked lists,

169:

With using fat node method, it requires O(1) space for every modification: just store the new data. Each modification takes O(1) additional time to store the modification at the end of the modification history. This is an

194:

back through the data structure: all nodes that pointed to the old node must be modified to point to the new node instead. These modifications cause more cascading changes, and so on, until the root node is reached.

3192:

implementation that takes advantage of the persistent nature of Elm data. As of 2016 it was reported by the developers of Elm that this virtual DOM allows the Elm language to render HTML faster than the popular

786:

where the additional d factor comes from updating the inedges at other nodes. Therefore, the amount of work required to complete a sequence of operations is bounded by the number of tables created multiplied by

3339:

Because persistent data structures are often implemented in such a way that successive versions of a data structure share underlying memory ergonomic use of such data structures generally requires some form of

3184:

is purely functional like Haskell, which makes all of its data structures persistent by necessity. It contains persistent implementations of linked lists as well as persistent arrays, dictionaries, and sets.

2018:. This will provide a new tree whose root is a copy of the root of the original tree. Then we perform the deletion on the new tree. We will end up with 2 versions of the tree. The original one which contains 46:, as their operations do not (visibly) update the structure in-place, but instead always yield a new updated structure. The term was introduced in Driscoll, Sarnak, Sleator, and Tarjan's 1986 article. 1674:. The trick is that since each copy differs from the previous one by only one insertion or deletion, then we need to copy only the parts that change. Let us assume that we have a tree rooted at 1033: 3084:

to transform their lookup key into a (usually 32 or 64 bit) integer. The path down the tree is then determined by using slices of the binary representation of that integer to index into a

2303: 2220: 57:

if every version can be both accessed and modified. If there is also a meld or merge operation that can create a new version from two previous versions, the data structure is called

719: 2515: 935: 3080:

in that they store nodes hierarchically and retrieve them by following a path down to a particular element. The key difference is that Hash Array Mapped Tries first use a

3108:), for most applications they are effectively constant time, as it would require an extremely large number of entries to make any operation take more than a dozen steps. 1167: 554:

CREATE-NODE: It acquires two credits, one is used to create the table and the other is given to the one row that is added to the table. Thus the invariant is maintained.

2465: 2421: 2164: 2120: 1976: 1447: 865: 2551: 1483: 821: 784: 2628:

be avoided with a different design. One primary advantage to using purely persistent data structures is that they often behave better in multi-threaded environments.

1672: 1612: 1552: 88:

among each version of the data structure. In the fully persistent model, both updates and queries are allowed on any version of the data structure. In some cases the

110:

One of the technique is by using randomized version of Van Emde Boas Tree which is created using dynamic perfect hashing. This data structure is created as follows:

2377: 2330: 2247: 1639: 1579: 1519: 1262: 1235: 673: 646: 117:

The tree is pruned by dividing the m elements into buckets of size log(log n) such that the elements of bucket 1 is smaller than the elements of bucket 2 and so on.

748: 3014:) persists. Second, many common nodes are shared between the old tree and the new tree. Such persistence and sharing is difficult to manage without some form of 608: 582: 433: 395: 2350: 2076: 2056: 2036: 2016: 1996: 1932: 1912: 1892: 1872: 1852: 1832: 1812: 1792: 1772: 1752: 1732: 1712: 1692: 1403: 1383: 1363: 1343: 1323: 1303: 1283: 1208: 1187: 1135: 1108:(if any). We will start by solving the Next Element Search using the naïve method then we will show how to solve it using the persistent data structure method. 1106: 1086: 1066: 955: 885: 3133:

In its standard library Haskell has efficient persistent implementations for linked lists, Maps (implemented as size balanced trees), and Sets among others.

2621: 224:

came up with a way to combine the techniques of fat nodes and path copying, achieving O(1) access slowdown and O(1) modification space and time complexity.

355:

Any of the above operations is performed at a specific time and the purpose of the persistent graph representation is to be able to access any version of

84:

In the partial persistence model, a programmer may query any previous version of a data structure, but may only update the latest version. This implies a

3294: 614:

credits left are used for updating the tables of the other vertices that need to point to the new table. We conclude that the invariant is maintained.

1068:

non intersecting line segments that don't cross each other that are parallel to the x-axis. We want to build a data structure that can query a point

489:

is full: In this case we need to create a new table. We copy the last row of the old table into the new table. We need to loop in the array inedges(

3538: 255:

Time and space for modifications require amortized analysis. A modification takes O(1) amortized space, and O(1) amortized time. To see why, use a

291:

of outgoing edges that are represented by pointers. Each vertex has a label representing the data. We consider that a vertex has a bounded number

4436: 2648:, are purely functional because once a node in the list has been allocated, it cannot be modified, only copied, referenced or destroyed by the 3352:. In some platforms where persistent data structures are used it is an option to not use garbage collection which, while doing so can lead to 3053:

that will preserve previous versions of itself on any updates. It is often used to implement a general purpose persistent map data structure.

3648: 2687:

where a circle indicates a node in the list (the arrow out representing the second element of the node which is a pointer to another node).

610:

credits. One credit will be used for the creation of the new table. Another credit will be used for the new row added to the table and the

190:

With the path copying method a copy of all nodes is made on the path to any node which is about to be modified. These changes must then be

120:

The maximal element in each bucket is stored in the stratified tree and each bucket is stored in the structure as an unordered linked list.

3157:

which gives the benefit of making them freely shareable between threads with cheap aliases, easy to fabricate, and language independent.

2609: 3552:

Brodal, Gerth Stølting; Makris, Christos; Tsichlas, Kostas (2006), "Purely Functional Worst Case Constant Time Catenable Sorted Lists",

397:

rows. Each row contains in addition to the pointers for the outgoing edges, a label which represents the data at the vertex and a time

3153:

The designers of the Clojure language advocate the use of persistent data structures over mutable data structures because they have

1048:

One of the useful applications that can be solved efficiently using persistence is the Next Element Search. Assume that there are

584:

credits are transformed to the new table in addition to the one credit acquired from calling the CHANGE-EDGE. So in total we have

266:

Putting it all together, the change in ϕ is Δϕ =1− k. Thus, the algorithm takes O(k +Δϕ)= O(1) space and O(k +Δϕ +1) = O(1) time

3033:

To use the persistent BST implementations, simply clone the repository and follow the instructions provided in the README file.

4422:

The Use of Mercury for the Implementation of a Finite Domain Solver - Henk Vandecasteele, Bart Demoen, Joachim Van Der Auwera

3435: 3015: 2649: 1934:

doesn't increase the insertion time by more than a constant factor then the insertion in the persistent data structure takes

493:) in order to let each vertex in the array point to the new table created. In addition to that, we need to change the entry 4395: 3030:

GitHub repo containing implementations of persistent BSTs using Fat Nodes, Copy-on-Write, and Path Copying Techniques.

2166:. Every sequence of insertion and deletion will cause the creation of a sequence of dictionaries or versions or trees 960: 138:

One method for creating a persistent data structure is to use a platform provided ephemeral data structure such as an

4405: 4331: 3579: 3500: 3276: 3018:(GC) to automatically free up nodes which have no live references, and this is why GC is a feature commonly found in 3385: 104:

A type of data structure where user may query any version of the structure but may only update the latest version.

3991: 3222:

persistent, however. Fully persistent collections are available in third-party libraries, or other JVM languages.

1485:. Let us see how we can build another persistent data structure with the same query time but with a better space. 1285:

coordinates. Thus we have a data structure that can answer any query. In order to find the segment above a point

4256: 3258: 3206: 2645: 157: 42:

that always preserves the previous version of itself when it is modified. Such data structures are effectively

2665: 2661: 2252: 2169: 2600:, can easily be adapted to create a persistent version. Some others need slightly more effort, for example: 107:

An ephemeral data structure can be converted to partially persistent data structure using a few techniques.

4015: 3341: 2757: 2624:(which have an additional operation of random access with sub-linear, most often logarithmic, complexity). 92:

of querying or updating older versions of a data structure may be allowed to degrade, as is true with the

4437:"The Essence of Object-Functional Programming and the Practical Potential of Scala - codecentric AG Blog" 3380: 3218: 3142: 2657: 678: 3967: 3298: 3290: 3198: 3181: 3147: 3088:

at each level of the tree. The leaf nodes of the tree behave similar to the buckets used to construct

2470: 890: 3858: 3778: 3728: 3418: 1978:

time. For the deletion, we need to find which nodes will be affected by the deletion. For each node

4578: 3872: 3562: 3556:, Lecture Notes in Computer Science, vol. 4168, Springer Berlin Heidelberg, pp. 172–183, 3485:, Lecture Notes in Computer Science, vol. 4960, Springer Berlin Heidelberg, pp. 322–336, 3254: 3127: 3122: 53:

if all versions can be accessed but only the newest version can be modified. The data structure is

3816: 3679: 2656:

purely functional, but supports non-destructive list operations subset, that is also true in the

2641: 1140: 435:

rows can be created. The old table becomes inactive and the new table becomes the active table.

3557: 3463: 3413: 3050: 3019: 2601: 2593: 2426: 2382: 2125: 2081: 1937: 1408: 826: 73: 2520: 1452: 790: 753: 4558: 3845: 3765: 3715: 3370: 3189: 3077: 1644: 1584: 1524: 93: 4583: 4507: 3753: 2355: 2308: 2225: 1617: 1557: 1497: 1240: 1213: 651: 624: 191: 175: 142:

to store the data in the data structure and copy the entirety of that data structure using

89: 3620: 3408:

Driscoll JR, Sarnak N, Sleator DD, Tarjan RE (1986). "Making data structures persistent".

724: 8: 4159: 3356:, can in some cases have a positive impact on the overall performance of an application. 3246: 3146:

array mapped tries. These data structures implement the mandatory read-only parts of the

1734:. Performing rotations to rebalance the tree will only modify the nodes of the path from 587: 561: 412: 374: 4183: 3757: 3481:

Conchon, Sylvain; Filliâtre, Jean-Christophe (2008), "Semi-persistent Data Structures",

76:, as languages in those paradigms discourage (or fully forbid) the use of mutable data. 3925: 3743: 3671: 3532: 3441: 3345: 3328: 3161: 2750: 2605: 2589: 2553:. Please find below the source code for an example related to the next search problem. 2423:. Using this persistent data structure we can solve the next element search problem in 2335: 2061: 2041: 2021: 2001: 1981: 1917: 1897: 1877: 1857: 1837: 1817: 1797: 1777: 1757: 1737: 1717: 1697: 1677: 1388: 1368: 1365:

coordinate to find the segment above it. Thus we need two binary searches, one for the

1348: 1328: 1308: 1288: 1268: 1193: 1172: 1120: 1091: 1071: 1051: 940: 870: 171: 20: 16:

Data structure that always preserves the previous version of itself when it is modified

3596:"Using persistent data structures for adding range restrictions to searching problems" 4531: 4401: 3917: 3812:

C++Now 2017: Phil Nash "The Holy Grail!? A Persistent Hash-Array-Mapped Trie for C++"

3625: 3575: 3520: 3496: 3431: 1614:

is only one insertion or deletion then it is not a good idea to copy everything from

69: 3929: 3410:

Proceedings of the eighteenth annual ACM symposium on Theory of computing - STOC '86

401:

at which the operation was performed. In addition to that there is an array inedges(

4111: 3909: 3675: 3663: 3615: 3607: 3567: 3486: 3423: 3169: 256: 43: 3445: 3039: 2780:

A function which inserts data into the binary tree and maintains the invariant is:

1554:

either one thing leaves or one thing enters. If the difference between what is in

750:

without taking into account the recursive calls, then filling in a table requires

3704: 3491: 3375: 3154: 208:

a linked list the worst case modification time complexity is O(n + update cost).

4483: 4087: 3898:"Optimizing hash-array mapped tries for fast and lean immutable JVM collections" 3611: 2774: 2681: 3595: 3349: 3093: 3004: 2700: 217: 114:

A stratified tree with m elements is implemented using dynamic perfect hashing.

39: 4462: 4039: 3810: 4572: 4420: 3921: 3644: 3629: 3524: 3365: 3085: 3081: 1834:. Now we have 2 versions of the tree, the original one which doesn't contain 518:

It works exactly the same as CHANGE-EDGE except that instead of changing the

443:

A call to CREATE-NODE creates a new table and set all the references to null

221: 143: 139: 3913: 3293:

is frequently used along with a state management system that implements the

4339: 3837: 3057: 237: 3331:, as well as persistent hash array mapped tries as introduced in Clojure. 529: 4307: 3353: 3066: 2637: 2562: 179: 85: 4464:

Extreme Cleverness: Functional Data Structures in Scala - Daniel Spiewak

4207: 3571: 3427: 3194: 3089: 3061: 937:. We conclude that There exists a data structure that can complete any 307:

CREATE-NODE(): Creates a new vertex with no incoming or outgoing edges.

4360: 4135: 4063: 3667: 2640:

are the bread-and-butter data structure in functional languages. Some

359:

at any given time. For this purpose we define a table for each vertex

4532:"The Last Frontier in Java Performance: Remove the Garbage Collector" 3165: 3056:

Hash array mapped tries were originally described in a 2001 paper by

2754: 2570: 244: 27: 4563: 4374: 4231: 3202: 1405:

coordinate to find the segment above it. Thus the query time takes

1345:

to know which copy or strip it belongs to. Then we can look at the

471:: In this case we copy the last row in the table and we change the 3748: 3076:

Conceptually, hash array mapped tries work similar to any generic

3049:

A persistent hash array mapped trie is a specialized variant of a

3070: 3742:

Liljenzin, Olle (2013). "Confluently Persistent Sets and Maps".

2569:-based list, a simple list of objects formed by each carrying a 4379: 204: 4232:"Flux | Application Architecture for Building User Interfaces" 3897: 3297:, a popular implementation of which is the JavaScript library 3160:

These data structures form the basis of Clojure's support for

1385:

coordinate to find the strip or the copy, and another for the

128: 4559:

Lightweight Java implementation of Persistent Red-Black Trees

2597: 2058:. Since any deletion only modifies the path from the root to 1038: 174:

bound, assuming modification history is stored in a growable

3164:

since they allow for easy retries of operations to sidestep

3092:

and may or may not contain multiple candidates depending on

3060:

entitled "Ideal Hash Trees". This paper presented a mutable

1998:

affected by the deletion, we copy the path from the root to

3943: 3642: 3407: 2122:, thus the deletion in the persistent data structure takes 3795:

This example is taken from Okasaki. See the bibliography.

2770:

might be represented by the following binary search tree:

68:

These types of data structures are particularly common in

2556: 957:

sequence of CREATE-NODE, CHANGE-EDGE and CHANGE-LABEL in

4280: 4208:"Persistent (immutable) collections for Java and Kotlin" 3896:

Steindorfer, Michael J.; Vinju, Jurgen J. (2015-10-23).

2573:

to the next in the list. This is persistent because the

1043: 617:

CHANGE-LABEL: It works exactly the same as CHANGE-EDGE.

530:

Efficiency of the generalized persistent data structure

2561:

Perhaps the simplest persistent data structure is the

1794:

into the tree, we copy all the nodes on the path from

1190:

order. We sort the endpoints of the segments by their

99: 4393: 3649:"Planar Point Location Using Persistent Search Trees" 2588:

Many common reference-based data structures, such as

2523: 2473: 2429: 2385: 2358: 2338: 2311: 2255: 2228: 2172: 2128: 2084: 2064: 2044: 2024: 2004: 1984: 1940: 1920: 1900: 1880: 1860: 1840: 1820: 1800: 1780: 1760: 1740: 1720: 1700: 1680: 1647: 1620: 1587: 1560: 1527: 1500: 1455: 1411: 1391: 1371: 1351: 1331: 1311: 1291: 1271: 1243: 1216: 1196: 1175: 1143: 1123: 1094: 1074: 1054: 963: 943: 893: 873: 829: 793: 756: 727: 681: 654: 627: 590: 564: 415: 377: 3551: 3044: 2660:(LISt Processing) functional language dialects like 2652:

when nothing refers to it. (Note that ML itself is

675:

calls to CHANGE_EDGE will result in the creation of

463:) is called, then there are two cases to consider. 295:

of edges leading into it which we define as inedges(

1488: 203:With m modifications, this costs O(log m) additive 2545: 2509: 2459: 2415: 2371: 2344: 2324: 2297: 2241: 2214: 2158: 2114: 2070: 2050: 2030: 2010: 1990: 1970: 1926: 1906: 1886: 1866: 1846: 1826: 1806: 1786: 1766: 1746: 1726: 1706: 1686: 1666: 1633: 1606: 1573: 1546: 1513: 1477: 1441: 1397: 1377: 1357: 1337: 1317: 1297: 1277: 1256: 1229: 1202: 1181: 1161: 1129: 1100: 1080: 1060: 1027: 949: 929: 879: 859: 815: 778: 742: 713: 667: 640: 602: 576: 427: 389: 299:). We allow the following different operations on 269: 79: 4397:The Implementation of Prolog - Patrice Boizumault 4394:Djamboulian, Ara M.; Boizumault, Patrice (1993), 3111: 2725:The reason for the copy is that the last node in 467:There is an empty row in the table of the vertex 4570: 3895: 3600:RAIRO - Theoretical Informatics and Applications 3480: 1028:{\displaystyle O(n\cdot d^{2})+m\cdot O(Log(d))} 405:) that keeps track of all the incoming edges to 250: 61:. Structures that are not persistent are called 3040:https://github.com/DesaultierMAKK/PersistentBST 2078:and any appropriate deletion algorithm runs in 1714:into the tree, we create a new leaf containing 542:Each call to CREATE-NODE comes with two credits 2733:) cannot be modified to point to the start of 2714:are shared. As a result, the original lists ( 545:Each call to CHANGE-EDGE comes with one credit 3010:Notice two points: first, the original tree ( 539:The creation of one table requires one credit 198: 3705:"Purely Functional Data Structures (thesis)" 3537:: CS1 maint: multiple names: authors list ( 3468:Handbook on Data Structures and Applications 3461: 3257:. There might be a discussion about this on 887:edge and label operations, thus it requires 2696:results in the following memory structure: 2577:of the list can be taken, meaning the last 344:): Changes the value of the data stored at 129:Techniques for preserving previous versions 4508:"Immutable Objects And Garbage Collection" 3594:Lenhof, Hans-Peter; Smid, Michiel (1994). 3593: 3403: 3401: 3314:Delayed goals might mitigate the problem. 3289:The popular JavaScript frontend framework 1265:and we store all the copies sorted by the 1237:, we store the subset segments that cross 1039:Applications of persistent data structures 4460: 3747: 3741: 3702: 3619: 3561: 3490: 3457: 3455: 3417: 3277:Learn how and when to remove this message 3000:The following configuration is produced: 2737:, because that would change the value of 2677:These would be represented in memory by: 409:. When a table is full, a new table with 164: 4064:"Clojure - Differences with other Lisps" 3808: 2729:(the node containing the original value 1874:and whose root is a copy of the root of 3790: 3788: 3696: 3398: 3141:Like many programming languages in the 2753:, where every node in the tree has the 2298:{\displaystyle S_{1},S_{2},\dots S_{i}} 2215:{\displaystyle S_{1},S_{2},\dots S_{i}} 1169:vertical strips since each segment has 823:. Each access operation can be done in 4571: 3636: 3517:RRB-Trees: Efficient Immutable Vectors 3452: 3069:to be fully persistent for use in the 2722:) persist and have not been modified. 2557:Examples of persistent data structures 2038:and the new one which doesn't contain 621:As a summary, we conclude that having 4564:Efficient persistent structures in C# 4484:"Vladimir Kostyukov - Posts / Slides" 4302: 4300: 3804: 3802: 3515:Tiark, Bagwell, Philip Rompf (2011). 3514: 3334: 1044:Next element search or point location 4254: 3835: 3785: 3229: 2710:have been copied, but the nodes in 2620:returning the minimal element) and 497:in the inedges(w) for every vertex 100:Partially persistent data structure 13: 4297: 4184:"blog/blazing-fast-html-round-two" 4040:"Performance/Arrays - HaskellWiki" 3799: 2352:elements, then the search in each 721:tables. Since each table has size 714:{\displaystyle 2\cdot n_{1}+n_{2}} 522:edge of the vertex, we change the 14: 4595: 4552: 3483:Programming Languages and Systems 3045:Persistent hash array mapped trie 2690:Now concatenating the two lists: 3386:Purely functional data structure 3234: 3126:structure invalid would violate 3020:functional programming languages 3003: 2773: 2699: 2680: 2510:{\displaystyle O(n\cdot Log(n))} 1489:Persistent data structure method 930:{\displaystyle m\cdot O(Log(d))} 211: 133: 4524: 4500: 4476: 4454: 4429: 4413: 4387: 4367: 4353: 4324: 4273: 4248: 4224: 4200: 4176: 4152: 4128: 4104: 4080: 4056: 4032: 4008: 3984: 3960: 3936: 3889: 3865: 3829: 3819:from the original on 2021-12-21 2631: 1854:and the new tree that contains 1111: 513: 270:Generalized form of persistence 185: 80:Partial versus full persistence 4400:, Princeton University Press, 4257:"How to handle state in React" 4112:"Keynote: The Value of Values" 3735: 3621:11858/00-001M-0000-0014-AD4F-B 3587: 3545: 3508: 3474: 3112:Usage in programming languages 2764:For instance, the set of data 2706:Notice that the nodes in list 2540: 2527: 2504: 2501: 2495: 2477: 2454: 2451: 2445: 2433: 2410: 2407: 2401: 2389: 2153: 2150: 2144: 2132: 2109: 2106: 2100: 2088: 1965: 1962: 1956: 1944: 1894:. Since copying the path from 1472: 1459: 1436: 1433: 1427: 1415: 1137:line segments then we can get 1022: 1019: 1013: 1001: 986: 967: 924: 921: 915: 903: 854: 851: 845: 833: 810: 797: 773: 760: 737: 731: 451:If we assume that CHANGE-EDGE( 446: 438: 1: 3391: 3225: 1088:and return the segment above 279:. We assume that each vertex 251:Complexity of the combination 3492:10.1007/978-3-540-78739-6_25 3464:"Persistent data structures" 3342:automatic garbage collection 2249:is the result of operations 36:not ephemeral data structure 7: 4088:"Clojure - Data Structures" 3381:Retroactive data structures 3359: 2608:, and extensions including 1774:. Before inserting the key 1210:coordinate. For each strip 479:to point to the new vertex 150: 90:performance characteristics 10: 4600: 4255:Mora, Osmel (2016-07-18). 3148:Java collections framework 3136: 3116: 2612:(which have an additional 1162:{\displaystyle 2\cdot n+1} 199:Complexity of path copying 18: 3656:Communications of the ACM 3612:10.1051/ita/1994280100251 3308: 3219:Java programming language 2644:-derived languages, like 2460:{\displaystyle O(Log(n))} 2416:{\displaystyle O(Log(m))} 2159:{\displaystyle O(Log(n))} 2115:{\displaystyle O(Log(n))} 1971:{\displaystyle O(Log(n))} 1442:{\displaystyle O(Log(n))} 860:{\displaystyle O(Log(d))} 648:calls to CREATE_NODE and 32:persistent data structure 4461:ClojureTV (2013-01-07), 4308:"Immutable Data - Redux" 3321: 3182:Elm programming language 3128:referential transparency 3123:pure functional language 2782: 2744: 2671:Consider the two lists: 2546:{\displaystyle O(n^{2})} 1478:{\displaystyle O(n^{2})} 816:{\displaystyle O(d^{2})} 779:{\displaystyle O(d^{2})} 19:Not to be confused with 3914:10.1145/2814270.2814312 3809:BoostCon (2017-06-13), 3212: 3025: 1694:. When we insert a key 1667:{\displaystyle s_{i+1}} 1607:{\displaystyle s_{i+1}} 1547:{\displaystyle s_{i+1}} 144:copy-on-write semantics 3853:Cite journal requires 3836:Phil, Bagwell (2001). 3773:Cite journal requires 3723:Cite journal requires 3175: 3073:programming language. 3051:hash array mapped trie 2997:ys = insert ("e", xs) 2547: 2511: 2461: 2417: 2373: 2346: 2326: 2299: 2243: 2216: 2160: 2116: 2072: 2052: 2032: 2012: 1992: 1972: 1928: 1908: 1888: 1868: 1848: 1828: 1808: 1788: 1768: 1748: 1728: 1708: 1688: 1668: 1635: 1608: 1575: 1548: 1515: 1479: 1443: 1399: 1379: 1359: 1339: 1319: 1299: 1279: 1258: 1231: 1204: 1183: 1163: 1131: 1102: 1082: 1062: 1029: 951: 931: 881: 861: 817: 780: 744: 715: 669: 642: 604: 578: 429: 391: 287:has a constant number 165:Complexity of fat node 74:functional programming 59:confluently persistent 3554:Algorithms – ESA 2006 3462:Kaplan, Haim (2001). 3371:Navigational database 2548: 2512: 2462: 2418: 2374: 2372:{\displaystyle S_{i}} 2347: 2327: 2325:{\displaystyle S_{i}} 2300: 2244: 2242:{\displaystyle S_{i}} 2217: 2161: 2117: 2073: 2053: 2033: 2013: 1993: 1973: 1929: 1909: 1889: 1869: 1849: 1829: 1809: 1789: 1769: 1749: 1729: 1709: 1689: 1669: 1636: 1634:{\displaystyle s_{i}} 1609: 1576: 1574:{\displaystyle s_{i}} 1549: 1516: 1514:{\displaystyle s_{i}} 1480: 1444: 1400: 1380: 1360: 1340: 1320: 1305:, we can look at the 1300: 1280: 1259: 1257:{\displaystyle s_{i}} 1232: 1230:{\displaystyle s_{i}} 1205: 1184: 1164: 1132: 1103: 1083: 1063: 1030: 952: 932: 882: 862: 818: 781: 745: 716: 670: 668:{\displaystyle n_{2}} 643: 641:{\displaystyle n_{1}} 605: 579: 430: 392: 367:. The table contains 4164:package.elm-lang.org 3412:. pp. 109–121. 3247:confusing or unclear 2622:random access deques 2521: 2471: 2427: 2383: 2356: 2336: 2309: 2253: 2226: 2170: 2126: 2082: 2062: 2042: 2022: 2002: 1982: 1938: 1918: 1898: 1878: 1858: 1838: 1818: 1798: 1778: 1758: 1738: 1718: 1698: 1678: 1645: 1618: 1585: 1558: 1525: 1498: 1453: 1409: 1389: 1369: 1349: 1329: 1309: 1289: 1269: 1241: 1214: 1194: 1173: 1141: 1121: 1092: 1072: 1052: 961: 941: 891: 871: 827: 791: 754: 743:{\displaystyle O(d)} 725: 679: 652: 625: 588: 562: 505:exists in the graph 485:Table of the vertex 413: 375: 51:partially persistent 49:A data structure is 4441:codecentric AG Blog 4020:hackage.haskell.org 3996:hackage.haskell.org 3972:hackage.haskell.org 3902:ACM SIGPLAN Notices 3873:"Are We There Yet?" 3758:2013arXiv1301.3388L 3572:10.1007/11841036_18 3428:10.1145/12130.12142 3255:clarify the section 603:{\displaystyle d+2} 577:{\displaystyle d+1} 428:{\displaystyle d+1} 390:{\displaystyle d+1} 94:rope data structure 4383:. 26 October 2021. 4336:facebook.github.io 4236:facebook.github.io 3944:"Haskell Language" 3838:"Ideal Hash Trees" 3346:reference counting 3335:Garbage collection 3188:Elm uses a custom 3162:parallel computing 3016:garbage collection 2751:binary search tree 2563:singly linked list 2543: 2507: 2457: 2413: 2369: 2342: 2322: 2295: 2239: 2212: 2156: 2112: 2068: 2048: 2028: 2008: 1988: 1968: 1924: 1904: 1884: 1864: 1844: 1824: 1804: 1784: 1764: 1744: 1724: 1704: 1684: 1664: 1631: 1604: 1571: 1544: 1521:, when we move to 1511: 1475: 1439: 1395: 1375: 1355: 1335: 1315: 1295: 1275: 1254: 1227: 1200: 1179: 1159: 1127: 1098: 1078: 1058: 1025: 947: 927: 877: 857: 813: 776: 740: 711: 665: 638: 600: 574: 475:th edge of vertex 425: 387: 257:potential function 216:Driscoll, Sarnak, 21:Persistent storage 4281:"Read Me - Redux" 4136:"Clojure - Atoms" 3992:"Data.Map.Strict" 3668:10.1145/6138.6151 3437:978-0-89791-193-1 3295:Flux architecture 3287: 3286: 3279: 2650:garbage collector 2517:space instead of 2345:{\displaystyle m} 2071:{\displaystyle v} 2051:{\displaystyle k} 2031:{\displaystyle k} 2011:{\displaystyle v} 1991:{\displaystyle v} 1927:{\displaystyle T} 1907:{\displaystyle k} 1887:{\displaystyle T} 1867:{\displaystyle k} 1847:{\displaystyle k} 1827:{\displaystyle T} 1807:{\displaystyle k} 1787:{\displaystyle k} 1767:{\displaystyle T} 1747:{\displaystyle k} 1727:{\displaystyle k} 1707:{\displaystyle k} 1687:{\displaystyle T} 1398:{\displaystyle y} 1378:{\displaystyle x} 1358:{\displaystyle y} 1338:{\displaystyle p} 1318:{\displaystyle x} 1298:{\displaystyle p} 1278:{\displaystyle x} 1203:{\displaystyle x} 1182:{\displaystyle 2} 1130:{\displaystyle n} 1101:{\displaystyle p} 1081:{\displaystyle p} 1061:{\displaystyle n} 950:{\displaystyle n} 880:{\displaystyle m} 4591: 4546: 4545: 4543: 4542: 4528: 4522: 4521: 4519: 4518: 4504: 4498: 4497: 4495: 4494: 4480: 4474: 4473: 4472: 4471: 4458: 4452: 4451: 4449: 4448: 4433: 4427: 4426: 4417: 4411: 4410: 4391: 4385: 4384: 4371: 4365: 4364: 4357: 4351: 4350: 4348: 4347: 4338:. Archived from 4328: 4322: 4321: 4319: 4318: 4304: 4295: 4294: 4292: 4291: 4277: 4271: 4270: 4268: 4267: 4252: 4246: 4245: 4243: 4242: 4228: 4222: 4221: 4219: 4218: 4204: 4198: 4197: 4195: 4194: 4180: 4174: 4173: 4171: 4170: 4156: 4150: 4149: 4147: 4146: 4132: 4126: 4125: 4123: 4122: 4108: 4102: 4101: 4099: 4098: 4084: 4078: 4077: 4075: 4074: 4060: 4054: 4053: 4051: 4050: 4044:wiki.haskell.org 4036: 4030: 4029: 4027: 4026: 4012: 4006: 4005: 4003: 4002: 3988: 3982: 3981: 3979: 3978: 3964: 3958: 3957: 3955: 3954: 3940: 3934: 3933: 3893: 3887: 3886: 3884: 3883: 3869: 3863: 3862: 3856: 3851: 3849: 3841: 3833: 3827: 3826: 3825: 3824: 3806: 3797: 3792: 3783: 3782: 3776: 3771: 3769: 3761: 3751: 3739: 3733: 3732: 3726: 3721: 3719: 3711: 3709: 3700: 3694: 3693: 3691: 3690: 3684: 3678:. Archived from 3653: 3645:Robert E. Tarjan 3640: 3634: 3633: 3623: 3591: 3585: 3584: 3565: 3549: 3543: 3542: 3536: 3528: 3512: 3506: 3505: 3494: 3478: 3472: 3471: 3459: 3450: 3449: 3421: 3405: 3282: 3275: 3271: 3268: 3262: 3238: 3237: 3230: 3170:compare and swap 3013: 3007: 2994:After executing 2990: 2987: 2984: 2981: 2978: 2975: 2972: 2969: 2966: 2963: 2960: 2957: 2954: 2951: 2948: 2945: 2942: 2939: 2936: 2933: 2930: 2927: 2924: 2921: 2918: 2915: 2912: 2909: 2906: 2903: 2900: 2897: 2894: 2891: 2888: 2885: 2882: 2879: 2876: 2873: 2870: 2867: 2864: 2861: 2858: 2855: 2852: 2849: 2846: 2843: 2840: 2837: 2834: 2831: 2828: 2825: 2822: 2819: 2816: 2813: 2810: 2807: 2804: 2801: 2798: 2795: 2792: 2789: 2786: 2777: 2740: 2736: 2732: 2728: 2721: 2717: 2713: 2709: 2703: 2684: 2552: 2550: 2549: 2544: 2539: 2538: 2516: 2514: 2513: 2508: 2466: 2464: 2463: 2458: 2422: 2420: 2419: 2414: 2378: 2376: 2375: 2370: 2368: 2367: 2351: 2349: 2348: 2343: 2331: 2329: 2328: 2323: 2321: 2320: 2304: 2302: 2301: 2296: 2294: 2293: 2278: 2277: 2265: 2264: 2248: 2246: 2245: 2240: 2238: 2237: 2221: 2219: 2218: 2213: 2211: 2210: 2195: 2194: 2182: 2181: 2165: 2163: 2162: 2157: 2121: 2119: 2118: 2113: 2077: 2075: 2074: 2069: 2057: 2055: 2054: 2049: 2037: 2035: 2034: 2029: 2017: 2015: 2014: 2009: 1997: 1995: 1994: 1989: 1977: 1975: 1974: 1969: 1933: 1931: 1930: 1925: 1913: 1911: 1910: 1905: 1893: 1891: 1890: 1885: 1873: 1871: 1870: 1865: 1853: 1851: 1850: 1845: 1833: 1831: 1830: 1825: 1813: 1811: 1810: 1805: 1793: 1791: 1790: 1785: 1773: 1771: 1770: 1765: 1753: 1751: 1750: 1745: 1733: 1731: 1730: 1725: 1713: 1711: 1710: 1705: 1693: 1691: 1690: 1685: 1673: 1671: 1670: 1665: 1663: 1662: 1640: 1638: 1637: 1632: 1630: 1629: 1613: 1611: 1610: 1605: 1603: 1602: 1580: 1578: 1577: 1572: 1570: 1569: 1553: 1551: 1550: 1545: 1543: 1542: 1520: 1518: 1517: 1512: 1510: 1509: 1484: 1482: 1481: 1476: 1471: 1470: 1448: 1446: 1445: 1440: 1404: 1402: 1401: 1396: 1384: 1382: 1381: 1376: 1364: 1362: 1361: 1356: 1344: 1342: 1341: 1336: 1324: 1322: 1321: 1316: 1304: 1302: 1301: 1296: 1284: 1282: 1281: 1276: 1263: 1261: 1260: 1255: 1253: 1252: 1236: 1234: 1233: 1228: 1226: 1225: 1209: 1207: 1206: 1201: 1188: 1186: 1185: 1180: 1168: 1166: 1165: 1160: 1136: 1134: 1133: 1128: 1107: 1105: 1104: 1099: 1087: 1085: 1084: 1079: 1067: 1065: 1064: 1059: 1034: 1032: 1031: 1026: 985: 984: 956: 954: 953: 948: 936: 934: 933: 928: 886: 884: 883: 878: 866: 864: 863: 858: 822: 820: 819: 814: 809: 808: 785: 783: 782: 777: 772: 771: 749: 747: 746: 741: 720: 718: 717: 712: 710: 709: 697: 696: 674: 672: 671: 666: 664: 663: 647: 645: 644: 639: 637: 636: 613: 609: 607: 606: 601: 583: 581: 580: 575: 525: 521: 508: 504: 500: 496: 492: 488: 482: 478: 474: 470: 462: 458: 454: 434: 432: 431: 426: 408: 404: 400: 396: 394: 393: 388: 370: 366: 362: 358: 351: 347: 343: 339: 333: 329: 325: 321: 317: 313: 302: 298: 294: 290: 286: 282: 278: 55:fully persistent 4599: 4598: 4594: 4593: 4592: 4590: 4589: 4588: 4579:Data structures 4569: 4568: 4555: 4550: 4549: 4540: 4538: 4530: 4529: 4525: 4516: 4514: 4506: 4505: 4501: 4492: 4490: 4482: 4481: 4477: 4469: 4467: 4459: 4455: 4446: 4444: 4435: 4434: 4430: 4419: 4418: 4414: 4408: 4392: 4388: 4373: 4372: 4368: 4359: 4358: 4354: 4345: 4343: 4330: 4329: 4325: 4316: 4314: 4306: 4305: 4298: 4289: 4287: 4279: 4278: 4274: 4265: 4263: 4261:React Ecosystem 4253: 4249: 4240: 4238: 4230: 4229: 4225: 4216: 4214: 4206: 4205: 4201: 4192: 4190: 4182: 4181: 4177: 4168: 4166: 4158: 4157: 4153: 4144: 4142: 4134: 4133: 4129: 4120: 4118: 4110: 4109: 4105: 4096: 4094: 4086: 4085: 4081: 4072: 4070: 4062: 4061: 4057: 4048: 4046: 4038: 4037: 4033: 4024: 4022: 4014: 4013: 4009: 4000: 3998: 3990: 3989: 3985: 3976: 3974: 3966: 3965: 3961: 3952: 3950: 3948:www.haskell.org 3942: 3941: 3937: 3908:(10): 783–800. 3894: 3890: 3881: 3879: 3871: 3870: 3866: 3854: 3852: 3843: 3842: 3834: 3830: 3822: 3820: 3807: 3800: 3793: 3786: 3774: 3772: 3763: 3762: 3740: 3736: 3724: 3722: 3713: 3712: 3707: 3703:Chris Okasaki. 3701: 3697: 3688: 3686: 3682: 3651: 3641: 3637: 3592: 3588: 3582: 3550: 3546: 3530: 3529: 3513: 3509: 3503: 3479: 3475: 3460: 3453: 3438: 3419:10.1.1.133.4630 3406: 3399: 3394: 3376:Persistent data 3362: 3344:system such as 3337: 3329:red–black trees 3324: 3311: 3283: 3272: 3266: 3263: 3252: 3239: 3235: 3228: 3215: 3178: 3155:value semantics 3139: 3119: 3114: 3094:hash collisions 3047: 3028: 3011: 2998: 2992: 2991: 2988: 2985: 2982: 2979: 2976: 2973: 2970: 2967: 2964: 2961: 2958: 2955: 2952: 2949: 2946: 2943: 2940: 2937: 2934: 2931: 2928: 2925: 2922: 2919: 2916: 2913: 2910: 2907: 2904: 2901: 2898: 2895: 2892: 2889: 2886: 2883: 2880: 2877: 2874: 2871: 2868: 2865: 2862: 2859: 2856: 2853: 2850: 2847: 2844: 2841: 2838: 2835: 2832: 2829: 2826: 2823: 2820: 2817: 2814: 2811: 2808: 2805: 2802: 2799: 2796: 2793: 2790: 2787: 2784: 2768: 2747: 2738: 2734: 2730: 2726: 2719: 2715: 2711: 2707: 2694: 2675: 2634: 2590:red–black trees 2581:items for some 2559: 2534: 2530: 2522: 2519: 2518: 2472: 2469: 2468: 2467:query time and 2428: 2425: 2424: 2384: 2381: 2380: 2363: 2359: 2357: 2354: 2353: 2337: 2334: 2333: 2316: 2312: 2310: 2307: 2306: 2289: 2285: 2273: 2269: 2260: 2256: 2254: 2251: 2250: 2233: 2229: 2227: 2224: 2223: 2206: 2202: 2190: 2186: 2177: 2173: 2171: 2168: 2167: 2127: 2124: 2123: 2083: 2080: 2079: 2063: 2060: 2059: 2043: 2040: 2039: 2023: 2020: 2019: 2003: 2000: 1999: 1983: 1980: 1979: 1939: 1936: 1935: 1919: 1916: 1915: 1899: 1896: 1895: 1879: 1876: 1875: 1859: 1856: 1855: 1839: 1836: 1835: 1819: 1816: 1815: 1799: 1796: 1795: 1779: 1776: 1775: 1759: 1756: 1755: 1739: 1736: 1735: 1719: 1716: 1715: 1699: 1696: 1695: 1679: 1676: 1675: 1652: 1648: 1646: 1643: 1642: 1625: 1621: 1619: 1616: 1615: 1592: 1588: 1586: 1583: 1582: 1581:and what is in 1565: 1561: 1559: 1556: 1555: 1532: 1528: 1526: 1523: 1522: 1505: 1501: 1499: 1496: 1495: 1491: 1466: 1462: 1454: 1451: 1450: 1410: 1407: 1406: 1390: 1387: 1386: 1370: 1367: 1366: 1350: 1347: 1346: 1330: 1327: 1326: 1310: 1307: 1306: 1290: 1287: 1286: 1270: 1267: 1266: 1248: 1244: 1242: 1239: 1238: 1221: 1217: 1215: 1212: 1211: 1195: 1192: 1191: 1174: 1171: 1170: 1142: 1139: 1138: 1122: 1119: 1118: 1114: 1093: 1090: 1089: 1073: 1070: 1069: 1053: 1050: 1049: 1046: 1041: 980: 976: 962: 959: 958: 942: 939: 938: 892: 889: 888: 872: 869: 868: 828: 825: 824: 804: 800: 792: 789: 788: 767: 763: 755: 752: 751: 726: 723: 722: 705: 701: 692: 688: 680: 677: 676: 659: 655: 653: 650: 649: 632: 628: 626: 623: 622: 611: 589: 586: 585: 563: 560: 559: 532: 523: 519: 516: 506: 502: 501:such that edge 498: 494: 490: 486: 480: 476: 472: 468: 460: 456: 452: 449: 441: 414: 411: 410: 406: 402: 398: 376: 373: 372: 368: 364: 360: 356: 349: 345: 341: 337: 331: 327: 323: 322:): Changes the 319: 315: 311: 300: 296: 292: 288: 284: 280: 276: 272: 253: 214: 201: 188: 167: 153: 136: 131: 102: 86:linear ordering 82: 24: 17: 12: 11: 5: 4597: 4587: 4586: 4581: 4567: 4566: 4561: 4554: 4553:External links 4551: 4548: 4547: 4523: 4499: 4475: 4453: 4428: 4412: 4406: 4386: 4366: 4352: 4332:"Immutable.js" 4323: 4296: 4272: 4247: 4223: 4199: 4175: 4151: 4127: 4103: 4079: 4055: 4031: 4007: 3983: 3959: 3935: 3888: 3864: 3855:|journal= 3828: 3798: 3784: 3775:|journal= 3734: 3725:|journal= 3695: 3662:(7): 669–679. 3635: 3586: 3580: 3563:10.1.1.70.1493 3544: 3507: 3501: 3473: 3451: 3436: 3396: 3395: 3393: 3390: 3389: 3388: 3383: 3378: 3373: 3368: 3361: 3358: 3350:mark and sweep 3336: 3333: 3323: 3320: 3310: 3307: 3285: 3284: 3242: 3240: 3233: 3227: 3224: 3214: 3211: 3177: 3174: 3138: 3135: 3118: 3115: 3113: 3110: 3046: 3043: 3027: 3024: 2996: 2783: 2766: 2746: 2743: 2693:zs = xs ++ ys 2692: 2673: 2633: 2630: 2616:(1) operation 2558: 2555: 2542: 2537: 2533: 2529: 2526: 2506: 2503: 2500: 2497: 2494: 2491: 2488: 2485: 2482: 2479: 2476: 2456: 2453: 2450: 2447: 2444: 2441: 2438: 2435: 2432: 2412: 2409: 2406: 2403: 2400: 2397: 2394: 2391: 2388: 2366: 2362: 2341: 2319: 2315: 2292: 2288: 2284: 2281: 2276: 2272: 2268: 2263: 2259: 2236: 2232: 2209: 2205: 2201: 2198: 2193: 2189: 2185: 2180: 2176: 2155: 2152: 2149: 2146: 2143: 2140: 2137: 2134: 2131: 2111: 2108: 2105: 2102: 2099: 2096: 2093: 2090: 2087: 2067: 2047: 2027: 2007: 1987: 1967: 1964: 1961: 1958: 1955: 1952: 1949: 1946: 1943: 1923: 1903: 1883: 1863: 1843: 1823: 1803: 1783: 1763: 1743: 1723: 1703: 1683: 1661: 1658: 1655: 1651: 1628: 1624: 1601: 1598: 1595: 1591: 1568: 1564: 1541: 1538: 1535: 1531: 1508: 1504: 1490: 1487: 1474: 1469: 1465: 1461: 1458: 1438: 1435: 1432: 1429: 1426: 1423: 1420: 1417: 1414: 1394: 1374: 1354: 1334: 1325:coordinate of 1314: 1294: 1274: 1251: 1247: 1224: 1220: 1199: 1178: 1158: 1155: 1152: 1149: 1146: 1126: 1113: 1110: 1097: 1077: 1057: 1045: 1042: 1040: 1037: 1024: 1021: 1018: 1015: 1012: 1009: 1006: 1003: 1000: 997: 994: 991: 988: 983: 979: 975: 972: 969: 966: 946: 926: 923: 920: 917: 914: 911: 908: 905: 902: 899: 896: 876: 867:and there are 856: 853: 850: 847: 844: 841: 838: 835: 832: 812: 807: 803: 799: 796: 775: 770: 766: 762: 759: 739: 736: 733: 730: 708: 704: 700: 695: 691: 687: 684: 662: 658: 635: 631: 619: 618: 615: 599: 596: 593: 573: 570: 567: 555: 547: 546: 543: 540: 531: 528: 515: 512: 511: 510: 483: 448: 445: 440: 437: 424: 421: 418: 386: 383: 380: 353: 352: 334: 308: 271: 268: 252: 249: 228:box is empty. 213: 210: 200: 197: 187: 184: 172:amortized time 166: 163: 152: 149: 135: 132: 130: 127: 122: 121: 118: 115: 101: 98: 81: 78: 40:data structure 15: 9: 6: 4: 3: 2: 4596: 4585: 4582: 4580: 4577: 4576: 4574: 4565: 4562: 4560: 4557: 4556: 4537: 4533: 4527: 4513: 4509: 4503: 4489: 4488:kostyukov.net 4485: 4479: 4466: 4465: 4457: 4442: 4438: 4432: 4424: 4423: 4416: 4409: 4407:9780691637709 4403: 4399: 4398: 4390: 4382: 4381: 4376: 4370: 4362: 4356: 4342:on 2015-08-09 4341: 4337: 4333: 4327: 4313: 4309: 4303: 4301: 4286: 4282: 4276: 4262: 4258: 4251: 4237: 4233: 4227: 4213: 4209: 4203: 4189: 4185: 4179: 4165: 4161: 4155: 4141: 4137: 4131: 4117: 4113: 4107: 4093: 4089: 4083: 4069: 4065: 4059: 4045: 4041: 4035: 4021: 4017: 4011: 3997: 3993: 3987: 3973: 3969: 3963: 3949: 3945: 3939: 3931: 3927: 3923: 3919: 3915: 3911: 3907: 3903: 3899: 3892: 3878: 3874: 3868: 3860: 3847: 3839: 3832: 3818: 3814: 3813: 3805: 3803: 3796: 3791: 3789: 3780: 3767: 3759: 3755: 3750: 3745: 3738: 3730: 3717: 3706: 3699: 3685:on 2015-10-10 3681: 3677: 3673: 3669: 3665: 3661: 3657: 3650: 3646: 3643:Neil Sarnak; 3639: 3631: 3627: 3622: 3617: 3613: 3609: 3605: 3601: 3597: 3590: 3583: 3581:9783540388753 3577: 3573: 3569: 3564: 3559: 3555: 3548: 3540: 3534: 3526: 3522: 3518: 3511: 3504: 3502:9783540787389 3498: 3493: 3488: 3484: 3477: 3469: 3465: 3458: 3456: 3447: 3443: 3439: 3433: 3429: 3425: 3420: 3415: 3411: 3404: 3402: 3397: 3387: 3384: 3382: 3379: 3377: 3374: 3372: 3369: 3367: 3366:Copy-on-write 3364: 3363: 3357: 3355: 3351: 3347: 3343: 3332: 3330: 3319: 3315: 3306: 3302: 3300: 3296: 3292: 3281: 3278: 3270: 3260: 3259:the talk page 3256: 3250: 3248: 3243:This section 3241: 3232: 3231: 3223: 3220: 3210: 3208: 3204: 3200: 3196: 3191: 3186: 3183: 3173: 3171: 3167: 3163: 3158: 3156: 3151: 3149: 3144: 3134: 3131: 3129: 3124: 3121:Haskell is a 3109: 3107: 3103: 3097: 3095: 3091: 3087: 3083: 3082:hash function 3079: 3074: 3072: 3068: 3063: 3059: 3054: 3052: 3042: 3041: 3038: 3034: 3031: 3023: 3021: 3017: 3008: 3006: 3001: 2995: 2781: 2778: 2776: 2771: 2765: 2762: 2759: 2756: 2752: 2742: 2723: 2704: 2702: 2697: 2691: 2688: 2685: 2683: 2678: 2672: 2669: 2667: 2663: 2659: 2655: 2651: 2647: 2643: 2639: 2629: 2625: 2623: 2619: 2615: 2611: 2607: 2603: 2599: 2595: 2591: 2586: 2584: 2580: 2576: 2572: 2568: 2564: 2554: 2535: 2531: 2524: 2498: 2492: 2489: 2486: 2483: 2480: 2474: 2448: 2442: 2439: 2436: 2430: 2404: 2398: 2395: 2392: 2386: 2364: 2360: 2339: 2317: 2313: 2290: 2286: 2282: 2279: 2274: 2270: 2266: 2261: 2257: 2234: 2230: 2207: 2203: 2199: 2196: 2191: 2187: 2183: 2178: 2174: 2147: 2141: 2138: 2135: 2129: 2103: 2097: 2094: 2091: 2085: 2065: 2045: 2025: 2005: 1985: 1959: 1953: 1950: 1947: 1941: 1921: 1901: 1881: 1861: 1841: 1821: 1801: 1781: 1761: 1741: 1721: 1701: 1681: 1659: 1656: 1653: 1649: 1626: 1622: 1599: 1596: 1593: 1589: 1566: 1562: 1539: 1536: 1533: 1529: 1506: 1502: 1486: 1467: 1463: 1456: 1430: 1424: 1421: 1418: 1412: 1392: 1372: 1352: 1332: 1312: 1292: 1272: 1249: 1245: 1222: 1218: 1197: 1176: 1156: 1153: 1150: 1147: 1144: 1124: 1109: 1095: 1075: 1055: 1036: 1016: 1010: 1007: 1004: 998: 995: 992: 989: 981: 977: 973: 970: 964: 944: 918: 912: 909: 906: 900: 897: 894: 874: 848: 842: 839: 836: 830: 805: 801: 794: 768: 764: 757: 734: 728: 706: 702: 698: 693: 689: 685: 682: 660: 656: 633: 629: 616: 597: 594: 591: 571: 568: 565: 556: 553: 552: 551: 544: 541: 538: 537: 536: 527: 484: 466: 465: 464: 444: 436: 422: 419: 416: 384: 381: 378: 336:CHANGE-LABEL( 335: 309: 306: 305: 304: 267: 264: 260: 258: 248: 246: 241: 239: 233: 229: 225: 223: 219: 212:A combination 209: 206: 196: 193: 183: 181: 177: 173: 162: 159: 148: 145: 141: 134:Copy-on-write 126: 119: 116: 113: 112: 111: 108: 105: 97: 95: 91: 87: 77: 75: 71: 66: 64: 60: 56: 52: 47: 45: 41: 37: 33: 29: 22: 4539:. Retrieved 4535: 4526: 4515:. Retrieved 4511: 4502: 4491:. Retrieved 4487: 4478: 4468:, retrieved 4463: 4456: 4445:. Retrieved 4443:. 2015-08-31 4440: 4431: 4421: 4415: 4396: 4389: 4378: 4369: 4355: 4344:. Retrieved 4340:the original 4335: 4326: 4315:. Retrieved 4312:redux.js.org 4311: 4288:. Retrieved 4285:redux.js.org 4284: 4275: 4264:. Retrieved 4260: 4250: 4239:. Retrieved 4235: 4226: 4215:. Retrieved 4211: 4202: 4191:. Retrieved 4188:elm-lang.org 4187: 4178: 4167:. Retrieved 4163: 4160:"core 1.0.0" 4154: 4143:. Retrieved 4139: 4130: 4119:. Retrieved 4115: 4106: 4095:. Retrieved 4091: 4082: 4071:. Retrieved 4067: 4058: 4047:. Retrieved 4043: 4034: 4023:. Retrieved 4019: 4010: 3999:. Retrieved 3995: 3986: 3975:. Retrieved 3971: 3962: 3951:. Retrieved 3947: 3938: 3905: 3901: 3891: 3880:. Retrieved 3876: 3867: 3846:cite journal 3831: 3821:, retrieved 3811: 3794: 3766:cite journal 3737: 3716:cite journal 3698: 3687:. Retrieved 3680:the original 3659: 3655: 3638: 3606:(1): 25–49. 3603: 3599: 3589: 3553: 3547: 3516: 3510: 3482: 3476: 3467: 3409: 3354:memory leaks 3338: 3325: 3316: 3312: 3303: 3288: 3273: 3264: 3253:Please help 3244: 3216: 3187: 3179: 3159: 3152: 3140: 3132: 3120: 3105: 3101: 3098: 3086:sparse array 3075: 3058:Phil Bagwell 3055: 3048: 3036: 3035: 3032: 3029: 3009: 3002: 2999: 2993: 2779: 2772: 2769: 2763: 2748: 2724: 2705: 2698: 2695: 2689: 2686: 2679: 2676: 2674:xs = ys = 2670: 2653: 2638:linked lists 2635: 2632:Linked lists 2626: 2617: 2613: 2587: 2582: 2578: 2574: 2566: 2560: 1492: 1115: 1112:Naïve method 1047: 620: 548: 533: 517: 514:CHANGE-LABEL 450: 442: 371:columns and 354: 330:to point to 310:CHANGE-EDGE( 273: 265: 261: 254: 242: 238:sorted array 234: 230: 226: 215: 202: 189: 186:Path copying 168: 154: 137: 123: 109: 106: 103: 83: 67: 62: 58: 54: 50: 48: 35: 31: 25: 4584:Persistence 4512:wiki.c2.com 4140:clojure.org 4092:clojure.org 4068:clojure.org 3968:"Data.List" 3197:frameworks 3190:virtual DOM 3172:semantics. 3168:and atomic 3090:hash tables 3067:Rich Hickey 2749:Consider a 2222:where each 447:CHANGE-EDGE 439:CREATE-NODE 240:of roots.) 180:access time 4573:Categories 4541:2018-11-30 4517:2018-11-30 4493:2018-11-30 4470:2018-10-23 4447:2018-10-23 4346:2018-10-23 4317:2018-10-23 4290:2018-10-23 4266:2018-10-23 4241:2018-10-23 4217:2023-12-13 4212:github.com 4193:2018-10-23 4169:2018-10-23 4145:2018-11-30 4121:2018-10-23 4097:2018-10-23 4073:2018-10-23 4049:2018-10-23 4025:2018-10-23 4016:"Data.Set" 4001:2018-10-23 3977:2018-10-23 3953:2018-10-22 3882:2018-10-22 3823:2018-10-22 3689:2011-04-06 3392:References 3249:to readers 3226:JavaScript 3195:JavaScript 3166:data races 3062:Hash table 2610:min-deques 2305:. If each 243:With this 3922:0362-1340 3749:1301.3388 3630:0988-3754 3558:CiteSeerX 3533:cite book 3525:820379112 3414:CiteSeerX 2758:invariant 2755:recursive 2571:reference 2484:⋅ 2332:contains 2283:… 2200:… 1148:⋅ 996:⋅ 974:⋅ 898:⋅ 686:⋅ 245:algorithm 63:ephemeral 44:immutable 28:computing 3930:10317844 3817:archived 3647:(1986). 3360:See also 3318:solver. 3267:May 2021 2606:dequeues 326:edge of 192:cascaded 151:Fat node 4375:"Immer" 3754:Bibcode 3676:8745316 3245:may be 3207:Angular 3137:Clojure 3117:Haskell 3071:Clojure 2646:Haskell 2636:Singly 526:label. 218:Sleator 158:pointer 70:logical 4425:, 1999 4404: 4380:GitHub 4361:"Mori" 3928: 3920: 3674: 3628: 3578: 3560: 3523: 3499: 3446:364871 3444: 3434: 3416: 3309:Prolog 3205:, and 3037:Link: 2968:insert 2902:insert 2836:insert 2788:insert 2767:xs = 2666:Racket 2662:Scheme 2602:queues 2598:treaps 2596:, and 2594:stacks 2379:takes 222:Tarjan 205:lookup 4536:InfoQ 4116:InfoQ 3926:S2CID 3877:InfoQ 3744:arXiv 3708:(PDF) 3683:(PDF) 3672:S2CID 3652:(PDF) 3442:S2CID 3322:Scala 3299:Redux 3291:React 3203:Ember 3199:React 3104:(log 2745:Trees 178:. At 176:array 140:array 38:is a 4402:ISBN 3918:ISSN 3859:help 3779:help 3729:help 3626:ISSN 3576:ISBN 3539:link 3521:OCLC 3497:ISBN 3432:ISBN 3217:The 3213:Java 3180:The 3143:Lisp 3078:tree 3026:Code 2986:else 2947:then 2941:> 2932:else 2893:then 2887:< 2718:and 2664:and 2658:Lisp 2575:tail 2567:cons 72:and 30:, a 3910:doi 3664:doi 3616:hdl 3608:doi 3568:doi 3487:doi 3424:doi 3348:or 3176:Elm 2785:fun 2668:.) 2654:not 2618:min 2565:or 1914:to 1814:to 1754:to 1641:to 503:v,w 363:in 348:to 303:. 283:in 34:or 26:In 4575:: 4534:. 4510:. 4486:. 4439:. 4377:. 4334:. 4310:. 4299:^ 4283:. 4259:. 4234:. 4210:. 4186:. 4162:. 4138:. 4114:. 4090:. 4066:. 4042:. 4018:. 3994:. 3970:. 3946:. 3924:. 3916:. 3906:50 3904:. 3900:. 3875:. 3850:: 3848:}} 3844:{{ 3815:, 3801:^ 3787:^ 3770:: 3768:}} 3764:{{ 3752:. 3720:: 3718:}} 3714:{{ 3670:. 3660:29 3658:. 3654:. 3624:. 3614:. 3604:28 3602:. 3598:. 3574:, 3566:, 3535:}} 3531:{{ 3519:. 3495:, 3466:. 3454:^ 3440:. 3430:. 3422:. 3400:^ 3209:. 3201:, 3150:. 3130:. 3096:. 3022:. 3012:xs 2983:)) 2935:if 2917:), 2881:if 2875:)) 2851:as 2741:. 2739:xs 2735:ys 2727:xs 2720:ys 2716:xs 2712:ys 2708:xs 2642:ML 2604:, 2592:, 1035:. 459:, 455:, 340:, 318:, 314:, 220:, 65:. 4544:. 4520:. 4496:. 4450:. 4363:. 4349:. 4320:. 4293:. 4269:. 4244:. 4220:. 4196:. 4172:. 4148:. 4124:. 4100:. 4076:. 4052:. 4028:. 4004:. 3980:. 3956:. 3932:. 3912:: 3885:. 3861:) 3857:( 3840:. 3781:) 3777:( 3760:. 3756:: 3746:: 3731:) 3727:( 3710:. 3692:. 3666:: 3632:. 3618:: 3610:: 3570:: 3541:) 3527:. 3489:: 3470:. 3448:. 3426:: 3280:) 3274:( 3269:) 3265:( 3261:. 3251:. 3106:n 3102:O 2989:s 2980:b 2977:, 2974:x 2971:( 2965:, 2962:y 2959:, 2956:a 2953:( 2950:T 2944:y 2938:x 2929:) 2926:b 2923:, 2920:y 2914:a 2911:, 2908:x 2905:( 2899:( 2896:T 2890:y 2884:x 2878:= 2872:b 2869:, 2866:y 2863:, 2860:a 2857:( 2854:T 2848:s 2845:, 2842:x 2839:( 2833:| 2830:) 2827:E 2824:, 2821:x 2818:, 2815:E 2812:( 2809:T 2806:= 2803:) 2800:E 2797:, 2794:x 2791:( 2731:2 2614:O 2583:k 2579:k 2541:) 2536:2 2532:n 2528:( 2525:O 2505:) 2502:) 2499:n 2496:( 2493:g 2490:o 2487:L 2481:n 2478:( 2475:O 2455:) 2452:) 2449:n 2446:( 2443:g 2440:o 2437:L 2434:( 2431:O 2411:) 2408:) 2405:m 2402:( 2399:g 2396:o 2393:L 2390:( 2387:O 2365:i 2361:S 2340:m 2318:i 2314:S 2291:i 2287:S 2280:, 2275:2 2271:S 2267:, 2262:1 2258:S 2235:i 2231:S 2208:i 2204:S 2197:, 2192:2 2188:S 2184:, 2179:1 2175:S 2154:) 2151:) 2148:n 2145:( 2142:g 2139:o 2136:L 2133:( 2130:O 2110:) 2107:) 2104:n 2101:( 2098:g 2095:o 2092:L 2089:( 2086:O 2066:v 2046:k 2026:k 2006:v 1986:v 1966:) 1963:) 1960:n 1957:( 1954:g 1951:o 1948:L 1945:( 1942:O 1922:T 1902:k 1882:T 1862:k 1842:k 1822:T 1802:k 1782:k 1762:T 1742:k 1722:k 1702:k 1682:T 1660:1 1657:+ 1654:i 1650:s 1627:i 1623:s 1600:1 1597:+ 1594:i 1590:s 1567:i 1563:s 1540:1 1537:+ 1534:i 1530:s 1507:i 1503:s 1473:) 1468:2 1464:n 1460:( 1457:O 1437:) 1434:) 1431:n 1428:( 1425:g 1422:o 1419:L 1416:( 1413:O 1393:y 1373:x 1353:y 1333:p 1313:x 1293:p 1273:x 1250:i 1246:s 1223:i 1219:s 1198:x 1177:2 1157:1 1154:+ 1151:n 1145:2 1125:n 1096:p 1076:p 1056:n 1023:) 1020:) 1017:d 1014:( 1011:g 1008:o 1005:L 1002:( 999:O 993:m 990:+ 987:) 982:2 978:d 971:n 968:( 965:O 945:n 925:) 922:) 919:d 916:( 913:g 910:o 907:L 904:( 901:O 895:m 875:m 855:) 852:) 849:d 846:( 843:g 840:o 837:L 834:( 831:O 811:) 806:2 802:d 798:( 795:O 774:) 769:2 765:d 761:( 758:O 738:) 735:d 732:( 729:O 707:2 703:n 699:+ 694:1 690:n 683:2 661:2 657:n 634:1 630:n 612:d 598:2 595:+ 592:d 572:1 569:+ 566:d 524:i 520:i 509:. 507:G 499:w 495:v 491:v 487:v 481:u 477:v 473:i 469:v 461:u 457:i 453:v 423:1 420:+ 417:d 407:v 403:v 399:t 385:1 382:+ 379:d 369:c 365:G 361:v 357:G 350:x 346:v 342:x 338:v 332:u 328:v 324:i 320:u 316:i 312:v 301:G 297:v 293:d 289:c 285:G 281:v 277:G 23:.

Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.

Knowledge

Persistent data structure

Index