Locally editing a purely functional tree

Question

Let's define a tree T:

    A
   / \
  B   C
 / \
D   E

Let's say a new node is added to E, yielding T':

    A
   / \
  B   C
 / \
D   E
     \
      G

In a mutable language this is an easy task - just update E's children and we're done. However, in an immutable world it is necessary to first know the path to E, then derive E' from E + new child, then derive B' and then finally A' ( = T').

This is cumbersome; ideally, there would be some function that would take the values of E and G (and possibly T) and produce T', without supplying the path to E.

I see two possible ways to attack this problem:

• parent references - this way, every node would be able to derive its path to the root. Two problems: creating two mutually referencing nodes (i.e. parent <-> child) is a problem in a purely functional language (any easy solutions?); and whenever E -> E' is derived, all of E''s children need to be newly derived as well, since they now store the old value of E instead of E'.
• zippers - every node stores a zipper on creation, derived from its parent zipper. The mutually referencing problem disappears, but still, when E -> E' is derived, all of E''s childrens' zippers need to be derived as well, since they now point to the old tree E.

Is what I desire even possible with a reasonable performance in mind? Many thanks for any input!

Answer 1

Another Option, based around doing a Lazy Replace. If it is performance critical and will have alot of changes made to it, I would suggest benchmarking it.

I have implemented it in F#, however I don't think i've used anything "inpure" except for my printing function.

This is a bit of a wall of text, The basic principle is to keep the tree Lazy, replace the nodes, by replacing the function that returns the node.

The trick is you need some way to identify an node, that isn't it's own reference/name, and isn't by value. The identification has to be duplicable onto the ReplacementNodes In this case I have used System.Object's as they are referentially each distinct.

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/Example:

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

---

We saw at the end of the test that using an old node Name (/reference) for the object being replaced does not work. There is the option of creating a new type that has the reference Id of another node:

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

You could also edit the ReplacementNode definition, so that it preserves the ID, of the node it replaces. (by not just returning newNode, instead returning yet another new node that has the value, and getChildren of the newNode, but the originalRefId of the nodetoReplace)