ocaml - 了解 Fold_right 的机制

Question

问题:定义函数mapf，其第一个参数是一元函数，第二个参数是列表。结果是应用于参数列表中每个元素的函数列表。使用fold_right 编写单行函数，而不是递归函数。

解决方案:

let mapf fn list = fold_right (fun h t -> fn h :: t) list []

我不明白这是如何解决问题的，因为 Fold_right 以递归方式使用列表参数计算函数，因此它返回一个值而不是列表。我不明白以下符号的含义:

fun h t -> fn h :: t

Answer 1

您的两个问题是相关的。确实，fold_right 返回一个值，但列表也是一个值!

:: 运算符将新元素添加到列表的开头。因此，fold_right 应用程序计算出的值确实是一个列表。

另一种思考方式可能如下。如果您将 fold_right 与 + 运算符一起使用，您将计算如下值:

fold_right (+) [1; 2; 3] 0 =>
1 + 2 + 3 + 0 =>
6

如果将 fold_right 与 :: 运算符一起使用，则可以计算如下值:

fold_right (::) [1; 2; 3] [] =>
1 :: 2 :: 3 :: [] =>
[1; 2; 3]

这不是理论上的，它在 REPL 中的工作原理与此完全相同:

# List.fold_right (+) [1; 2; 3] 0;;
- : int = 6
# List.fold_right (fun a b -> a :: b) [1; 2; 3] [];;
- : int list = [1; 2; 3]

(您需要编写 fun a b -> a::b 因为 :: 表示法实际上不能用作独立函数。不幸的是。 )

请注意，您自己使用 :: 运算符编写列表是完全合法的:

# 1 :: 2 :: 3 :: [];;
- : int list = [1; 2; 3]

更新

首先，fun x y -> expr 是 OCaml 中“lambda”的表示法，即函数文字。

函数fun h t -> fn h::t采用两个值h和t。它将函数 fn 应用于 h，并返回一个新列表，该新值位于 t 的前面。

从打字的角度来看，值h必须是传递给fn的正确类型，并且fn必须返回一个值正确输入要在列表中的t。

您可以将其括起来，如下所示:fun h t -> (fn h)::t，如果这样更清楚的话。

函数 fun a b -> a::b 类似，只是它只是将 a 直接放入列表 b 中。它不应用任何功能。本质上，它的作用与 :: 运算符的作用相同。

从打字的角度来看，a 必须是正确的类型才能成为列表 b 的元素。

更新2

如果您想了解 lambda 是什么，看待它的一种方式是，它只是编写相当小的函数的一种便捷方法。您可以轻松编写没有 lambda 的给定代码:

let mapf fn list =
    let helper h t = fn h :: t in
    List.fold_right helper list []

此版本有一个名为 helper 的本地声明函数，而不是 lambda。

另一种看待它的方式是，所有函数都是 lambda。编写函数的惯用方式:

let f x y = x + y

只是带有显式 lambda 的版本的方便缩写:

let f = fun x y -> x + y

所以，实际上，lambda 并不是一种特殊的函数。它与任何其他功能完全相同。这只是一个符号选择。