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

Question

类型值如何:

type Tree =
    | Node of int * Tree list

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

对于Tree的合适定义,结果值应该等于以下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#编译器将生成一些初始化数据结构并填充递归引用的代码).最简单的方法是将refernece包装在一个惰性值中(函数也可以):

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

正如James所说,如果你不允许这样做,你可以拥有一些不错的属性,例如任何遍历数据结构的程序都将终止(因为数据结构是有限的,不能递归).所以,你需要对递归值更加小心:-)