使用F＃实现树构建器(Implement tree builder with F#)

 我是F＃的新手，我想实现以下问题的解决方案：从随机顺序发现的一系列磁盘路径（例如“C：\ Hello \ foo”“C：”，“C：\ Hello \ bar “等......）如何构建（有效）树。 假设：序列有效，这意味着可以有效地创建树。 
 
 所以我尝试使用递归函数（下面的“mergeInto”）实现，该函数将树“就地”与字符串列表（称为“branch”的分割路径）合并在一起 
 
 这是我的实现，不变性防止了对输入树的副作用，所以我尝试使用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 

I am pretty new to F# and I wanted to implement a solution to the following problem: From a sequence of disk paths discovered in random order (e.g. "C:\Hello\foo" "C:" , "C:\Hello\bar" etc....) how to build (efficiently) the tree. Assumption: the sequence is valid, which means the tree can be effectively created.
 
So I tried to implement with a recursive function ("mergeInto" in the following) which merges the tree "in place" with a list of string (the splitted path called "branch")
 
Here is my implementation, the immutability prevents side effects on the input tree, so I tried to use a ref cell for the input Tree but I encounter difficulty with the recursion. Any solution ?
 
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 

原文：https://stackoverflow.com/questions/17364840