OCaml - 使用左折叠的累加器
OCaml - Accumulator Using Fold Left
从here学习OCaml。
我想验证一下我是否理解了这段 OCaml 代码的工作原理
List.fold_left (fun acc x -> acc + x) 0 [ 1; 2; 3; 4 ]
我有直觉，这相当于Python中的reduce函数。具体来说，我觉得相当于
reduce(lambda x, y: x + y, [1, 2, 3])
匿名函数采用两个参数 - acc 和 x 以及 returns 单个值 acc + x。我知道最初，第一个参数 acc 将为 0 但它如何知道第二个参数必须是列表的第一个元素？
我认为正在发生的事情是 fold_left 向匿名函数提供了两个参数，然后用新参数递归调用自身，直到列表变空。
为了证实这一点，我看到了 this。
当我定义像 let inc x = x + 1 这样的函数时，我得到像 val inc : int -> int = <fun> 这样的东西，但在这种情况下，签名是 : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a = <fun>
什么是 'a 以及我应该如何解释这个函数签名以便 List.fold_right f [a1; ...; an] b 变成 f a1 (f a2 (... (f an b) ...))？
你问的问题很多。
我很确定 Python reduce 是弃牌，所以您的直觉可能是正确的。
你问 "how does it know that the second argument has to be the first element of the list?" 不幸的是，我不认为这是一个结构良好的问题。没有 "it" 什么都知道。 fold_left 的定义很可能给出了答案。它知道该怎么做，因为有人是这样写代码的:-)
这是标准库中 fold_left 的定义：
let rec fold_left f accu l =
match l with
[] -> accu
| a::l -> fold_left f (f accu a) l
从某种意义上说，这应该可以回答您所有的问题。
fold_left类型中的'a类型是累加器的类型。关键是您可以为累加器使用任何类型。这就是折叠如此强大的原因。只要与折叠函数接受和返回的值匹配，它可以是任何你想要的。
如果我没记错的话，reduce 是 fold 的简化版本，它将列表的第一个元素作为起始元素。我会这样定义它：
let reduce f = function
| x::xs -> fold_left f x xs
| [] -> failwith "can't call reduce on empty lists!"
如果你在OCaml中输入它，它会显示它的类型：
val reduce : ('a -> 'a -> 'a) -> 'a list -> 'a
你可以对比一下fold_left的类型：
('b -> 'a -> 'b) -> 'b -> 'a list -> 'b
这里的类型变量'a和'b表示可以代表任何类型。在您的示例中，'a 和 'b 都变为 int。如果我们插入类型，fold_left 具有签名：
(int -> int -> int) -> int -> int list -> int
这正是我们所期望的：+ 是一个接受两个整数和 returns 一个新整数的函数，0 是一个整数而 [1;2;3;4;] 是一个列表整数。 fold_left 有两个类型变量而 reduce 只有一个的情况已经暗示它更通用。要知道为什么我们可以看看reduce的定义。由于折叠的起始元素是列表的元素，因此类型 'a' 和 'b 必须相同。这对于总结元素很好，但是说，我们想为我们的总结构建一个抽象语法树。我们为此定义一个类型：
type exp = Plus of exp * exp | Number of int
然后我们可以调用：
fold_left (fun x y -> Plus (x, (Number y))) (Number 0) [1; 2; 3; 4]
这导致表达式：
Plus (Plus (Plus (Plus (Number 0, Number 1), Number 2), Number 3), Number 4)
这棵树的一个好处是您可以清楚地看到首先应用的是什么（0 和 1）- 在加法的情况下这不是问题，因为它是关联的（这意味着 a+(b+c) = (a+b)+c) 这不是减法的情况（比较例如 5-(3-2) 和 (5-3)-2).
如果你想用 reduce 做一些类似的事情，你会注意到 OCaml 抱怨类型错误：
reduce (fun x y -> Plus (x, (Number y))) [1; 2; 3; 4];;
错误：此表达式的类型为 exp 但表达式应为 <br> 类型
整数
在这种情况下，我们可以将每个整数作为表达式包装在我们的输入列表中，然后类型一致。因为我们已经有了 Numbers，所以我们不需要将 Number 构造函数添加到 y:
let wrapped = map (fun x -> Number x) [1; 2; 3; 4] in
reduce (fun x y -> Plus (x, y)) wrapped
同样，我们得到了相同的结果，但我们需要对 map 进行额外的函数调用。在fold_left的情况下，这是没有必要的。
P.S.：您可能已经注意到 OCaml 将 fold_left 的类型给出为 ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a。我想您很快就会意识到类型变量的名称不起作用。为了便于比较，我切换了名称，以便函数始终应用于 'a.
的列表
有点晚了，但是如果您合并 reduce 的 initializer 参数，OCaml 的折叠和 Python 的 reduce 之间的比较可能会更容易。
使用折叠对 OCaml 中的整数列表求和：
let sum = List.fold_left (+) 0 [1; 2; 3]
并在 Python 中使用 reduce。
from functools import reduce
sum = reduce(int.__add__, [1, 2, 3], 0)
在这里你可以看到参数的顺序有点不同，但它们都在那里。
Python 认为您不太可能需要初始化程序，因此为了方便起见，将其作为可选参数留在最后。 OCaml 将列表作为最后一个参数也是为了方便，因为部分应用程序使得编写类似 sum 函数的东西变得容易。
let sum = List.fold_left (+) 0
而不是：
let sum lst = List.fold_left (+) 0 lst
从here学习OCaml。
我想验证一下我是否理解了这段 OCaml 代码的工作原理
List.fold_left (fun acc x -> acc + x) 0 [ 1; 2; 3; 4 ]
我有直觉，这相当于Python中的reduce函数。具体来说，我觉得相当于
reduce(lambda x, y: x + y, [1, 2, 3])
匿名函数采用两个参数 - acc 和 x 以及 returns 单个值 acc + x。我知道最初，第一个参数 acc 将为 0 但它如何知道第二个参数必须是列表的第一个元素？
我认为正在发生的事情是 fold_left 向匿名函数提供了两个参数，然后用新参数递归调用自身，直到列表变空。
为了证实这一点，我看到了 this。
当我定义像 let inc x = x + 1 这样的函数时，我得到像 val inc : int -> int = <fun> 这样的东西，但在这种情况下，签名是 : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a = <fun>
什么是 'a 以及我应该如何解释这个函数签名以便 List.fold_right f [a1; ...; an] b 变成 f a1 (f a2 (... (f an b) ...))？
你问的问题很多。
我很确定 Python reduce 是弃牌，所以您的直觉可能是正确的。
你问 "how does it know that the second argument has to be the first element of the list?" 不幸的是，我不认为这是一个结构良好的问题。没有 "it" 什么都知道。 fold_left 的定义很可能给出了答案。它知道该怎么做，因为有人是这样写代码的:-)
这是标准库中 fold_left 的定义：
let rec fold_left f accu l =
match l with
[] -> accu
| a::l -> fold_left f (f accu a) l
从某种意义上说，这应该可以回答您所有的问题。
fold_left类型中的'a类型是累加器的类型。关键是您可以为累加器使用任何类型。这就是折叠如此强大的原因。只要与折叠函数接受和返回的值匹配，它可以是任何你想要的。
如果我没记错的话，reduce 是 fold 的简化版本，它将列表的第一个元素作为起始元素。我会这样定义它：
let reduce f = function
| x::xs -> fold_left f x xs
| [] -> failwith "can't call reduce on empty lists!"
如果你在OCaml中输入它，它会显示它的类型：
val reduce : ('a -> 'a -> 'a) -> 'a list -> 'a
你可以对比一下fold_left的类型：
('b -> 'a -> 'b) -> 'b -> 'a list -> 'b
这里的类型变量'a和'b表示可以代表任何类型。在您的示例中，'a 和 'b 都变为 int。如果我们插入类型，fold_left 具有签名：
(int -> int -> int) -> int -> int list -> int
这正是我们所期望的：+ 是一个接受两个整数和 returns 一个新整数的函数，0 是一个整数而 [1;2;3;4;] 是一个列表整数。 fold_left 有两个类型变量而 reduce 只有一个的情况已经暗示它更通用。要知道为什么我们可以看看reduce的定义。由于折叠的起始元素是列表的元素，因此类型 'a' 和 'b 必须相同。这对于总结元素很好，但是说，我们想为我们的总结构建一个抽象语法树。我们为此定义一个类型：
type exp = Plus of exp * exp | Number of int
然后我们可以调用：
fold_left (fun x y -> Plus (x, (Number y))) (Number 0) [1; 2; 3; 4]
这导致表达式：
Plus (Plus (Plus (Plus (Number 0, Number 1), Number 2), Number 3), Number 4)
这棵树的一个好处是您可以清楚地看到首先应用的是什么（0 和 1）- 在加法的情况下这不是问题，因为它是关联的（这意味着 a+(b+c) = (a+b)+c) 这不是减法的情况（比较例如 5-(3-2) 和 (5-3)-2).
如果你想用 reduce 做一些类似的事情，你会注意到 OCaml 抱怨类型错误：
reduce (fun x y -> Plus (x, (Number y))) [1; 2; 3; 4];;
错误：此表达式的类型为 exp 但表达式应为 <br> 类型
整数
在这种情况下，我们可以将每个整数作为表达式包装在我们的输入列表中，然后类型一致。因为我们已经有了 Numbers，所以我们不需要将 Number 构造函数添加到 y:
let wrapped = map (fun x -> Number x) [1; 2; 3; 4] in
reduce (fun x y -> Plus (x, y)) wrapped
同样，我们得到了相同的结果，但我们需要对 map 进行额外的函数调用。在fold_left的情况下，这是没有必要的。
P.S.：您可能已经注意到 OCaml 将 fold_left 的类型给出为 ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a。我想您很快就会意识到类型变量的名称不起作用。为了便于比较，我切换了名称，以便函数始终应用于 'a.
有点晚了，但是如果您合并 reduce 的 initializer 参数，OCaml 的折叠和 Python 的 reduce 之间的比较可能会更容易。
使用折叠对 OCaml 中的整数列表求和：
let sum = List.fold_left (+) 0 [1; 2; 3]
并在 Python 中使用 reduce。
from functools import reduce
sum = reduce(int.__add__, [1, 2, 3], 0)
在这里你可以看到参数的顺序有点不同，但它们都在那里。
Python 认为您不太可能需要初始化程序，因此为了方便起见，将其作为可选参数留在最后。 OCaml 将列表作为最后一个参数也是为了方便，因为部分应用程序使得编写类似 sum 函数的东西变得容易。
let sum = List.fold_left (+) 0
而不是：
let sum lst = List.fold_left (+) 0 lst