Lokalnie edycji czysto funkcjonalny drzewa

Question

Zdefiniujmy drzewo T:

A 
/\ 
    B C 
/\ 
D E 

powiedzmy nowy węzeł jest dodawany do E, otrzymując T ':

A 
/\ 
    B C 
/\ 
D E 
    \ 
     G 

w języku zmienny jest to łatwe zadanie - wystarczy zaktualizować dzieci E i skończymy. Jednak w niezmiennym świecie należy najpierw poznać ścieżkę do E, następnie wyprowadzić E 'z E + nowego dziecka, następnie wyprowadzić B', a następnie ostatecznie A '(= T').

Jest to uciążliwe; Optymalnym rozwiązaniem byłby funkcję, która będzie przyjmować wartości E i G (i ewentualnie T) oraz produkcji T”, bez dostarczania ścieżkę E.

widzę dwa możliwe sposoby atakują ten problem:

• odniesienia dla rodziców - w ten sposób każdy węzeł będzie mógł wyprowadzić swoją ścieżkę do katalogu głównego. Dwa problemy: utworzenie dwóch wzajemnie się odwołujących węzłów (np. Rodzic < -> dziecko) jest problemem w czysto funkcjonalnym języku (dowolne łatwe rozwiązanie?); a ilekroć E -> E 'pochodzi, wszystkiewszystkich potomków E muszą być również nowo wyprowadzone, ponieważ teraz przechowują starą wartość E zamiast E'.
• zamki błyskawiczne - każdy węzeł przechowuje zamek błyskawiczny podczas tworzenia, wywodzący się z zamka nadrzędnego. Wzajemnie przedstawieniu problem znika, ale nadal, gdy E -> E”pochodzi, wszystkie E ''S zamki dziecięcych muszą pochodzić, jak również, ponieważ teraz wskazują na starym drzewie E.

Czy to, czego pragnę, jest możliwe, mając na uwadze rozsądny wynik? Wielkie dzięki za wszelkie dane wejściowe!

Answer 1

Inna opcja, oparta na wykonaniu lazy. Jeśli jest to krytyczne z punktu widzenia wydajności i wiele zmian zostanie w nim wprowadzonych, sugerowałbym przeprowadzenie testu porównawczego.

Zaimplementowałam go w języku F #, jednak nie sądzę, że użyłem czegoś "niedokładnego", z wyjątkiem funkcji drukowania.

To jest trochę ściany tekstu, Podstawową zasadą jest utrzymanie drzewa Lazy, zastąpienie węzłów, poprzez zastąpienie funkcji, która zwraca węzeł.

Podstęp polega na tym, że potrzebny jest jakiś sposób identyfikacji węzła, który nie jest jego własnym odnośnikiem/nazwą i nie ma wartości. Identyfikacja musi być duplikowana na ReplacementNodes W tym przypadku użyłem System.Object's, ponieważ są one odrębne dla każdego z nich.

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) 



    } 

Przypadek Testowy/Przykład:

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() 

---

Widzieliśmy na koniec testu, który przy użyciu starego nazwa węzła (/ odniesienia) dla obiektu zastępowane nie działa. Istnieje możliwość stworzenia nowego typu, który ma odniesienie ID innego węzła:

//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;} 

Można również edytować definicję ReplacementNode tak, że zachowuje identyfikatora węzła zastępuje. (Przez to nie tylko powrót newNode, zamiast wracać kolejny nowy węzeł, który ma value i getChildren z newNode, ale originalRefId z nodetoReplace)