我们如何在 SML 中编写递归函数？

Question

这是我正在实现的递归函数的 python 代码。

def f(x):
  return x+1
def iter(n, f,x):
  if n == 0:
    return x
  return iter(n-1, f, f(x))

正在调用 iter

iter(7, f, 9)

如何用 SML 编写它？

fun iter 0 f x = x
  |iter n f x = iter(n-1, f, f(x));

Answer 1

语法是：

fun iter 0 f x = x
  | iter n f x = iter (n-1) f (f x);

注意：您可以在第 1 行将 f 替换为 _，因为 f 不会出现在结果表达式中。

Answer 2

OP 代码混合了柯里化函数符号和元组符号。 OP 定义了一个柯里化函数，然后在递归调用中将一个元组传递给它。有两个明显的解决方案：决定是否需要柯里化表示法或元组表示法，并始终如一地使用它。

使用元组表示法 iter 接受一个包含参数的元组，即，这里 iter 实际上只接受一个参数，它是一种数据类型，包含参数。也就是说，元组 iter 的类型为：fn : int * ('a -> 'a) * 'a -> 'a

fun iter (0, _, x) = x
  | iter (n, f, x) = iter(n-1, f, f x);

上面的表达方式可能有点不同，例如iter((n-1), f, (f x))，或iter((n-1), f, f(x))。

使用柯里化符号 iter 接受单个 int 参数和 returns 接受函数参数的函数，返回一个接受与传递函数匹配的参数的函数。也就是说，curried iter 的类型为 fn : int -> ('a -> 'a) -> 'a -> 'a.

fun iter 0 _ x = x
  | iter n f x = iter (n-1) f (f x);

元组版本和柯里化版本是两种截然不同的情况。对于元组版本，如果传递的“参数”少于三个，则会出现类型错误，例如：

- iter(2, double);
stdIn:1.2-1.17 Error: operator and operand do not agree [tycon mismatch]
  operator domain: int * ('Z -> 'Z) * 'Z
  operand:         'Y[INT] * (int -> int)
  in expression:
    iter (2,double)

问题是元组版本需要一个包含三个字段的元组参数。传递少于三个字段的元组违反了这一预期。

但是对于 curried 版本，如果你传递的参数少于三个，你就会有一个偏函数应用程序：

- val doubleTwice = iter 2 double;
val doubleTwice = fn : int -> int
- doubleTwice 3;
val it = 12 : int
- doubleTwice 5;
val it = 20 : int

此处，仅向柯里化 iter 传递两个参数，其中一个 double 函数将 int 加倍， returns 将输入加倍的函数价值两倍。 Curried 函数可能非常有用，您需要了解这两种样式之间的区别。

我们如何在 SML 中编写递归函数？

How do we write Recursive function in SML?

sml

smlnj