在函数式编程中 "function times zero" 时函数 return 是什么意思？

Question

我被这个 SML 任务困住了。我正在尝试创建一个复合函数（fun compound n f）。它应该对自身应用函数 f n 次，例如，化合物 3 f 将等于 f(f(f(x)))。我让它工作，除了 n 为零的情况。我问过教授，但他不会直接告诉我答案。他试图给我一个提示 "what's function times zero?" 我仍然无法弄清楚。 Whosebug 能算出来吗？

谢谢。

我的代码：

fun compound n f =
    if n < 2 then
        if n = 0 then fn x => f x else fn x => f x
    else fn x => f(compound (n-1) f(x));

示例：

val fnc = fn x => x + 1; (* example function to be used *)
compound 5 fnc(10); (* will return 15 which is correct*)
compound 0 fnc(10); (* returns 11, should be 10 *)

答案：

fun compound n f =
    if n < 2 then
        if n = 0 then fn x => x else fn x => f x
    else fn x => f(compound (n-1) f(x));

Answer 1

这个算法的基本情况是什么？即递归终止于 n 的什么值？当它终止时，你 return 做什么？想想如果 f 没有应用到 x，你会想要 return。在您的示例的上下文中，如果 fnc 应用于 10 零次，应该 returned 什么？

fun compound n f =
  (* If n equals the termination value, then return the base case*)
  if n = ?
  else fn x => f(compound (n-1) f(x));

这里有一个模式存在于递归算法的基本情况中。例如，没有元素的列表的总和是多少？或者，没有元素的列表的长度是多少？

Answer 2

我不会给你最后的答案，因为我不想让老师不高兴 ;) 但是，我会尝试一个我相信你会发现很容易完成的推导。

让我们从一个非常简单的案例开始。让我们 "reimplement" 函数应用程序，即让我们编写一个函数，它接受一个函数和一个参数，并将第一个参数应用于第二个参数：

fun apply f a = f a

让我们使用一个人为设计的函数，增加整数，进行测试：

- fun inc n = n + 1;
val inc = fn : int -> int

- inc 1;
val it = 2 : int

- apply inc 1;
val it = 2 : int

现在，让我们编写 apply2，一个接受函数和参数并将参数函数两次应用于参数的函数：

fun apply2 f a = f (f a)

让我们用inc测试一下：

- apply2 inc 1;
val it = 3 : int

似乎有效。如您所料，我们现在将实现 apply3、apply4 等。让我们马上看看其中的一些：

fun apply f a = f a
fun apply2 f a = f (f a)
fun apply3 f a = f (f (f a))
fun apply4 f a = f (f (f (f a)))

看来我们可以根据前面的重写后面的：

fun apply2 f a = f (apply f a)
fun apply3 f a = f (apply2 f a)
fun apply4 f a = f (apply3 f a)

我们甚至可以重写apply:

fun apply f a = f (apply0 f a)

记住之前apply的定义，它们是等价的：

fun apply f a = f a

那么，apply0 应该是什么？

fun apply0 f a = ...

在函数式编程中 "function times zero" 时函数 return 是什么意思？

What does function return when "function times zero" in functional programming?

sml