我對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
「您遇到遞歸困難」 - 編譯或運行時錯誤? –
它編譯得很好,但結果不是預期的結果(請參閱代碼塊底部的測試中的第二個語句)。不考慮遞歸調用中的「副作用」。但在遞歸的第一級,它是可以的(見第一條語句) –