1

给定数据类型:

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

例如,我如何设计一个函数来返回这个递归函数的总和。我了解如何定义递归函数以及如何使用它,但我找不到关于 'ex 如何在线更改数据类型群或我的任何其他参考资料的指示。

4

1 回答 1

0

您的第二个定义使bunch数据结构多态,即它可以包含任何类型的数据。例如Group (3, One 2)是一个int bunch,并且Group ("three", One "two")是一个string bunch。该值NIL具有代表任何类型的类型(即'a bunch具有类型和类型以及...)。'aNILint bunchstring bunch

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

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

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

以下函数计算具有任何元素类型(如其类型所示'a bunch -> int)的束中元素的数量。你可以定义这样一个多态函数的原因是它不需要查看一堆元素的内部来操作:它是参数化的多态函数。

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

(在生产程序中,应该使用尾递归算法以不太清晰但较少占用资源的方式编写此类函数。)

由于束类型几乎与列表同构,因此您可以查看实现的标准列表库的来源以获得灵感。

于 2010-10-10T10:43:25.960 回答