Как работает изменение состояния под капотом на функциональных языках

Question

Я хотел бы знать, как функциональные языки могут реализовать "под капотом" создание нового состояния, например, Vector.Когда у меня есть Вектор, и я добавляю еще один элемент в этот конкретный Вектор, старый все еще остается неизменным, и создается новый Вектор, содержащий старый, содержащий еще один элемент.

Как это обрабатывается внутри?Может ли кто-нибудь попытаться объяснить это?Спасибо.

Answer 1

Концептуально новый Вектор создается каждый раз, когда Вектор расширяется или изменяется. Однако, поскольку исходный Вектор не изменен, могут использоваться умные методы для разделения структуры. См. Например, веревки .

Также см. чисто функциональные структуры данных Okasaki.

Answer 2

Если вы добавляете элемент в связанный список, создается новый связанный список с новым элементом в качестве его заголовка и указателем на старый список в качестве его хвоста.

Если вы добавляете элемент в массив, обычно копируется весь массив (что делает неэффективным создание неизменяемого массива постепенно).

Однако, если вы добавляете в конец каждого массива только один раз, например:

arr1 = emptyArray()
arr2 = add(arr1, 1)
arr3 = add(arr2, 2)
arr4 = add(arr3, 3)

Все это можно оптимизировать, чтобы arr1, arr2, arr3 и arr4 имели указатели на одну и ту же память, но разную длину. Конечно, эта оптимизация может быть выполнена только при первом добавлении в любой массив. Если у вас есть arr5 = add(arr4, 4) и arr5prime = add(arr4, 42), по крайней мере, один из них должен быть копией.

Обратите внимание, что это не обычная оптимизация, поэтому не следует ожидать, что она будет там, если это явно не указано в документации.