F#中的树表示

Question

我正在尝试使用元组列表在F#中实现一个树.
[a]where 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 list) list
给定的一个,但
    'b list
统一时产生的类型将是无限的''a',并''b * 'a 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,因为案例更明确):

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)