ocaml - N次函数组合

Question

我需要编写一个代码，它使用递归函数组成一个函数 f (x)，它本身 N 次。

我写的是：

let f x = x + 1 (*it can be any function*)
let rec compose n f x = if n = 0 then 
   "Can't compose anymore" 
else compose (n-1) f (f x);; 

这显然是不对的。我知道代码还没有写完，但我不知道如何继续。我是否走在正确的道路上？你能告诉我如何解决这个问题吗？

标签： ocaml

Answer 1

你走在正确的道路上。根据要求，我会尝试从这些方程式开始：

compunere 1 f x == f x

上面说应用f一次与x做完全一样(f x)。

compunere 2 f x == f (f x)

同样，应用f两次应该计算f (f x). 如果您(f x)通过调用来替换compunere，您将拥有：

compunere 2 f x == f (f x) = f (compunere 1 f x)

递归的一般模式似乎是：

compunere n f x == f (compunere (n - 1) f x)

请注意，最一般的类型fis a -> b，但是当f再次使用 type 的值调用时b，这意味着aandb应该是相同的类型，因此f实际上是自同态，是 type 的函数a -> a。N >= 1 就是这种情况，但在 N=0 的退化情况下，您可能会有不同的行为。

应用f零时间x可能意味着“返回 x”，这意味着compunere 理论上可以返回一个类型a为零的值，对于任何f函数a -> b，a并且b可能是不同的；您可以使用更多代码来区分这两种情况，但在这里我们可以简单地让类型检查器强制执行a = b在所有情况下都具有统一行为的约束。您还可以通过抛出异常使 0 无效（如负数）（负应用理论上可以是反函数的正应用，但是当您对 f 一无所知时，您无法计算它； f 可能是不可逆的）。

您的代码有点不同：

compunere 3 f x == (compunere 2 f (f x))
                == (compunere 1 f (f (f x)))
                == (compunere 0 f (f (f (f x))))
...

您的方法的优点是递归调用compunere直接给出当前计算的结果：它位于尾部位置，允许编译器执行尾部调用消除。

当您达到 N=0 时，本地绑定的值x会给出您想要的结果。这里，对于 N=0 作为输入，唯一自然的解释也是返回x。