8

类型的值如何：

type Tree =
    | Node of int * Tree list

有一个引用自身以功能方式生成的值吗？

在以下 Python 代码中，结果值应等于 x，以获得合适的 Tree 定义：

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

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

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

4

2 回答 2

9

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 })
于 2010-06-21T19:23:49.387 回答
7

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

但是，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>而不是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

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

于 2010-06-21T16:50:42.673 回答