如何使用List.fold_left? [英] How do I use List.fold_left?

问题描述

我仍在尝试了解fold_left的工作原理.是否像List.iter那样遍历列表?还是我的代码还有其他问题?我认为e是列表中的元素(因此它是一个元组)，fst e占据了元组的第一个元素，而snd e占据了元组中的第二个元素.

I'm still trying to understand how fold_left exactly works. Does it iterate through the list like List.iter? Or is there just something else wrong with my code? I'm thinking that e is the element in the list (so it's a tuple) and fst e takes the first element of the tuple and snd e takes the second element in the tuple.

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是一个元组列表，其中每个元组都有两个整数并构成一个多项式函数，因此多项式应该返回一个函数.因此，应该发生的一个例子是

lst is a list of tuples where each tuple has two integers and makes a polynomial function, so polynomial is supposed to return a function. So an example of what should happen is this

# 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类型的表达式".

"Error: This expression has type int but an expression was expected of type 'a -> int * int".

推荐答案

List.fold_left确实在列表上进行了迭代，将值从一个调用传递到另一个，基本上像

List.fold_left indeed iterates over a list, passing the value from one call to another, which basically works like a bucket brigade, with only one bucket, where on each iteration you can look into the bucket, take whatever is there and put something new.

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

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

，它带有三个参数:函数f，初始值init和elements的列表.对于elements的每个元素x以f acc x的形式调用函数f，如果x是列表的第一个元素，则acc是init或上一次调用返回的结果f.回到我们的类比，它要么是初始的空桶，要么是链中上一个调用传递的桶.

and it takes three arguments, the function f, the initial value init, and a list of elements. The function f is called for each element x of elements as f acc x, where acc is either init if x is the first element of the list or a result returned by the previous invocation of f. Back to our analogy, it is either the initial empty bucket or a bucket passed from the previous call in the chain.

在您的情况下，存储桶的作用是所有条件的最终总和.最初，它为空，然后每个新术语计算(fst e) * (pow x (snd e))并将其添加到存储桶中，以便最后您将拥有所有术语的总和

In your case, the role of the bucket is the final sum of all terms. Initially, it is empty, then each new term computes (fst e) * (pow x (snd e)) and adds it to the bucket so that at the end you will have the sum of all terms,

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

请注意，我没有使用fst和snd访问该对中的元素，而是直接在参数列表中对元组进行了解构.这使代码更易于理解和缩短.

Note, that instead of using fst and snd to access the elements of the pair, I deconstructed the tuple directly in the parameter list. This makes code easier to understand and shorter.

应用于每个步骤的函数带有两个参数，sum是存储区(通常称为累加器")和列表的元素，在我们的例子中是一对(k,r).我们将k乘以x变量的值并提高到幂r，然后将结果添加到累加器中.

The function, that is applied on each step takes two arguments, sum is the bucket (it is often called the "accumulator") and the element of the list, which is a pair (k,r) in our case. We multiply k by the value of the x variable raised to the power r and then we add the result to the accumulator.

对于有命令性思维方式的人，以下伪代码 ¹ 可能比水桶大队的类比更具洞察力:

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

---

¹ )与Python的任何相似之处纯属巧合:)

---

¹) Any resemblance to Python is purely coincidental :)

这篇关于如何使用List.fold_left?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！