F#类型的递归树结构

Question

我仍然是F#的新手,并试图找出如何制作我自己的类型,可以容纳任何数量的"A"之前,如果最终应该如何一个值.

作为一个例子,它可能像:

A(A(A(A(A(0))))).

如果我尝试制作这样的类型,我试着像这样声明:

type test = 
          | A of int
          | A of test;;

它告诉我,我不能声明两次相同的类型,因为我有重复.有没有办法解决这个问题,或者我真的需要让最后一个节点成为另一个名字:

type test = 
          | B of int
          | A of test;;

结果将是:

A(A(A(A(B(0)))))

有什么帮助吗？

Answer 1

我不确定这是否适合您的其他限制(您没有告诉我们),但这可以通过使类型通用来轻松完成:

type test<'a> = A of 'a

let a0 = A 0
let a1 = A(A(0))
let a5 = A(A(A(A(A(0)))))

这种方法具有这样的特性:具有不同数量的As的值具有不同的类型 - 即在上面的片段中,a0具有类型test<int>,但a1具有类型test<test<int>>.这是优势还是劣势取决于您的大背景.

话虽这么说,我发现自己想知道为什么你想要首先这样做,除了作为语言句法的抽象练习.也许如果您澄清根问题和/或域名,社区将能够更好地帮助您.

Answer 2

其他人提出了解决方法,但我建议你真的不想要A(A(A(A(A(0)))))你的想法,而且A(A(A(A(B(0)))))(语言试图迫使你进入)是一个更好的选择.

我们来看看你的树型.您有两种不同的东西:包含其他树节点的树节点或包含数据的树节点.你要做的是用同一个名字称这两件事:

type test =
          | A of int
          | A of test

这些名称不是特别描述性的.我们将它们重命名为

type Tree =
          | Node of int
          | Node of Tree

现在当你正在处理你的树结构时,你需要告诉"Node of int"除了"树节点"之外的情况:如果它是"int of Node",你会想要(比如说) )提取int并在计算中使用它.但如果它是一个"树的节点",你会想要(比方说)进一步深入到树形结构中,最终到达彩虹尽头的金罐...我的意思是,在结束时的int树.

所以你需要编写match如下结构:

let rec diveTree calculation node =
    match node with
        | Node a -> match a with
                    | :? int -> calculation a
                    | :? Tree -> diveTree calculation a

但是,如果我们做了F#试图强迫你做的事情,并使用不同的名称"包含一个int"和"包含另一个树"的情况怎么办？然后你的类型看起来像:

type Tree =
          | LeafNode of int
          | TreeNode of Tree

和match结构将如下所示:

let rec diveTree calculation node =
    match node with
        | LeafNode a -> calculation a
        | TreeNode a -> diveTree calculation a

我想你会发现后者比前者更容易阅读和理解.而这也就是为什么F#,您需要使用不同的标签可识别联合的不同情况.