OCaml递归函数以n次应用函数为例

Question

我希望创建一个OCaml类型为int -> ('a -> 'a) -> 'a -> 'a的函数，该函数接受一个整数n(非负数)，一个返回' a ->' a的函数f和一个类型为'a的参数a。 f应该在a上调用n次。

我尝试了三种不同的方法，但只能获得int -> ('a -> 'b) -> 'a -> 'b，以下是我尝试的一些内容。

let rec f n g a = 
g a;
f (n-1) g a;;

这提供了

val f : int -> ('a -> 'b) -> 'a -> 'c = <fun>

我尝试过

    let rec f n g a =
  if n > 0 then f (n-1) g a
  else g a
  ;;

这给了我

val f : int -> ('a -> 'b) -> 'a -> 'b = <fun>

第二个更接近答案，但我不知道如何将int转换为('a -> 'a) -> 'a -> 'a。

- Bizzle

Answer 1

我不太确定您想要做什么。我猜测下面是您需要的函数：

let rec foldi i f acc =
    if i <= 0 then acc else foldi (pred i) f (f acc)

这个函数递归地将函数 f 应用于初始值 acc 和其结果，共应用 i 次。虽然 foldi 可能不是最好的名称。

- didierc

---

你的代码中的pred i是什么？它似乎会减一？ - Bizzle

pred 是 succ 的对偶，它返回其（整数）参数的前驱，即该值减一。 - didierc

是的，你猜对了。它被定义在“Pervasives”模块中。 - didierc

定义这样微不足道的操作的函数可能看起来很奇怪，但由于它们经常出现，实际上非常方便。 - didierc

哦，我明白了，我对Java有一定的了解，我喜欢我的i++；i--等。 - Bizzle

这些运算符在OCaml中也有类似的操作：incr和decr。 - didierc

Answer 2

let rec f n g a =
if n > 0 then f (n-1) g a
else g a
;;

这几乎就是答案了，但你需要更好地理解自己的问题，也许只是 f^n 的定义。你可以通过以下方式定义 f^n：对于所有 x，f^n(x) = f^(n-1)(f(x))，且 f^0(x) = x。

在您的代码中，您有 f (n-1) g a，这是我的符号表示中的 f^(n-1)(x)。您从未应用过 f，仅在最后应用了一次。

解决方案是：f (n-1) g (g a) !!!

您必须每次都应用 g。

- bruce_ricard

Answer 3

只要你正确编写了函数，类型就会自动解决。你第二次尝试的问题在于它给出了f5 0 ...的错误答案。在我看来，在这种情况下你根本不想应用该函数。

也许下面的例子可以帮助理解：

# let add1 x = x + 1;;
val add1 : int -> int = <fun>
# f5 2 add1 3;;
- : int = 5
# f5 1 add1 3;;
- : int = 4
# f5 0 add1 3;;
- : int = 3
# 

这些答案应该是你所需要的，据我所知与此相关。

- Jeffrey Scofield

---

将">"替换为">="似乎没有帮助。那是大于/等于的正确运算符吗，还是我的错误在其他地方？ - Bizzle

你的错误在其他地方。你需要有一个不对参数进行任何操作的情况。你的代码中没有这样的情况。（如果你想偷看，你可以在didierc的答案中看到解决方案。） - Jeffrey Scofield

再次感谢您的帮助，我承认我偷看了一下。 - Bizzle

Answer 4

我恰巧几分钟前写了一个可工作的版本：

let rec applyn n func arg =
if n <= 0 then
    arg
else
    applyn (n-1) func (func arg)

注意，在递归调用时，函数应用会发生多次。在你的代码中，g只被调用了一次；OCaml无法推断它为'a -> 'a，因此给出了'a -> 'b。

- Libo Wang