F中的樹表示法＃

Question

我正試圖在F＃中使用元組列表實現一棵樹。
[a]其中a = (string, [a])
每個節點都有自己的孩子和葉子節點的列表將(name, [])

我希望能夠通過遞歸列表這樣的每一層迭代。

a 
b  e 
c d f g 

然而，它們並不總是二叉樹。

let t2 = [("a", [("b", [("c", []), ("d", [])]), ("e", [("f", []), ("g", [])])])] 

let rec checkstuff tple = 
    match tple with 
    | (_, []) -> true 
    | (node, children) -> 
     List.fold (||) false (List.map checkstuff children) 

我得到：

類型不匹配。統一''a'和''b * 'a list'

當期待
        ('a * 'b list) list
但給予
        'b list
產生的類型將是無限的有沒有一種方法可以讓我做這樣的事情還是不支持這樣的元組遞歸列表？

Answer 1

試着改變你的數據結構中的位：

type Tree = 
    | Branch of string * Tree list 
    | Leaf of string 

let t2 = Branch ("a", [Branch ("b", [Leaf "c"; Leaf "d"]); Branch ("e", [Leaf "f"; Leaf "g"])]) 

let rec checkstuff tree = 
    match tree with 
    | Leaf _ -> true 
    | Branch (node, children) -> 
     List.fold (||) false (List.map checkstuff children) 

Answer 2

有幾個方法可以解決這個，和丹尼爾的是好的。但是這裏有另一種方法（也使用判別聯合）來定義一個遞歸數據結構，這個方法與你自己的方法有些接近（儘管我認爲我可能更喜歡Daniel's，因爲這些例子更加明確）：

type tree<'a> = 
    | Node of 'a * list<tree<'a>> 

let t3 = Node("a", [Node("b", [Node("c",[]); Node("d",[])]); Node("e", [Node("f",[]); Node("g",[])])]) 

let rec checkstuff tple = 
    match tple with 
    | Node(_, []) -> true 
    | Node(node, children) -> 
     List.fold (||) false (List.map checkstuff children)