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

당신은 list의 요소에 ref를 만드는 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 당신은 돌연변이가없는 비슷한 것을 할 수있는 흥미를 가질 것입니다.