如何在（功能）F# 中创建递归数据结构值？

Question

type: 的值如何

type Tree =
    | Node of int * Tree list

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

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

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

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

在命令式语言中，节点有一个包含其自身的子节点列表。我知道这可以在 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 })

Answer 2

如果递归引用没有延迟（例如包装在函数或惰性值中），则不能直接执行此操作。我认为动机是没有办法“立即”通过立即引用来创造价值，因此从理论角度来看这会很尴尬。

但是，F# 支持递归值 - 如果递归引用被延迟，您可以使用这些值（F# 编译器随后将生成一些代码来初始化数据结构并填充递归引用）。最简单的方法是将引用包装在惰性值中（函数也可以工作）：

type Tree = 
    | Node of int * Lazy<Tree list>

// Note you need 'let rec' here!        
let rec t = Node(0, lazy [t; t;])

另一种选择是使用突变来编写它。然后你还需要使你的数据结构可变。例如，您可以存储 ref 而不是 Tree：

type Tree = 
    | Node of int * ref<Tree> list

// empty node that is used only for initializataion
let empty = Node(0, [])
// create two references that will be mutated after creation    
let a, b = ref empty, ref empty

// create a new node
let t = Node(0, [a; b])
// replace empty node with recursive reference
a := t; b := t

正如 James 提到的，如果您不允许这样做，您可以拥有一些不错的属性，例如任何遍历该数据结构的程序都将终止（因为数据结构是有限的并且不能递归）。因此，您需要对递归值更加小心:-)