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

Question

Определим дерево Т:

A 
/\ 
    B C 
/\ 
D E 

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

A 
/\ 
    B C 
/\ 
D E 
    \ 
     G 

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

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

Я вижу два возможных пути, чтобы атаковать эту проблему:

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

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

Answer 1

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

Я внедрил его в F #, однако я не думаю, что использовал что-либо «inpure», кроме моей функции печати.

Это немного текст, Основной принцип - сохранить дерево Lazy, заменить узлы, заменив функцию, которая возвращает узел.

Фокус в том, что вам нужно каким-то образом идентифицировать узел, это не его собственная ссылка/имя, а не по значению. Идентификация должна быть дублируема на ReplacementNodes В этом случае я использовал System.Object, так как они ссылочно различаются.

type TreeNode<'a> = { 
    getChildren: unit -> seq<TreeNode<'a>>; 
    value: 'a; 
    originalRefId: System.Object; //This is set when the onject is created, 
            // so we can identify any nodes that are effectivly this one 
    } 


let BasicTreeNode : 'a ->seq<TreeNode<'a>>-> TreeNode<'a> = fun nodeValue -> fun children -> 
    {value = nodeValue; originalRefId = System.Object(); getChildren = fun() -> children;} 


let rec ReplacementNode : TreeNode<'a> -> TreeNode<'a> -> TreeNode<'a> -> TreeNode<'a> = 
    fun nodeToReplace -> fun newNode -> fun baseNode -> 
     if (System.Object.ReferenceEquals(baseNode.originalRefId, nodeToReplace.originalRefId)) then 
      //If it has the same Oringal 
      newNode //replace the node 
     else 
      //Just another pass on node, tranform its children, keep orignial reference 
      {value = baseNode.value; 
      originalRefId = baseNode.originalRefId; 
      getChildren = fun() -> 
       baseNode.getChildren() |> Seq.map(ReplacementNode nodeToReplace newNode); } 


type TreeType<'a> = { 
    Print: unit -> unit; 
    ReplaceNode: TreeNode<'a> -> TreeNode<'a> -> TreeType<'a>; 
    //Put all the other tree methods, like Traversals, searches etc in this type 
    } 

let rec Tree = fun rootNode -> 
    { 
     Print = fun() -> 
      let rec printNode = fun node -> fun depth -> 
       printf "%s %A\n" (String.replicate depth " - ") node.value 
       for n in node.getChildren() do printNode n (depth + 1) 
      printNode rootNode 0 
      ; 
     ReplaceNode = fun oldNode -> fun newNode -> 
      Tree (ReplacementNode oldNode newNode rootNode) 



    } 

Test Case/Пример:

let e = BasicTreeNode "E" Seq.empty 
let d = BasicTreeNode "D" Seq.empty 
let c = BasicTreeNode "C" Seq.empty 
let b = BasicTreeNode "B" [d;e] 
let a = BasicTreeNode "A" [b;c] 
let originalTree = Tree a 
printf "The Original Tree:\n" 
originalTree.Print() 

let g = BasicTreeNode "G" Seq.empty 
let newE = BasicTreeNode "E" [g] 

let newTree = originalTree.ReplaceNode e newE 
printf "\n\nThe Tree with a Local Change: \n" 
newTree.Print() 

printf "\n\nThe Original Tree is Unchanged: \n" 
originalTree.Print() 


printf "\n\nThe Tree with a Second Local Change: \n" 
let h = BasicTreeNode "H" Seq.empty 
let newC = BasicTreeNode "C" [h] 
let newTree2 = newTree.ReplaceNode c newC 
newTree2.Print() 



printf "\n\nTrying to Change a node that has been replaced doesn't work \n" 
let i = BasicTreeNode "i" Seq.empty 
let newnewC = BasicTreeNode "C" [h; i] 
let newTree3 = newTree.ReplaceNode c newC //newTree.ReplaceNode newc newnewC would work 
newTree3.Print() 

---

Мы видели в конце теста, используя старое имя узла (/ ссылку) для объекта заменяются не работает. Существует возможность создания нового типа, который имеет ссылку Id другого узла:

//Like a basicTreeNode, but reuses an existing ID, so they can be replaced for oneanother 
let EdittedTreeNode = fun orignalNode -> fun nodeValue -> fun children -> 
    {value = nodeValue; originalRefId = orignalNode.originalRefId; getChildren = fun() -> children;} 

Вы также можете редактировать ReplacementNode определение, так что он сохраняет идентификатор узла его заменяет. (По не только возвращение newNode, но вместо возвращения еще один новый узел, который имеет value и getChildren в newNode, но originalRefId в nodetoReplace)