如何使用递归数据类型在 ML 中创建函数

Question

给定数据类型：

datatype bunch = One of int
               | Group of bunch list;
datatype 'ex bunch = NIL
                   | One of 'ex
                   | Group of 'ex * 'ex bunch;

如何设计一个函数，例如返回此递归函数的总和。我了解如何定义递归函数以及如何使用它，但我找不到 'ex 如何在线更改数据类型束的指示，也找不到我的任何其他参考文献。

Answer 1

您的第二个定义使 bunch 数据结构多态，即它可以包含任何类型的数据。例如Group(3, One 2)是一个int一串，而Group("三", One "二")是一个<代码>字符串束。值 NIL 的类型为 'a一堆，其中 'a 代表任意类型（即 NIL 的类型为int Bundle 和类型String Bundle 以及...）。

您的目标“返回此递归函数的总和”没有意义：您没有递归函数。如果您的意思是“返回此归纳数据结构的总和”，那么仍然不清楚您想要什么，您需要更准确地了解非数字集合的数据结构的总和的含义。

以下函数计算 int 串 中的整数之和。正如您将其输入到 ML 解释器中所看到的，其类型为 int chunk -> int，也就是说，它只能作用于整数串（否则 + 运算符就没有意义）。

fun bunch_sum NIL = 0
  | bunch_sum (One x) = x
  | bunch_sum (Group (x, b)) = x + bunch_sum b;

以下函数计算任意元素类型的一堆中的元素数量（如其类型“a一堆->int”所示）。您可以定义这样一个多态函数的原因是，它不需要查看该组元素的内部即可进行操作：它是参数多态的。

fun bunch_count NIL = 0
  | bunch_count (One x) = 1
  | bunch_count (Group (x, b)) = 1 + bunch_count b;

（在生产程序中，此类函数应该使用尾递归算法，以不太清晰但资源消耗更少的方式编写。）

由于簇类型几乎与列表同构，因此您可以查看实现的标准列表的源代码图书馆寻找灵感。