f# - 如何在(功能性)F# 中创建递归数据结构值？

Question

类型的值如何:

type Tree =
    | Node of int * Tree list

有一个以函数方式生成的引用自身的值？

对于合适的 Tree 定义，结果值应等于以下 Python 代码中的 x:

x = Tree()
x.tlist = [x]

编辑 : 显然需要更多的解释。我正在尝试学习 F# 和函数式编程，所以我选择实现 cover tree我以前用其他语言编程过。这里相关的一点是，每个级别的点数都是下一个级别的点数的子集。该结构在概念上达到无限级。

在命令式语言中，一个节点有一个包含它自己的子节点列表。我知道这可以在 F# 中强制完成。不，鉴于覆盖树算法，它不会创建无限循环。

Answer 1

Tomas 的回答提出了两种在 F# 中创建递归数据结构的可能方法。第三种可能性是利用记录字段支持直接递归的事实(当在定义记录的同一个程序集中使用时)。例如，以下代码可以正常工作:

type 'a lst = Nil | NonEmpty of 'a nelst
and 'a nelst = { head : 'a; tail : 'a lst }

let rec infList = NonEmpty { head = 1; tail = infList }

使用此列表类型而不是内置列表类型，我们可以使您的代码正常工作:

type Tree = Node of int * Tree lst
let rec x = Node(1, NonEmpty { head = x; tail = Nil })