Persistent Erlang Data Structures

Question

As I understand it, when creating a new list with an expression of type Erlang, L1 not copied, it just copies H

 L2 = [H|L1] 

Does Erlang have a constant data structure (see Permanent data structure ) for dict , that is, when adding / removing / changing nodes in the tree, only a few elements are copied (for example, Clojure )?

Answer 1

You misunderstood the situation when creating a list using [H|T] . As you say, T not copied, but not H All that happens is that a new list cell is added to T with reference to H as its head (its tail is T ). When working with lists, the only bits that are created are the actual cells of the list and never the data in each cell.

The same thing happens when working with dict . When you change (add / remove elements) in a dict , only the actual structure of the dict changed, not the actual data in the dict . It is also smart to only copy as little dict structure as possible for making changes.

So yes, Erlang has persistent data structures. In this respect, clojure is similar to Erlang (we were long before it).

Answer 2

In my experience, data structures for a library module do not degrade performance or memory pressure when they become larger.

For dict, it uses a dynamic hash table as an internal data structure, and the work is done essentially only on the bucket where the modification is performed.

I also looked in the gb_trees module where I found a comment:

Logarithmic behavior (as it should be).

And gb_trees is usually pretty fast, so I'm sure there are not many copies happening.

Generally, if you implement data structures like these in a language such as Erlang, you take care of copying problems, so there is no need to worry about that for the general library functions.

---

I am re-reading an article on persistent data structures: in the sense of this article, Erlang data structures are fully stable as well as confluent.