Локальное редактирование чисто функционального дерева - PullRequest
Новая
       31

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

10 голосов
/ 27 января 2012

Давайте определим дерево T: 

    A
   / \
  B   C
 / \
D   E

Допустим, к E добавлен новый узел, в результате чего T ': 

    A
   / \
  B   C
 / \
D   E
     \
      G

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

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

Я вижу два возможных способа решения этой проблемы:

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

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

1 Ответ

1 голос
/ 07 сентября 2013

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

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

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

Хитрость в том, что вам нужен какой-то способ идентификации узла, который не является собственной ссылкой / именем и не по значению.Идентификация должна дублироваться на узлы замены. В этом случае я использовал объекты 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()

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

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

...