F#中的树表示 [英] Tree Representation in F#

问题描述

我正在尝试使用元组列表在F#中实现一棵树.
[a]其中a = (string, [a])
每个节点都有其子节点列表，叶节点为(name, [])

I'm trying to implement a tree in F# using a list of tuples.
[a] where a = (string, [a])
Each node has a list of their children and leaf nodes would be (name, [])

我希望能够像这样递归地遍历列表的每个级别.

I want to be able to recursively iterate through each level of the list like this.

    a
 b     e
c d   f g

但是它们不会总是二叉树.

They wont always be binary trees however.

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'

Type mismatch. Expecting a
    ('a * 'b list) list
but given a
    'b list
The resulting type would be infinite when unifying ''a' and ''b * 'a list'

有没有办法做到这一点，或者不支持像这样的元组的递归列表?

Is there a way I can do something like this or is there not support for a recursive list of tuples like this?

推荐答案

尝试稍微更改数据结构:

Try changing your data structure a bit:

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)

这篇关于F#中的树表示的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！