function - OCaml 递归函数应用函数 n 次

Question

我想在 OCaml 中创建一个 int -> ('a -> 'a) -> 'a -> 'a 类型的函数，它需要一个 int n （非否定）和一个函数 f 'a -> 'a 和'a 类型的参数 a。f 应该被调用一次。

我尝试了 3 种不同的方法，但只能得到 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

score 6 · Accepted Answer

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

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

它递归地将i函数应用f到一个值acc，然后应用到它的结果。foldi虽然可能不是最好的名字。

score 2 · Accepted Answer

一旦你正确编写了函数，类型就会变直。您第二次尝试的问题是它给出了错误的答案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
#

这些是你应该得到的答案，在我看来。

score 2 · Accepted Answer

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) ga，即 f^(n-1)(x) 与我的符号。你永远不会申请 f，只是在最后。

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

你必须每次都申请 g 。

score 1 · Accepted Answer

几分钟前我碰巧写了一个工作版本：

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

请注意，每次进行递归调用时都会发生函数应用程序。在您的代码中， g 仅被调用一次；OCaml 不能推断它是 'a -> 'a，所以给出 'a -> 'b。

4 回答 4