如何使用List.fold_left？

我仍在尝试了解如何fold_left完全有效。它是否像这样迭代列表List.iter？或者我的代码还有其他问题吗？我认为 e 是列表中的元素（所以它是一个元组）并且fst e获取元组的第一个元素并且snd e获取元组中的第二个元素。

let rec pow x n = 
    if n < 0 then
        0
    else if n = 0 then
        1
    else 
        x * pow x (n - 1);;    

let polynomial lst = function
    | x -> List.fold_left (fun e -> (fst e) * (pow x (snd e))) 1 lst;;

lst 是一个元组列表，其中每个元组有两个整数并构成一个多项式函数，因此多项式应该返回一个函数。所以应该发生的事情的一个例子是这样的

# let f = polynomial [3, 3; -2, 1; 5, 0];;
val f : int -> int = <fun>
# f 2;; (* f is the polynomial function f(x) = 3x^3 + (-2)x + 5 *)
- : int = 25

但我收到此错误消息

“错误：此表达式的类型为 int，但表达式的类型应为 'a -> int * int”。

List.fold_left确实迭代一个列表，将值从一个调用传递到另一个调用，这基本上就像一个斗旅 https://en.wikipedia.org/wiki/Bucket_brigade，只有一个桶，在每次迭代中，您都可以查看桶中的内容，取出其中的所有内容并放入新的内容。

更正式地说，fold_left f init elements有类型

val fold_left : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a

它需要三个参数，函数f，初始值init，以及一个列表elements。功能f为每个元素调用x of elements as f acc x, where acc或者是init if x是列表的第一个元素或先前调用返回的结果f。回到我们的类比，它要么是初始的空桶，要么是链中上一个调用传递的桶。

在您的情况下，存储桶的作用是所有项的最终总和。最初，它是空的，然后每个新项计算(fst e) * (pow x (snd e))并将其添加到存储桶中，这样最后您将得到所有项的总和，

let polynomial coeffs x = 
  List.fold_left (fun sum (k,r) -> sum + k * pow x r) 0 coeffs

请注意，不要使用fst and snd为了访问该对的元素，我直接在参数列表中解构了元组。这使得代码更容易理解并且更短。

应用于每个步骤的函数有两个参数，sum是桶（通常称为“累加器”）和列表的元素，它是一对(k,r)在我们的例子中。我们乘以k的值x变量的幂r然后我们将结果添加到累加器中。

For people with an imperative mindset the following pseudocode¹ might be more insightful than the bucket brigade analogy:

def fold_left(user_func, init, elements):
    acc = init
    for elt in elts:
       acc = user_func(acc, elt)
    return acc

¹) Any resemblance to Python is purely coincidental :)