Which term to use when referring to functional data structures: constant or unchanged?

Question

In the context of functional programming, which is the right term to use: constant or immutable? When I google "immutable data structures", I get a Wikipedia link in the article "Permanent data structure", which even continues to say:

such data structures are effectively immutable

What else bothers me. Functional programs rely on persistent data structures or immutable data structures? Or are they always the same?

Answer 1

Permanent struth data saves only the previous version of itself after the change. Depending on the type of persistent data structure ... you may or may not be able to change previous versions.

An immutable type cannot be changed at all.

Functional languages ​​mainly rely on immutable types (also called values) to store data (although you can use Mutable types in some ... but this should be done explicitly).

Answer 2

The correct term for functional data structures is immutable . Teerm "persistent" is used in at least three ways:

• A persistent data structure refers to a situation where you have an old data structure, you create a new one, but keep a pointer to the old one. As a rule, old and new are shared by many states: they can differ only by a constant number of heap objects or, possibly, by a linear number of heap data structures. Such constancy is a consequence of the presence of unchanged data structures, as well as an algorithm that stores pointers to old versions of the data structure, which allows them to be saved.

• A persistent variable is a value whose value is stored in several calls of the same program. This can be done using language features or libraries.

• A persistent programming language is one that provides constant variables. The Holy Grail is orthogonal persistence : a programmer can decide whether a variable is constant, regardless of all other properties of that variable. At the moment, such a programming language is far-reaching research, but it is useful to preserve the terminological difference.

I do not want to edit Wikipedia today: - (

Answer 3

The article also says that "in a purely functional program, all data is immutable", which is true.

In my opinion, you really do not need to make this distinction. If you are programming in a functional language or in a fully functional style - as opposed to using functional idioms in imperative code, where convenient - then you can simply say "data structure". By definition, they will be unchanging and permanent.

If you need to make a distinction for some reason, then “persistent” may be more suitable for dynamic structures such as trees and queues, where values ​​are “modified” based on execution traces and “unchanged” for simple value objects.

Answer 4

Immutable usually means "not changing." Persistence is usually perceived as "stored on a permanent medium." However, the Wikipedia article mentioned seems to perceive these two words as very similar things (but not exact). In fact, it says:

A persistent data structure is not a data structure intended for permanent storage, such as a disk; it is a different and unrelated sense of the word "persistent."

Answer 5

“Immutable” is used much more often because “persistent” is overloaded (usually it means “stored outside and burns the program”), and even the correct definition carries additional semantic baggage, which is often not connected with distinctive quality, purely functional programming - the fact that there isn’t volatile state. A = A and will always be for all values ​​of A.

Answer 6

In this article, the authors use the word "persistent," which means "observationally unchanged, albeit implemented with mutations under the hood." In this particular case, mutations are hidden by a modular system of a functional, but not pure programming language.