Episode #125 of the Stack Overflow podcast is here. We talk Tilde Club and mechanical keyboards. Listen now

Questions tagged [persistent-data-structure]

A persistent data structure is a data structure that is never modified in place, but by creating a new data structure.

Filter by
Sorted by
Tagged with
21
votes
4answers
3k views

Why do we use persistent data structures in functional programming?

Functional programming employs persistent data structures and immutable objects. My question is why is it crucial to have such data structures here? I want to understand at a low level what would ...
18
votes
1answer
2k views

What classes of data structures can be made persistent?

Persistent data structures are immutable data structures. Operations on them return a new "copy" of the data structure, but altered by the operation; the old data structure remains unchanged though. ...
11
votes
2answers
2k views

Array-like immutable (persistent) data structure implementation with fast indexing, append, prepend, iteration

I'm looking for a persistent data structure similar to array (but immutable), allowing for fast indexing, append, prepend, and iteration (good locality) operations. Clojure provides persistent Vector,...
5
votes
2answers
423 views

Is it possible to build a heap from the root to the leaves?

Most books on data-structures will briefly introduce heaps (aka priority queues) and then move to describe the "trick" allowing heaps to be implemented as arrays. I've been looking for a way to ...
5
votes
1answer
125 views

What progress has been made on persistent catenable deques in the last decade?

I'm interested in persistent catenable deques: deques that can be concatenated. Kaplan and Tarjan came up with the first such data structure in 1995; Okasaki came up with a simpler, amortized version ...
4
votes
2answers
428 views

How append, prepend, and generally insertAt work in RRB-tree

I read the paper about Relaxed Radix Balanced trees (RRB trees) and am trying to implement them. What I can't get is how insertion at an index should be performed step by step. Can anyone proficient ...
4
votes
1answer
87 views

How do confluently persistent data structures handle merge conflicts?

From my limited understanding fully persistent data structures allow changes to be made to previous nodes, with new nodes creating a branch rooted at the changed node, resulting in a tree of nodes and ...
3
votes
2answers
611 views

What is the “Chairman Tree”?

My competitive programming coach told me of a balanced binary tree used by a lot of Chinese competitors that has all the functions of any other balanced binary tree and is fully persistent and runs ...
3
votes
2answers
123 views

Using persistence on a constant database

I'm quite new to understanding persistent data structures, so bear with me. Consider some database with data of the form $(\text{id}, d_1, d_2)$. The last two could e.g. mean production data and ...
3
votes
1answer
75 views

Guessing the structure of a finger tree from the number of elements

I'm writing a data structure library, and I want to write an efficient algorithm for adding many elements to a finger tree (from an iterable sequence). I'm going to do this by constructing a finger ...
3
votes
0answers
57 views

Persistent data structures representing a directed graph's paths

Are there any standard persistent data structures that facilitate the following? tabulating, for each arc in a rooted, oriented, acyclic multigraph, the set of root-emanating paths containing the arc ...
2
votes
0answers
21 views

Formal semantics of a mutable/imperative stack

When introducing formal semantics for data structures, immutable stacks are a nice simple example : $\mathit{is\_empty}(\mathit{create()})=\mathrm{True}$ $\mathit{is\_empty}(\mathit{push}(e, s))=\...
2
votes
0answers
27 views

Distributed Computing: Persistent Data Structures in Functional Programming versus Wait-Free Data Structures

Persistent (aka immutable) data structures in functional programming sidestep issues of shared memory mutual exclusion, and thus also issues such as data races that arise and which may be difficult to ...
2
votes
0answers
44 views

Persistent data structure with double and subtract operations

I am seeking a data structure that maintains an array of N numbers and supports the following two operations: Double the first i numbers Subtract the first i numbers of a previous version from the ...
1
vote
1answer
254 views

Multithreaded access to a persistent linked list data structure

I previously asked a question about persistent data structures here. After that I came across an article that introduced persistent data structures. I have got a question on the following figure from ...
1
vote
0answers
58 views

combine divergent persistent red-black tree instances

Given a persistent red-black tree, I've been searching for an algorithm, approach, or equivalent data structure that allows me to efficiently merge two instances of the tree produced by divergent ...
0
votes
0answers
22 views

Do parent pointers affect path-copying in a persistent binary tree?

I am familiar with the concept of path-copying in the context of binary trees to achieve persistent modifications, but I am unsure if the inclusion of parent pointers has any effect on the complexity. ...
0
votes
0answers
33 views

How do Clojure's persistent data structure determine equality?

I'm trying to understand the time complexity of determining equality between persistent data structures in Clojure (Vectors, Maps, Sets, etc.). These are based on data structures pioneered by Phil ...
0
votes
0answers
213 views

Analysis of finding the k-th largest element in a subsegment of an array

Given an array $A$ of length $N$. There are $Q$ queries, each queries will be in the form ...
0
votes
0answers
34 views

What is a good rule-of-thumb for the size of leaf nodes in a rope?

The formal descriptions of ropes I’ve found use very small numbers like 4 or 8 characters per leaf node as the maximum size. Some also mention that this (obviously) is not a very efficient rope size ...
0
votes
0answers
69 views

Immutable data structures for 2d+ lattices

I would like to find an immutable/persistent data structure that allows efficient updating for 2d (or higher) lattices/arrays/matrices, and reasonable performance when appending in any direction. ...