ML；复合函数n次

Question

如何在ML中合成函数f n次？

合成两次；f(Fx)合成三次；f(f(Fx)合成n次；f(f……(Fx)

我试过了；

fun composite f g =
          let h x = f(g x)
            in h end;

fun repeat f n =
       if n = 0 then x 
       else composite f repeat(f (n - 1));

谢谢

Answer 1

在编写递归函数时，请将问题分为一般情况、递归情况和不需要递归的基本情况。例如，将函数自身组合n次听起来像是基本情况可能是当n=0时或当n=1时(这两种情况都可以工作；我将回到那个问题)。

我鼓励模式匹配，但是当递归整数时，if-then-else看起来就像是一样简单。在任何情况下，所有的示例都是以两种样式编写的。简单的骨架可能是：

fun repeat f n =
    if n = 0
    then ?
    else ?

fun repeat f 0 = ?
  | repeat f 1 = ?
  | repeat f n = ?

关于返回函数的函数

我想这里的一些困难是repeat必须返回一个函数。从语法上讲，你可以通过各种方式来实现这一点。就像约翰建议的那样，您可以通过用x扩展repeat来编写它

fun repeat f n x =
    if n = 1
    then f x
    else ...

fun repeat f 1 x = f x
  | repeat f n x = ...

对它的自然但有点奇怪的解释是"repeat是一个带有三个参数的函数；函数f__，它必须应用于n__的次数，以及f__的参数x (?!)“。

或者，你也可以这样写它

fun repeat f n =
    if n = 1
    then (fn x => f x)
    else ...

fun repeat f 1 = (fn x => f x)
  | repeat f n = ...

这可能会被解释为"repeat是一个带有两个参数的函数；函数f和它必须应用n__的次数，并返回一个将f应用于其参数n次的函数。“

这些定义实际上是等价的。通过将描述转换为类型，您将看到这一点：

• val repeat : ('a -> 'a) -> int -> 'a -> 'a
• val repeat : ('a -> 'a) -> int -> ('a -> 'a)

最后一个括号隐含在第一个类型签名中。

有时，将具有许多curried参数的函数视为“具有多个参数的函数”会有所帮助，而有时将它们视为“返回带有其他参数的函数的函数”会有所帮助。而repeat似乎就是这样的混合体；n最好被认为是“第二个参数”，但x最好被认为是“我们要返回的函数接受的参数”。

有了这个偏好，以及对模式匹配的偏好，我推荐的基础是：

fun repeat f 0 = ...
  | repeat f 1 = f
  | repeat f n = ...

因为(fn x => f x)和f实际上是同一个函数。

关于基本情况和递归情况

您可以这样写：

fun repeat f n= if n=0则x否则复合f repeat(f (n - 1))；

1. then x中的x的类型错误，因为repeat f n必须返回函数。见上。
2. 当应用f零次时，情况有点棘手。无论结果如何，无论f如何，repeat f 0都应该给出相同的结果。或者换句话说，f没有被应用，尽管repeat f 0确实需要返回递归的情况，真的，你只是弄乱了括号。约翰透露了o操作符，这是标准ML的内置版本的composite，我也更喜欢它：

复合f (repeat f (n-1)) f o repeat f (n-1)

关于标准ML中的括号，您需要知道的是:添加它们主要是为了对事物进行分组。当您编写composite f repeat (f (n-1))时，您所说的是："composite是一个以f__、repeat和f (n-1)为参数的三参数函数“和"f是一个以整数为参数的函数”。

当你真正想说的是"composite取f和用它自己合成f的结果n__-1次，然后合成它们。“这是一个典型的错误，当你来自那些期望函数调用看起来像foo(arg1, arg, arg3)的语言时，有人认为这会翻译成foo(arg1 arg arg3)，而实际上你想要的是foo arg1 arg2 arg3。在标准ML中，此括号强制将arg1视为函数，并将其应用于arg2和arg3，并将foo应用于该结果。哇！

Answer 2

你的想法几乎是正确的。您可以使用currying来使它们工作：

fun composite f g x = f(g(x));

SML推断其类型为：

val composite = fn : ('a -> 'b) -> ('c -> 'a) -> 'c -> 'b

这对于组合来说是非常合适的。函数应用程序是左关联的，因此

composite f g x 

解析为

(composite f g) x

因此，函数定义读作给出了对参数x应用函数(composite f g)的含义。当然，其含义是返回值f(g(x))。

您可以对其进行测试：

fun square x = x*x
fun increment x = x + 1
val h = composite increment square

然后，例如h 5的计算结果如预期的那样为26。

类似的调整也适用于您的第二个定义。它可以开始：

fun repeat f n x =

由于这看起来像是家庭作业，我将把细节留给您，但您当前的尝试非常接近于正确的解决方案。

说到这里，您应该知道composition是SML中的一个内置运算符，用小写的o表示，并且(op o)可以在您的第二个定义中用来代替composite。