了解 fold_right 的机制

Question

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

解决方案：

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

我不明白这是如何解决问题的，因为 fold_right 以递归方式计算带有列表参数的函数，所以它 returns 是一个值而不是列表。我不明白以下符号的含义：

fun h t -> fn h :: t

Answer 1

你的两个问题是相关的。确实 fold_right return 是一个值，但是列表是一个值！

:: 运算符将一个新元素添加到列表的开头。所以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，并且 returns 是一个新列表，该新值位于 t 的前面。

从类型的角度来看，值 h 必须是传递给 fn 的正确类型，并且 fn 必须 return 传递给 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 实际上并不是一种特殊的函数。它与任何其他功能完全一样。这只是一个符号选择。

Understanding the mechanics of fold_right