2013-06-28 62 views
3

我對F#很新,我想實現以下問題的解決方案: 從以隨機順序發現的磁盤路徑序列(例如「C:\ Hello \ foo」「C: 「,」C:\ Hello \ bar「等....)如何構建(高效)樹。 假設:序列是有效的,這意味着樹可以被有效地創建。使用F實現樹生成器#

所以我試着用(在下面的「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 
+1

「您遇到遞歸困難」 - 編譯或運行時錯誤? –

+0

它編譯得很好,但結果不是預期的結果(請參閱代碼塊底部的測試中的第二個語句)。不考慮遞歸調用中的「副作用」。但在遞歸的第一級,它是可以的(見第一條語句) –

回答

2

你不能讓一個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,它允許您做類似的事情,但沒有變異。

+0

這解決了我的問題,但它迫使我改變這個特定結構的數據結構。也許,「我的」樹型的其他用法不需要​​ref單元格。我會仔細閱讀你關於拉鍊的鏈接。謝謝。 –

+0

事實上,拉鍊正是我所期待的。我回顧了算法並寫了一篇文章:[link] http://benoitpatra.com/2013/07/24/rethink-a-basic-tree-algorithm-with-purely-functional-data-structures-the-zippers/ –

+0

寫得很好,謝謝分享這篇文章。 –