函数式编程中的部分应用和柯里化
Partial applications and currying in functional programming
几个小时过去了，我无法理解 OCaml 中的这个示例。
我不知道该如何思考这个问题，所以我会尝试给出我的思考过程。
问题是：对于每个定义或表达式，给出类型和值（包括）
这是完整的代码（顶层）：
let rec church_of_int n =
if n = 0 then fun f x -> x
else fun f x -> church_of_int (n-1) f (f x);;
let three f x = church_of_int 3 f x;;
three (fun x -> x + 1) 0;;
three three (fun x -> x + 1) 0;;
1) 第一块
let rec church_of_int n =
if n = 0 then fun f x -> x
else fun f x -> church_of_int (n-1) f (f x);;
这是一个接受 int 的函数，因为 int 运算符“-”n-1 和 returns 一个接受两个参数 'a 和 'b 的函数。由于 fun f x -> x.
，该函数返回 returns 相同类型的 'b
因此类型为：
int -> ('a -> 'b) -> 'b = <fun>
但是顶层说：
val church_of_int : int -> ('a -> 'a) -> 'a -> 'a = <fun>
我不明白...
2) 第二块
let three f x = church_of_int 3 f x;;
对于第二个块，三个接受一个函数和一个 int 并将其应用于 church_of_int 的返回函数。
因此，类型是：
('a -> 'b) -> int -> 'b = <fun>
顶层说：
val three : ('a -> 'a) -> 'a -> 'a = <fun>
3) 第三块
three (fun x -> x + 1) 0;;
在这里，我们将一个函数和一个整数应用于三。
我们需要计算
church_of_int 3 (fun x -> x + 1) 0
church_of_int 3 = fun f x -> church_of_int 2 f (f x)
church_of_int 2 = fun f x -> church_of_int 1 f (f x)
church_of_int 1 = fun f x -> church_of_int 0 f (f x)
church_of_int 0 = fun f x -> x
然后
church_of_int 1 = fun f x -> ((fun f x -> x) f (f x)) = fun f x -> f x
church_of_int 2 = fun f x -> ((fun f x -> f x) f f(x)) = fun f x -> f (f x)
church_of_int 3 = fun f x -> ((fun f x -> f (f x)) f f(x)) = fun f x -> f (f (f x))
因此，
church_of_int 3 (fun x -> x + 1) 0 = 3
Toplevel 确认这是正确的。
4）第四块
three three (fun x -> x + 1) 0;;
这里变得异常混乱。一方面，我们知道 three (fun x -> x + 1) 0 = 3
然后
三个3是部分应用
在另一个顶层 returns 27.
你能帮我改正我的错误和我的思维过程以获得正确的类型和结果吗？
第一部分
让我们考虑一下：
let rec church_of_int n =
if n = 0 then fun f x -> x
else fun f x -> church_of_int (n-1) f (f x)
关于这里的类型我们可以推断出什么？
显然，您已经确定 n 必须是 int，因为它被减去并与另一个 int.
进行比较
int -> ... -> ... -> ...
举个例子，如果我们调用 church_of_int 3 那会是什么样子？它 return 是一个接受函数的函数，该函数接受一个函数 f 和一个值 x，我们将其表示为类型 'a。所以 f 接受类型 'a 的值并将其转换为...
嗯，f x 的结果被传递给 church_of_int 期望类型 a 的值，因此 f 的类型必须是 'a -> 'a .
既然我们知道了f和x的推断类型，我们就可以完成church_of_int的类型签名了。
int -> ('a -> 'a) -> 'a -> 'a
第二块
关于：
let three f x = church_of_int 3 f x
这可能只是以下使用部分应用程序。
let three = church_of_int 3
在这种情况下，类型签名 ('a -> 'a) -> 'a -> 'a 不足为奇。
第三块
three (fun x -> x + 1) 0
让我们考虑一下这是如何计算的，(fun x -> x + 1) 代替了加法运算符 ((+) 1) 的部分应用。
church_of_int 3 ((+) 1) 0
3 不等于 0 所以我们返回 fun f x -> church_of_int (n-1) f (f x)，我们将其应用于 (3 - 1)、((+) 1) 和 ((+) 1) 0 .
所以现在我们调用了：
church_of_int 2 ((+) 1) 1
对此进行评估，我们得到：
church_of_int 1 ((+) 1) 2
因为 1 不是 0:
church_of_int 0 ((+) 1) 3
现在，n 是 0，所以我们得到一个函数，其中 f 从未应用于任何东西，所以它没关系。我们只是returnx，也就是3.
第四部分
再次考虑three的定义。
let three = church_of_int 3
类型是：
('a -> 'a) -> 'a -> 'a
three 的第一个参数是一个函数，它将 'a 类型的值映射到另一个相同类型的值。让我们重写一下那个类型签名。
('a -> 'a) -> ('a -> 'a)
如果我们部分应用 three three，我们会得到一个具有以下类型的函数，它看起来很像 three 的类型。
('_a -> '_a) -> '_a -> '_a
将three应用到three的效果是得到另一个函数，它接受一个新函数，它接受一个函数和一个初始值。我们可以无休止地应用它。如果我们这样看，语法可能更有意义：
let f = ((+) 1 in
((three three) f) 0
我们可以通过定义更多的函数来看到这种“求幂”。
─( 10:02:30 )─< command 42 >----
utop #
let two f x = church_of_int 2 f x
let three f x = church_of_int 3 f x
let four f x = church_of_int 4 f x;;
val two : ('a -> 'a) -> 'a -> 'a = <fun>
val three : ('a -> 'a) -> 'a -> 'a = <fun>
val four : ('a -> 'a) -> 'a -> 'a = <fun>
─( 10:02:39 )─< command 43 >----
utop #
let inc x = x + 1;;
val inc : int -> int = <fun>
─( 10:03:05 )─< command 44 >----
utop # two two inc 0;;
- : int = 4
─( 10:03:13 )─< command 45 >----
utop # two four inc 0;;
- : int = 16
─( 10:03:21 )─< command 46 >----
utop # two two two inc 0;;
- : int = 16
─( 10:03:30 )─< command 47 >----
utop # two two four inc 0;;
- : int = 256
This is a function which takes an int because of int operator "-" n-1 and returns a function which takes two arguments 'a and 'b. The function returned returns the same type of 'b because of the fun f x -> x.
Therefore the type is :
int -> ('a -> 'b) -> 'b = <fun>
让我们仔细看看定义，
let rec church_of_int n =
if n = 0 then fun f x -> x
else fun f x -> church_of_int (n-1) f (f x)
从 if 表达式的第一个分支我们确实可以推断出 return 类型是一个接受两个参数并且 return 是最后一个参数的函数，即
int -> ('a -> 'b -> 'b)
我们可以重写（使用 -> 类型运算符的右结合性），
int -> 'a -> 'b -> 'b
请注意，您的思路是如何偏离正确路径的 - 因为您表示一个函数接受两个参数，return将第二个参数设为 ('a -> 'b) -> 'b。您错误地放置了括号，实际上，您的类型表示一个接受单个参数的函数，它本身就是一个接受任何参数的函数，并且 returns 是类型 'b.
的值
但让我们回到我们的定义。我们只使用了 if 表达式一个分支的信息，因此我们错过了一些可用信息。从 else 分支，church_of_int (n-1) f (f x) 我们可以看到第一个参数（我们用 'a 赋予的类型）是一个函数本身，因为应用程序 (f x)，所以我们可以将 'a 细化为函数类型。我们看到它应用于 x，我们知道它具有类型 'b，此外，应用的结果传递给第二个参数，我们从第一个分支推断为 'b ，所以我们知道 f 的类型是 'b -> 'b。现在我们用 ('b -> 'b) 替换 'a 并得到，
int -> ('b -> 'b) -> 'b -> 'b
这相当于模变量名与 OCaml 顶层推断的类型。
那么这个类型是什么意思，或者更具体地说，church_of_int n 表达式定义了什么？此函数将 n 次传递的函数 f 应用于传递的参数 x。参数的类型并不重要，因为我们从不使用它，我们只是将 f 应用到它 n 次。
有了这些知识，我们可以轻松消化 let three f x = church_of_int 3 f x。它应用 f 到 x 三次。所以类型是('a -> 'a) -> 'a -> 'a（我们还是等f和x通过）。
如果我们将 fun x -> x + 1 作为函数传递，将 0 作为初始值传递，那么 three (fun x -> x + 1) 0 是该函数对 0 的三重应用。我们把fun x -> x + 1命名为succ，所以three succ 0就是succ (succ (succ 0)))，即零的第三个后继，也就是三
现在是困难的部分，让我们尝试理解 three three (fun x -> x + 1) 0 表达式。首先，让我们将其重写为 three three succ 0.
您可能会有的第一个问题是为什么three可以接受两个以上的参数？由于 three 的类型为 ('a -> 'a) -> 'a -> 'a，因此第二个参数 'a 本身可能是一个函数。我们知道 succ 的类型是 int -> int，所以我们用 (int -> int)、
代替 'a
((int -> int) -> (int -> int)) -> (int -> int) -> (int -> int)
让我们删除一些括号，
((int -> int) -> int -> int) -> (int -> int) -> int -> int
这给了我们一个接受三个参数的函数，
- 函数
three 类型 ((int -> int) -> int -> int),
- 函数
succ 类型为 (int -> int)
- 类型为
int 的初始参数 0
并且three three succ对succ应用了三次three。那么让我们展开它，
three three succ
===========================
three (three (three succ))
我们已经知道three succ在传递的参数上加了3，所以是x + 3，我们把它命名为plus3，改写一下，
three three succ
===========================
three (three (three succ))
=================== (three succ => plus3)
three (three plus3)
如果我们将 plus3 重复三次，即 x + 3 + 3 + 3 这与 x + 9 相同，那么我们可以将其重写为，
three three succ
===========================
three (three (three succ))
=================== (three succ => plus3)
three (three plus3)
=================== (three plus3 => plus9)
three plus9
现在，最后一步，重复x + 9 + 9 + 9是x+27，所以我们可以做最后的重写，
three three succ
===========================
three (three (three succ))
=================== (three succ => plus3)
three (three plus3)
=================== (three plus3 => plus9)
three plus9
=========== (three plus9 => plus27)
plus27
所以最后 three three succ x 创建了一个在语义上等同于 fun x -> x + 27 的函数，而 three three succ 0 给了我们 27.
几个小时过去了，我无法理解 OCaml 中的这个示例。
我不知道该如何思考这个问题，所以我会尝试给出我的思考过程。
问题是：对于每个定义或表达式，给出类型和值（包括
这是完整的代码（顶层）：
let rec church_of_int n =
if n = 0 then fun f x -> x
else fun f x -> church_of_int (n-1) f (f x);;
let three f x = church_of_int 3 f x;;
three (fun x -> x + 1) 0;;
three three (fun x -> x + 1) 0;;
1) 第一块
let rec church_of_int n =
if n = 0 then fun f x -> x
else fun f x -> church_of_int (n-1) f (f x);;
这是一个接受 int 的函数，因为 int 运算符“-”n-1 和 returns 一个接受两个参数 'a 和 'b 的函数。由于 fun f x -> x.
因此类型为：
int -> ('a -> 'b) -> 'b = <fun>
但是顶层说：
val church_of_int : int -> ('a -> 'a) -> 'a -> 'a = <fun>
我不明白...
2) 第二块
let three f x = church_of_int 3 f x;;
对于第二个块，三个接受一个函数和一个 int 并将其应用于 church_of_int 的返回函数。
因此，类型是：
('a -> 'b) -> int -> 'b = <fun>
顶层说：
val three : ('a -> 'a) -> 'a -> 'a = <fun>
3) 第三块
three (fun x -> x + 1) 0;;
在这里，我们将一个函数和一个整数应用于三。
我们需要计算
church_of_int 3 (fun x -> x + 1) 0
church_of_int 3 = fun f x -> church_of_int 2 f (f x)
church_of_int 2 = fun f x -> church_of_int 1 f (f x)
church_of_int 1 = fun f x -> church_of_int 0 f (f x)
church_of_int 0 = fun f x -> x
然后
church_of_int 1 = fun f x -> ((fun f x -> x) f (f x)) = fun f x -> f x
church_of_int 2 = fun f x -> ((fun f x -> f x) f f(x)) = fun f x -> f (f x)
church_of_int 3 = fun f x -> ((fun f x -> f (f x)) f f(x)) = fun f x -> f (f (f x))
因此，
church_of_int 3 (fun x -> x + 1) 0 = 3
Toplevel 确认这是正确的。
4）第四块
three three (fun x -> x + 1) 0;;
这里变得异常混乱。一方面，我们知道 three (fun x -> x + 1) 0 = 3
然后
三个3是部分应用
在另一个顶层 returns 27.
你能帮我改正我的错误和我的思维过程以获得正确的类型和结果吗？
第一部分
让我们考虑一下：
let rec church_of_int n =
if n = 0 then fun f x -> x
else fun f x -> church_of_int (n-1) f (f x)
关于这里的类型我们可以推断出什么？
显然，您已经确定 n 必须是 int，因为它被减去并与另一个 int.
int -> ... -> ... -> ...
举个例子，如果我们调用 church_of_int 3 那会是什么样子？它 return 是一个接受函数的函数，该函数接受一个函数 f 和一个值 x，我们将其表示为类型 'a。所以 f 接受类型 'a 的值并将其转换为...
嗯，f x 的结果被传递给 church_of_int 期望类型 a 的值，因此 f 的类型必须是 'a -> 'a .
既然我们知道了f和x的推断类型，我们就可以完成church_of_int的类型签名了。
int -> ('a -> 'a) -> 'a -> 'a
第二块
关于：
let three f x = church_of_int 3 f x
这可能只是以下使用部分应用程序。
let three = church_of_int 3
在这种情况下，类型签名 ('a -> 'a) -> 'a -> 'a 不足为奇。
第三块
three (fun x -> x + 1) 0
让我们考虑一下这是如何计算的，(fun x -> x + 1) 代替了加法运算符 ((+) 1) 的部分应用。
church_of_int 3 ((+) 1) 0
3 不等于 0 所以我们返回 fun f x -> church_of_int (n-1) f (f x)，我们将其应用于 (3 - 1)、((+) 1) 和 ((+) 1) 0 .
所以现在我们调用了：
church_of_int 2 ((+) 1) 1
对此进行评估，我们得到：
church_of_int 1 ((+) 1) 2
因为 1 不是 0:
church_of_int 0 ((+) 1) 3
现在，n 是 0，所以我们得到一个函数，其中 f 从未应用于任何东西，所以它没关系。我们只是returnx，也就是3.
第四部分
再次考虑three的定义。
let three = church_of_int 3
类型是：
('a -> 'a) -> 'a -> 'a
three 的第一个参数是一个函数，它将 'a 类型的值映射到另一个相同类型的值。让我们重写一下那个类型签名。
('a -> 'a) -> ('a -> 'a)
如果我们部分应用 three three，我们会得到一个具有以下类型的函数，它看起来很像 three 的类型。
('_a -> '_a) -> '_a -> '_a
将three应用到three的效果是得到另一个函数，它接受一个新函数，它接受一个函数和一个初始值。我们可以无休止地应用它。如果我们这样看，语法可能更有意义：
let f = ((+) 1 in
((three three) f) 0
我们可以通过定义更多的函数来看到这种“求幂”。
─( 10:02:30 )─< command 42 >----
utop #
let two f x = church_of_int 2 f x
let three f x = church_of_int 3 f x
let four f x = church_of_int 4 f x;;
val two : ('a -> 'a) -> 'a -> 'a = <fun>
val three : ('a -> 'a) -> 'a -> 'a = <fun>
val four : ('a -> 'a) -> 'a -> 'a = <fun>
─( 10:02:39 )─< command 43 >----
utop #
let inc x = x + 1;;
val inc : int -> int = <fun>
─( 10:03:05 )─< command 44 >----
utop # two two inc 0;;
- : int = 4
─( 10:03:13 )─< command 45 >----
utop # two four inc 0;;
- : int = 16
─( 10:03:21 )─< command 46 >----
utop # two two two inc 0;;
- : int = 16
─( 10:03:30 )─< command 47 >----
utop # two two four inc 0;;
- : int = 256
This is a function which takes an
intbecause ofintoperator "-"n-1and returns a function which takes two arguments 'a and 'b. The function returned returns the same type of 'b because of thefun f x -> x. Therefore the type is :
int -> ('a -> 'b) -> 'b = <fun>
让我们仔细看看定义，
let rec church_of_int n =
if n = 0 then fun f x -> x
else fun f x -> church_of_int (n-1) f (f x)
从 if 表达式的第一个分支我们确实可以推断出 return 类型是一个接受两个参数并且 return 是最后一个参数的函数，即
int -> ('a -> 'b -> 'b)
我们可以重写（使用 -> 类型运算符的右结合性），
int -> 'a -> 'b -> 'b
请注意，您的思路是如何偏离正确路径的 - 因为您表示一个函数接受两个参数，return将第二个参数设为 ('a -> 'b) -> 'b。您错误地放置了括号，实际上，您的类型表示一个接受单个参数的函数，它本身就是一个接受任何参数的函数，并且 returns 是类型 'b.
但让我们回到我们的定义。我们只使用了 if 表达式一个分支的信息，因此我们错过了一些可用信息。从 else 分支，church_of_int (n-1) f (f x) 我们可以看到第一个参数（我们用 'a 赋予的类型）是一个函数本身，因为应用程序 (f x)，所以我们可以将 'a 细化为函数类型。我们看到它应用于 x，我们知道它具有类型 'b，此外，应用的结果传递给第二个参数，我们从第一个分支推断为 'b ，所以我们知道 f 的类型是 'b -> 'b。现在我们用 ('b -> 'b) 替换 'a 并得到，
int -> ('b -> 'b) -> 'b -> 'b
这相当于模变量名与 OCaml 顶层推断的类型。
那么这个类型是什么意思，或者更具体地说，church_of_int n 表达式定义了什么？此函数将 n 次传递的函数 f 应用于传递的参数 x。参数的类型并不重要，因为我们从不使用它，我们只是将 f 应用到它 n 次。
有了这些知识，我们可以轻松消化 let three f x = church_of_int 3 f x。它应用 f 到 x 三次。所以类型是('a -> 'a) -> 'a -> 'a（我们还是等f和x通过）。
如果我们将 fun x -> x + 1 作为函数传递，将 0 作为初始值传递，那么 three (fun x -> x + 1) 0 是该函数对 0 的三重应用。我们把fun x -> x + 1命名为succ，所以three succ 0就是succ (succ (succ 0)))，即零的第三个后继，也就是三
现在是困难的部分，让我们尝试理解 three three (fun x -> x + 1) 0 表达式。首先，让我们将其重写为 three three succ 0.
您可能会有的第一个问题是为什么three可以接受两个以上的参数？由于 three 的类型为 ('a -> 'a) -> 'a -> 'a，因此第二个参数 'a 本身可能是一个函数。我们知道 succ 的类型是 int -> int，所以我们用 (int -> int)、
'a
((int -> int) -> (int -> int)) -> (int -> int) -> (int -> int)
让我们删除一些括号，
((int -> int) -> int -> int) -> (int -> int) -> int -> int
这给了我们一个接受三个参数的函数，
- 函数
three类型((int -> int) -> int -> int), - 函数
succ类型为(int -> int) - 类型为
int 的初始参数
0
并且three three succ对succ应用了三次three。那么让我们展开它，
three three succ
===========================
three (three (three succ))
我们已经知道three succ在传递的参数上加了3，所以是x + 3，我们把它命名为plus3，改写一下，
three three succ
===========================
three (three (three succ))
=================== (three succ => plus3)
three (three plus3)
如果我们将 plus3 重复三次，即 x + 3 + 3 + 3 这与 x + 9 相同，那么我们可以将其重写为，
three three succ
===========================
three (three (three succ))
=================== (three succ => plus3)
three (three plus3)
=================== (three plus3 => plus9)
three plus9
现在，最后一步，重复x + 9 + 9 + 9是x+27，所以我们可以做最后的重写，
three three succ
===========================
three (three (three succ))
=================== (three succ => plus3)
three (three plus3)
=================== (three plus3 => plus9)
three plus9
=========== (three plus9 => plus27)
plus27
所以最后 three three succ x 创建了一个在语义上等同于 fun x -> x + 27 的函数，而 three three succ 0 给了我们 27.