localmente la edición de un árbol puramente funcional

Question

Vamos a definir un árbol T:

A 
/\ 
    B C 
/\ 
D E 

Digamos que se añade un nuevo nodo a E, produciendo T ':

A 
/\ 
    B C 
/\ 
D E 
    \ 
     G 

En un lenguaje mutable se trata de una tarea fácil: simplemente actualice los hijos de E y terminamos. Sin embargo, en un mundo inmutable es necesario conocer primero el camino hacia E, luego derivar E 'de E + nuevo hijo, luego derivar B' y luego finalmente A '(= T').

Esto es engorroso; idealmente, no habría alguna función que tomaría los valores de E y G (y, posiblemente, T) y producir T', sin necesidad de suministrar la ruta a E.

veo dos formas posibles para atacar este problema:

• referencias principales: de esta forma, cada nodo podría derivar su ruta a la raíz. Dos problemas: crear dos nodos mutuamente referenciados (es decir, el padre < -> hijo) es un problema en un lenguaje puramente funcional (¿alguna solución fácil?); y cada vez que se deriva E -> E ', todos los hijos de E deben derivarse también nuevos, ya que ahora almacenan el valor anterior de E en lugar de E'.
• cremalleras: cada nodo almacena una cremallera en la creación, derivada de su cremallera principal. El problema de referencia mutua desaparece, pero aun así, cuando se deriva E -> E ', todas las cremalleras para niños de E deben derivarse también, ya que ahora apuntan al árbol anterior E.

¿Es lo que deseo incluso posible con un rendimiento razonable en mente? Muchas gracias por cualquier entrada!

Answer 1

Otra opción, basada en hacer un Lazy Replace. Si es crítico para el rendimiento y se le harán muchos cambios, sugeriría una evaluación comparativa.

Lo he implementado en F #, sin embargo, no creo haber usado nada "inpure" a excepción de mi función de impresión.

Esto es un poco de una pared de texto, El principio básico es mantener el árbol Lazy, reemplazar los nodos, reemplazando la función que devuelve el nodo.

El truco es que necesita alguna manera de identificar un nodo, que no es su propia referencia/nombre, y no es por su valor. La identificación tiene que ser duplicable en los ReplacementNodes En este caso he usado System.Object ya que son referencialmente distintos.

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) 



    } 

caso de prueba/Ejemplo:

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

---

vimos al final de la prueba que el uso de un viejo nombre de nodo (/ referencia) para el objeto que está siendo sustituido no trabajar. Existe la opción de crear un nuevo tipo que tiene el ID de referencia de otro nodo:

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

También puede editar la definición ReplacementNode, por lo que conserva la identificación, del nodo al que sustituye. (Por no acaban de volver newNode, en lugar de regresar otro nuevo nodo que tiene el value, y getChildren del newNode, pero el originalRefId del nodetoReplace)