如何构建for for for for ford_left的index访问的累加器 我想编写一个列表[a_n; A_N-1; ...; A_0]带有Ackulator ACC。 该功能应该计算出列出的整个列表中的每个元素的总和...

Question

该函数应该计算出列出的每个列表中的每个元素的总和。功能

acc

将为

fold_left

提供整数。公式为

f

。我的问题是：

acc + sum from i=0 to n of a_i ^ i：

fold_left

累加器总是返回一个整数 - 因此我没有参考可以知道

i

'thelement是什么数字。

我的问题是我应该如何构建我的

let fold_left f acc l = 
 match l with 
 | [] -> acc
 | x::xs -> fold_left f (f x acc) xs 

函数。 f

应该这样结构： f

---

I通过使用一个

f a_0 (f a_1 (...(f a_n acc)...))

变量来存储the以前的值

ref

f

但是我确定有更好的解决方案解决这个问题...

累加器不需要是整数，可以是元组，也可以是记录

type 'a acc = { pos:int; acc:'a }

您可以将一对用于累加器：

Answer 1

# let f (s, i) x =
      (s + pow x i, i + 1);;
val f : int * int -> int -> int * int = <fun>

# let sum_powers_left l = fst (List.fold_left f (0, 0) l);;
val sum_powers_left : int list -> int = <fun>


# let g x (s, i) =
      (s + pow x i, i + 1);;
val g : int -> int * int -> int * int = <fun>

# let sum_powers_right l = fst (List.fold_right g l (0, 0));;
val sum_powers_right : int list -> int = <fun>


# sum_powers_left [2000; 100; 20; 3];;   (* 1 + 100 + 20*20 + 3*3*3 *)
- : int = 528

# sum_powers_right [2000; 100; 20; 3];;  (* 2000*2000*2000 + 100*100 + 20 + 1 *)
- : int = 8000010021

where

pow x i

评估

Answer 2

对

i

的力量。 aaddly它不在标准库中。

List.fold_left

可以接受任何类型的累加器

(* given some pow function *)
let rec pow a b =
  match b with
  | 0 -> 1
  | _ -> a * pow a (b - 1)

(* your initial accumulator *)
let init = (0, 0) in 

(* your folding function *)
let f (i, r) v = 
  (i + 1, r + pow v i) in

(* note the output is a tuple of the last i and the sum *) 
let (i, result) = List.fold_left f init [10;20;30;40] in

(* print the result *)
Format.printf "result: %d\n" result

result: 64921

检查您的工作-

10^0 + 20^1 + 30^2 + 40^3 = 64921 ✅

Answer 3

LLET首先考虑了对您的问题的真正急切解决方案。

实用程序功能，因此我们可以进行整数启用。我们将使用

List.iter

在

int list

中运行命令式循环。

let rec pow x =
  function
  | 0 -> 1
  | 1 -> x
  | n -> x * pow x (n - 1)

let lst = [1; 4; 7; 2]

let pos = ref 0
let sum = ref 0

let () = 
  List.iter 
    (fun x -> sum := !sum + pow x !pos; 
              pos := !pos + 1) 
    lst

Printf.printf "The sum is %d\n" !sum

我们需要两个信息来跟踪整个迭代：

Answer 4

和

sum

。以这种命令式的风格，我们通过突变价值来跟踪它们。

当我们使用

List.fold_left

并使用累加器来包含同一状态时，我们不再需要突变任何值。

let (pos, sum) = 
  List.fold_left 
    (fun (p, s) x -> (p + 1, s + pow x p)) 
    (0, 0) 
    lst

您可以看到最初提供的原始状态如何镜像我在命令式示例中提供的零。

如果我们查看它在列表上的工作方式的进展方式，那么可以更好地了解累加器元组的工作原理。

List.fold_left f (0, 0) [1; 4; 7; 2]
List.fold_left f (1,  0 + pow 1 0) [4; 7; 2]
List.fold_left f (2,  1 + pow 4 1) [7; 2]
List.fold_left f (3,  5 + pow 7 2) [2]
List.fold_left f (4, 54 + pow 2 3) []
(4, 62)

偏离...

我们可以简单地使用

List.mapi

将每个元素作为指数提高到其索引，然后使用

List.fold_left

来汇总

those

值。

# [1; 4; 7; 2]
  |> List.mapi @@ Fun.flip pow
  |> List.fold_left (+) 0;;
- : int = 62

对于一个大列表，您可能希望采用序列来避免生成另一个列表。

# [1; 4; 7; 2]
  |> List.to_seq
  |> Seq.mapi @@ Fun.flip pow
  |> Seq.fold_left (+) 0;;
- : int = 62