F#类型的递归树结构

Question

我对 F# 还是很陌生，我正在尝试弄清楚如何制作我自己的类型，它可以容纳任意数量的 "A"，如果最终值应该是多少。

例如，它可能是这样的：

A(A(A(A(A(0))))).

如果我尝试制作这样的类型，我会尝试这样声明它：

type test = 
          | A of int
          | A of test;;

它告诉我不能声明相同的类型两次，因为我有重复项。有什么办法可以解决这个问题，还是我真的需要将最后一个节点改成这样的另一个名称：

type test = 
          | B of int
          | A of test;;

然后结果将是：

A(A(A(A(B(0)))))

有什么帮助吗？

Answer 1

我不确定这是否符合您的其他限制（您没有告诉我们），但这可以通过将类型设为通用来轻松完成：

type test<'a> = A of 'a

let a0 = A 0
let a1 = A(A(0))
let a5 = A(A(A(A(A(0)))))

这种方法具有这样的特点，即具有不同数量 A 的值具有不同的类型 - 即在上面的代码片段中，a0 具有类型 test<int>，但 a1 具有类型 test<test<int>>。这是优点还是缺点取决于您的更大背景。

话虽这么说，但我发现自己想知道为什么您首先要这样做，除了作为语言语法的抽象练习。也许如果您澄清了您的根本问题 and/or 域，社区将能够更好地帮助您。

Answer 2

其他人提出了解决方法，但我建议您确实不希望 A(A(A(A(A(0))))) 您认为的方式，A(A(A(A(B(0)))))（语言试图强迫您into) 是更好的选择。

让我们看看你的树类型。您有两种不同的事物：包含其他树节点的树节点，或包含数据的树节点。您要做的是用相同的名称调用这两件事：

type test =
          | A of int
          | A of test

这些名称并不是特别具有描述性。让我们将它们重命名为

type Tree =
          | Node of int
          | Node of Tree

现在，当您处理树结构时，您需要区分 "Node of int" 案例和 "Node of Tree" 案例：如果它是 "Node of int"，您我会想（比如说）提取 int 并在计算中使用它。但如果它是 "Node of Tree"，你会想（比如说）进一步深入树结构，最终到达彩虹尽头的金罐……我的意思是，在树.

所以你需要编写一个 match 结构，如下所示：

let rec diveTree calculation node =
    match node with
        | Node a -> match a with
                    | :? int -> calculation a
                    | :? Tree -> diveTree calculation a

但是，如果我们做了 F# 试图强迫您做的事情，并为 "contains an int" 和 "contains another tree" 案例使用了 不同的 名称，会怎样？然后你的类型看起来像：

type Tree =
          | LeafNode of int
          | TreeNode of Tree

match 结构如下所示：

let rec diveTree calculation node =
    match node with
        | LeafNode a -> calculation a
        | TreeNode a -> diveTree calculation a

我想你会发现后者比前者更容易阅读和理解。那就是为什么 F# 要求您对不同情况的可区分联合使用不同的标签。

F#类型的递归树结构

F# type of recursive tree structure

tree

recursion

f#