3

我对 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
4

1 回答 1

2

您不能对 aref中的元素进行 alist更改ref，然后期望 the 中的项目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)部分，然后您的代码将起作用。

您可能对拉链感兴趣，它可以让您做类似但没有突变的事情。

于 2013-06-28T13:41:05.097 回答