3

私は F# の初心者で、次の問題に対する解決策を実装したいと考えていました: ランダムな順序で検出された一連のディスク パスから (例: "C:\Hello\foo" "C:" , "C:\Hello\bar " など....) ツリーを (効率的に) 構築する方法。仮定: シーケンスは有効です。これは、ツリーを効果的に作成できることを意味します。

そこで、ツリーを「その場で」文字列のリスト（「ブランチ」と呼ばれる分割されたパス）とマージする再帰関数（以下の「mergeInto」）で実装しようとしました

これが私の実装です。不変性により入力ツリーへの副作用が防止されるため、入力ツリーに参照セルを使用しようとしましたが、再帰で問題が発生しました。解決策はありますか？

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