我想撰寫一個[a_n; a_n-1; ...; a_0]帶有累加器的 List 的函式acc。
該函式應該計算整個串列中每個元素的i次冪的總和。該函式fold_left將給出f一個整數。公式是acc sum from i=0 to n of a_i ^ i。我的問題是在fold_left：
let fold_left f acc l =
match l with
| [] -> acc
| x::xs -> fold_left f (f x acc) xs
累加器總是回傳一個整數——所以我沒有參考來知道第i個元素是什么數字。
所以我的問題是我應該如何構建我的f功能。
f 應該是這樣的結構：
f a_0 (f a_1 (...(f a_n acc)...))
我嘗試了一種命令式方法，使用一個ref變數來存盤f迄今為止計算的先前值。但我相信這個問題有更好的解決方案......
uj5u.com熱心網友回復：
累加器不需要是整數，可以是元組，也可以是記錄
type 'a acc = { pos:int; acc:'a }
uj5u.com熱心網友回復：
讓我們首先考慮一個真正必要的解決方案。
一個實用函式，因此我們可以進行整數取冪。我們將用于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
我們需要在整個迭代程序中跟蹤兩條資訊：pos和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)
uj5u.com熱心網友回復：
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 ?
uj5u.com熱心網友回復：
您可以使用一對累加器：
# 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
其中pow x i計算為x的冪i。遺憾的是它不在標準庫中。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/384453.html