Как я могу манипулировать деревом неизменяемых объектов?

Я создаю цельное приложение из неизменяемых объектов, чтобы упростить реализацию многопоточности и отмены. Я использую Библиотека коллекций Google, в которой содержатся неизменные версии Map, List и Set.

Моя модель приложения выглядит как дерево:

Сцена - это объект верхнего уровня, содержащий ссылку на корень Node.
Каждый Node может содержать дочерние узлы и порты.

График объектов может выглядеть так:

Scene
 |
 +-- Node
      |
      +-- Node 
           |
           +- Port
      +-- Node
           |
           +- Port
           +- Port

Если все эти объекты неизменяемы, они контролируются объектом SceneController верхнего уровня:

Каков наилучший способ построения этой иерархии?
Как заменить объект, который является сколь угодно глубоким в дереве объектов?
Есть ли способ поддерживать обратные ссылки, например. a Node с атрибутом "parent"?

И в целом:

Появились ли какие-либо шаблоны для работы с данным типом данных?
Есть ли (академическая) литература по этому вопросу?
Это хорошая идея?

Ответ 1

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

Например, если вы должны добавить третий порт к Node, который уже имеет два порта, вам нужно будет создать новую сцену, новый потомок сцены Node и Node, который вы меняются. Другой Node и все порты не нужно создавать заново - вы просто ссылаетесь на них в новых сценах/узлах.

Другая концепция - концепция Zipper. Застежка-молния - это способ "перемещаться" через постоянную структуру данных для оптимизации локальных изменений. Например, если вы добавили четыре новых порта вместо одного, но вы добавили каждый порт по одному, вам нужно будет создать четыре новых сценария и восемь новых узлов. С застежкой-молнией вы откладываете такие творения, пока не закончите, сохраняя эти промежуточные объекты.

Лучшее объяснение, которое я когда-либо читал о молнии, здесь.

Теперь использование застежки-молнии для навигации по структуре данных избавит вас от необходимости иметь обратные ссылки. Вы можете иметь обратные ссылки в неизменной структуре, умело используя рекурсивные конструкторы. Однако такая структура данных не будет постоянной. Непрерывные неизменные структуры данных имеют плохую производительность модификации, потому что вам нужно копировать все данные каждый раз.

Что касается академической литературы, я рекомендую Структуры данных с чисто функцией, Окасаки (PDF диссертаций, полноценная книга).

Ответ 2

Если ваше дерево неизменно, то если вы хотите изменить его, вы должны создать новое дерево.

Звучит неплохо, но его нет, если все ваши узлы также неизменяемы! Поскольку вам не нужно делать копии неизменяемых объектов, ваше новое дерево будет в основном ссылаться на старое дерево, кроме тех изменений, которые вы сделали.

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

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