tree - 本地编辑纯功能树

Question

让我们定义一棵树 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 的路径。

我发现有两种可能的方法来解决这个问题:

• 父引用 - 这样，每个节点都能够导出其到根的路径。两个问题:创建两个相互引用的节点(即父节点 <-> 子节点)是纯函数式语言中的一个问题(有简单的解决方案吗？)；并且每当导出 E -> E' 时，所有 E' 的子级也需要重新导出，因为它们现在存储 E 的旧值而不是 E'。
• zippers - 每个节点在创建时都会存储一个从其父 zipper 派生的 zipper 。相互引用的问题消失了，但是，当 E -> E' 导出时，E' 的所有子 zipper 也需要导出，因为它们现在指向旧树 E。

在考虑到合理的性能的情况下，我想要的是否可能实现？非常感谢您的任何意见!

Answer 1

另一个选择， 基于延迟替换。 如果它对性能至关重要并且需要对其进行大量更改，我建议对其进行基准测试。

我已经在 F# 中实现了它，但是我认为除了打印功能之外我没有使用任何“不纯粹”的东西。

这是一堵文字墙， 基本原则是让树保持惰性， 通过替换返回节点的函数来替换节点。

诀窍是您需要某种方法来识别节点，这不是它自己的引用/名称，也不是通过值。 标识必须可复制到替换节点上 在本例中，我使用了 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)



    }

测试用例/示例:

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 定义，以便保留它所替换的节点的 ID。 (不仅返回 newNode，而是返回另一个具有 value 的新节点，以及 newNode 的 getChildren >，但是 nodetoReplace 的 originalRefId)