# Tag Info

24

Positive result: persistence does not cost too much. One can show that every data structure can be made fully persistent with at most a $O(\lg n)$ slowdown. Proof: You can take an array and make it persistent using standard data structures (e.g., a balanced binary tree; see the end of this answer for a bit more detail). This incurs a $O(\lg n)$ slowdown: ...

19

When you work with immutable data objects, functions have the property that every time you call them with the same inputs, they produce the same outputs. This makes it easier to conceptualize computations and get them right. It also makes them easier to test. That is just a start. Since mathematics has long worked with functions, there are plenty of ...

15

It is easier to correctly work with persistent data structures than it is to work with mutable data structures. This, I would say, is the main advantage. Of course, theoretically speaking, anything we do with persistent data structures we can also do with mutable ones, and vice versa. In many cases persitent data structures incure extra costs, usually ...

13

The obvious candidate is a persistent balanced binary tree. All the operations you listed can be performed in $O(1)$ or $O(\lg n)$ time, using path copying. For more details on how to achieve this runtime, see Chris Okasaki's book referenced below or my answer here. Of course, as an variant, each leaf of such a tree could itself contain an immutable array ...

7

I don't think the Tarjan and Mihaesau catenable deques have that lookup/modify performance. The non-catenable ones certainly do, though. I don't think there are any published simplifications since then. As far as I can tell, the T&M version wasn't ever published in a peer-reviewed venue. Publication about purely functional data structures seems to have ...

5

Chairman Tree is an alias of the data structure Functional Segment Tree. Its construction is fundamentally similar to a segment tree, only that it supports retroactive queries and modifications. Every retroactive version is created by attaching new child nodes to the old parent node without modifying the original child node. Clearly, as the depth of a ...

5

I've been doing competitive programming for several years at a very high level and haven't ever heard of a Chairman tree. Though I still can tell you how to make any data structure persistent. In case of BSTs and segment trees it even doesn't increase the running time (asymptotically, of course; you can notice some slowdown in practice). First, let's ...

5

Currently there's no "magic trick" to do an insertAt for RRB-trees: It can be implemented by doing concat(append(leftSlice(rrb, i), elt), rightSlice(rrb, i)) Append can (as I've shown in my thesis) be very efficient. If you don't want to focus on transients and tails, then chapter 5 explains how you modify the persistent vector append algorithm to work for ...

4

Such list is intended to be immutable - the shared nodes will never be written to. There is no problem with several threads reading from the same memory location.

4

I have described one implementation of such a data structure in my article about incremental regular expression matching - see http://jkff.info/articles/ire/#ropes-strings-with-fast-concatenation and the text below and above that section. It's a variety of a constant-height tree (like B-trees or 2-3 trees). Basically it's a (2,3) tree, whose leaves are (N, ...

4

Binary heaps are one possible implementations for priority queues. Although their operations are best understood as binary trees, their implementation as arrays is essential. They are stored efficiently, due to the perfect balance you mention, and do not need explicit pointers to children or parent (as these are found by calculating their index in the array)....

4

From first principles, every 2-3 tree is a finger tree viewed from another angle, so you could solve the problem by solving the somewhat easier problem of "What shape are the valid 2-3 trees of size $n$?" You can also look at many existing finger-tree libraries. The first one created, was, of course, the Haskell one. The function you are looking for is ...

4

Typically, confluently persistent data structures are built so that they will never have a merge conflict. The details differ for each such data structure, but here are the broad outlines. Basically, you define a semantics for what you want to happen during a merge, then devise a data structure with those semantics. (The desired semantics depends on the ...

3

{- Yes, you can implement a priority queue using a complete binary tree in a purely functional way. You don't need parent pointers or pointers to the left or right most elements to get the same asymptotic complexity as the usual binary heaps. This post is Haskell, with the prose enclosed in comments. You can copy and paste it and it should work in GHC 7.6....

3

Yes, you can do this in $O(\log n)$ time. Use a sweep-line algorithm together with a persistent tree data structure. Imagine the point $(d_1,d_2)$ as being on a grid, with $d_1$ as the value of the $x$-coordinate and $d_2$ as the value of the $y$-coordinate. Your sweep line is a horizontal line, namely, at time $t$, the sweep line is the line $d_2=t$. ...

2

I want to understand at a low level what would happen if the data structure is not persistent? Let's look at a pseudorandom number generator with a huge state space (like "Mersenne twister" with a state of 2450 bytes) as a data structure. We don't really want to use any random number more than once, so there seems to be little reason to implement this as an ...

2

Adding to others' answers, and reinforcing a mathematical approach, functional programming also has a nice synergy with Relational Algebra, and Galois Connections. This is extremely useful in the area of Formal Methods. For instance: Formal proofs in program verification are simplified with Extended Static Checking; A number of properties from Relational ...

2

If your data are constant, most data structures are persistent. (Not self-adjusting ones like splay trees or the union-find structure of Tarjan) You can do "three-sided range queries" with a priority search tree in $O(k + \log n)$ time, where $k$ is the number of items returned.

1

How cool is it to be in a field and an age where Jean Niklas L'orange can answer your questions? That's a great response! Another approach to consider is to localize the "focus". The focus is analogous to the "tail" in Rich Hickey's PersistentVector. It's a little buffer to take new items added to the vector without having to update the tree for each of ...

Only top voted, non community-wiki answers of a minimum length are eligible