Постоянная и неизменная структура данных

Есть ли разница в постоянной и неизменной структуре данных? Википедия ссылается на неизменяемую структуру данных при обсуждении настойчивости, но у меня есть ощущение, что между ними может быть тонкое различие.

Ответ 1

Неизменность - это метод реализации. Помимо прочего, он обеспечивает постоянство, являющееся интерфейсом. API-интерфейс persistence выглядит примерно так:

version update(operation o, version v) выполняет операцию o в версии v, возвращая новую версию. Если структура данных неизменна, новая версия представляет собой новую структуру (которая может разделять неизменяемые части старой структуры). Если структура данных не является неизменной, возвращаемая версия может быть просто номером версии. Версия v остается допустимой версией и не должна изменяться ни в каком observe -зависимом режиме из-за этого обновления - обновление отображается только в возвращенной версии, а не в v.
data observe(query q, version v) наблюдает структуру данных в версии v без изменения или создания новой версии.

Подробнее об этих различиях см. ниже:

Ответ 2

Да, есть разница. Неизменяемая структура данных никоим образом не может быть изменена после ее создания. Единственным способом эффективного его изменения было бы сделать изменчивую копию или что-то подобное (например, слегка изменив параметры, которые вы передаете конструктору нового). С другой стороны, постоянная структура данных изменена в том смысле, что открытый API, по-видимому, допускает изменения в структуре данных. Правда, однако, любые изменения будут содержать указатель на существующую структуру данных (и, следовательно, каждую предыдущую структуру); они только, кажется, мутируют структуру данных, потому что открытый API возвращает новый указатель, который может содержать указатели на подмножество предыдущей структуры данных (в деревьях, например, мы укажем на node, чье поддерево не изменилось как результат операции).