使用F实现树生成器＃

Question

我对F＃很新，我想实现以下问题的解决方案： 从以随机顺序发现的磁盘路径序列（例如“C：\ Hello \ foo”“C： “，”C：\ Hello \ bar“等....）如何构建（高效）树。 假设：序列是有效的，这意味着树可以被有效地创建。

所以我试着用（在下面的“mergeInto”）的递归函数来实现其融合树“到位”与字符串列表（称为“分支”的分裂路线）

这里是我的实现中，不变性防止了输入树上的副作用，所以我尝试使用ref单元格作为输入树，但遇到递归困难。任何解决方案

open Microsoft.VisualStudio.TestTools.UnitTesting 

type Tree = 
    |Node of string*list<Tree> 
    |Empty 

let rec branchToTree (inputList:list<string>) = 
    match inputList with 
     | [] -> Tree.Empty 
     | head::tail -> Tree.Node (head, [branchToTree tail]) 

//branch cannot be empty list 
let rec mergeInto (tree:Tree ref) (branch:list<string>) = 
    match !tree,branch with 
     | Node (value,_), head::tail when String.op_Inequality(value, head) -> raise (ApplicationException("Oops invariant loop broken")) 
     | Node (value,_), [_] -> ignore() //the branch is singleton and by loop invariant its head is the current Tree node -> nothing to do. 
     | Node (value,children), _ -> 
           let nextBranchValue = branch.Tail.Head //valid because of previous match 

           //broken attempt to retrieve a ref to the proper child 
           let targetChild = children 
               |> List.map (fun(child) -> ref child) 
               |> List.tryFind (fun(child) -> match !child with 
                         |Empty -> false 
                         |Node (value,_) -> value = nextBranchValue) 
           match targetChild with 
            |Some x -> mergeInto x branch.Tail //a valid child match then go deeper. NB: branch.Tail cannot be empty here 
            |None -> tree := Node(value, (Node (nextBranchValue,[])) :: children)//attach the next branch value to the children 
     | Empty,_ -> tree := branchToTree branch 

[<TestClass>] 
type TreeTests() = 
    [<TestMethod>] 
    member this.BuildTree() = 
     let initialTree = ref Tree.Empty 
     let branch1 = ["a";"b";"c"] 
     let branch2 = ["a";"b";"d"] 

     do mergeInto initialTree branch1 
     //-> my tree is ok 
     do mergeInto initialTree branch2 
     //->not ok, expected a 
     //     | 
     //     b 
     //    /\ 
     //     d c 

Answer 1

你不能让一个ref的元素在list，改变ref，然后期望在list要更改的项目。如果你真的想这样做，那么你应该把参考文献放入你的Tree类型中。

type Tree = 
    |Node of string*list<Tree ref> 
    |Empty 

let rec branchToTree (inputList:list<string>) = 
    match inputList with 
     | [] -> Tree.Empty 
     | head::tail -> Tree.Node(head, [ref (branchToTree tail)]) 

如果你这样做，删除List.map (fun(child) -> ref child)一部分，那么你的代码工作。

您可能感兴趣zippers，它允许您做类似的事情，但没有变异。