Локальное редактирование чисто функционального дерева

Давайте определим дерево T:

    A
   / \
  B   C
 / \
D   E

Скажем, новый узел добавлен к E, что дает T ':

    A
   / \
  B   C
 / \
D   E
     \
      G

В изменяемом языке это это простая задача - просто обновите дочерние элементы E, и все готово. Однако в неизменяемом мире необходимо сначала узнать путь к E, затем получить E 'из E + новый дочерний элемент, затем получить B' и, наконец, A '(= T').

Это громоздко; в идеале была бы какая-то функция, которая принимала бы значения E и G (и, возможно, T) и производила бы T ', не указывая путь к E.

Я вижу два возможных способа решения этой проблемы:

• родительские ссылки - таким образом, каждый узел сможет получить свой путь к корню. Две проблемы: создание двух взаимно ссылающихся узлов (т.е. parent <-> child) - проблема чисто функционального языка (есть ли простые решения?); и всякий раз, когда E -> E 'выводится, все дочерние элементы E также должны быть получены заново, поскольку теперь они хранят старое значение E вместо E'.
• застежки-молнии - каждый узел при создании сохраняет застежку-молнию, производную от ее родительской застежки-молнии. Проблема взаимной ссылки исчезает, но все же, когда E -> E 'получено, все детские молнии E также должны быть получены, так как теперь они указывают на старое дерево E.

Это то, что я желание даже возможно с разумной производительностью? Большое спасибо за любой вклад!