如何在(功能)F#中创建递归数据结构值? [英] How to create a recursive data structure value in (functional) F#?

问题描述

如何键入一个值:

type Tree =
    | Node of int * Tree list

是否具有引用以功能方式生成的自身的值?

have a value that references itself generated in a functional way?

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

The resulting value should be equal to x in the following Python code, for a suitable definition of Tree:

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

编辑:显然，更多的解释是必要的.我正在尝试学习F#和函数编程，所以我选择实现封面树之前已经用其他语言编程过.这里重要的是每个级别的点是下面级别的点的子集.该结构从概念上讲是无穷大.

Edit: Obviously more explanation is necessary. I am trying to learn F# and functional programming, so I chose to implement the cover tree which I have programmed before in other languages. The relevant thing here is that the points of each level are a subset of those of the level below. The structure conceptually goes to level -infinity.

在命令式语言中，节点具有包含其自身的子代列表.我知道可以在F#中强制执行此操作.不，在给定覆盖树算法的情况下，它不会创建无限循环.

In imperative languages a node has a list of children which includes itself. I know that this can be done imperatively in F#. And no, it doesn't create an infinite loop given the cover tree algorithm.

推荐答案

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

Tomas's answer suggests two possible ways to create recursive data structures in F#. A third possibility is to take advantage of the fact that record fields support direct recursion (when used in the same assembly that the record is defined in). For instance, the following code works without any problem:

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

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

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

Using this list type instead of the built-in one, we can make your code work:

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

这篇关于如何在(功能)F#中创建递归数据结构值?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！