Представление дерева в 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 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

Есть несколько способов подойти к этому, и Даниэль хорош. Но вот еще один способ (также с использованием дискриминантных объединений) определить рекурсивную структуру данных, которая немного ближе к вашему собственному подходу (хотя я думаю, что на самом деле я мог бы предпочесть подход Дэниела, поскольку случаи более явные):

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)