OCaml - 使用向左折叠的累加器

Question

从这里学习OCaml .

我想验证我是否已经理解了这段OCaml代码是如何工作的

List.fold_left (fun acc x -> acc + x) 0 [ 1; 2; 3; 4 ]

我有一种直觉,认为这相当于reducePython中的函数.具体来说,我认为它相当于

reduce(lambda x, y: x + y, [1, 2, 3])

匿名函数接受两个参数- acc和x并返回一个值acc + x.我理解,最初,第一个参数acc将为0,但它如何知道第二个参数必须是列表的第一个元素？

我认为正在发生的是fold_left为匿名函数提供两个参数,然后使用新参数递归调用自身,直到列表变空.

为了证实这一点,我看到了.

当我定义一个像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) ...))？

Answer 1

你问了很多问题.

我很确定Python reduce是一个折叠,所以你的直觉可能是正确的.

你问"怎么知道第二个参数必须是列表的第一个元素？" 不幸的是,我认为这不是一个很好的问题.没有"它"知道任何事情.很可能答案是由定义给出的fold_left.它知道该怎么做因为有人写了这样的代码:-)

以下是fold_left标准库的定义:

let rec fold_left f accu l =
  match l with
    [] -> accu
  | a::l -> fold_left f (f accu a) l

从某种意义上说,这应该回答你所有的问题.

类型'a中的类型fold_left是累加器的类型.关键是你可以使用你想要的任何类型的累加器.这就是折叠如此强大的原因.只要它与折叠函数接受并返回的值匹配,它就可以是您想要的任何值.