如何在（函数式）F＃中创建递归数据结构值？

Question

如何处理类型为：

type Tree =
    | Node of int * Tree list

在函数式编程中，如何生成一个引用自身的值？

对于一个合适的 Tree 定义，在以下 Python 代码中，生成的值应该等于 x：

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

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

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

- Muhammad Alkarouri

---

你能详细阐述一下这个问题吗，对于那些不太懂Python的人？你的类型定义看起来很好，但请注意，F#不允许直接构造一个区分联合类型（例如，Tree）...只允许构造联合值；例如Node，如"let x = Node(0, [])"或"let y = Node(1, [x])"，其中[]是空列表。 - James Hugard

@James：他想创建一个节点，它是自己的子节点。就像 let rec x = Node (something, [x])（但这样做不起作用）。 - sepp2k

@sepp2k：对于任何遍历列表的代码来说，这通常会创建一个无限循环，非常不可取 :-) 我在其他语言中看到过这样做来标记列表的结尾，但是惯用的 F# 会使用另一个 DU 值，比如“None”，来实现这个目的。 - James Hugard

你到底想做什么，而不是试图用 F# 语法写 Python 代码？值得一提的是，纯函数、循环数据结构会让人头疼（见 http://www.haskell.org/haskellwiki/Tying_the_Knot），你最好使用非循环数据结构编写代码。 - Juliet

@sepp2k：谢谢，这正是我所要的。 @Juliet：感谢您提供的链接。请参见上面编辑过的问题。 - Muhammad Alkarouri

@James：像这样的递归值在OCaml中是允许的，并且确实有用处，例如解释器中的递归闭包环境。 - J D

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 })

- kvb

---

有趣。从概念上讲，“a lst”的定义在某种意义上等同于“lazy list”吗？ - Muhammad Alkarouri

@Muhammad - 不，'a lst不是惰性的，所以它就像内置的列表一样。它通过记录进行的事实允许您创建自引用数据结构，但是您不能使用此类型来执行诸如创建所有偶数流之类的操作，就像您可以使用惰性列表一样。 - kvb

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;])

另一种选择是使用mutation来编写代码。这时你需要将数据结构变为可变的。例如，你可以存储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所提到的，如果您不允许这样做，您可以获得一些很好的属性，例如任何遍历数据结构的程序都将终止（因为数据结构是有限的且不能递归）。因此，您需要更加小心处理递归值 :-)

- Tomas Petricek

---

好答案。谢谢。从效率的角度来看，哪个更好？（不知怎么的，我感觉我会后悔;)） - Muhammad Alkarouri

“Lazy” 比 “ref” 更加复杂（它必须跟踪是否已经被评估），因此 “ref” 应该更有效率，但我怀疑实际上没有任何区别。 - GS - Apologise to Monica