ocaml - 在 OCaml 中总结列表的最惯用（或最快）的方式是什么？

Question

这是我要实施的

功能方式

let sum l = List.fold_left (fun s x -> s+x) 0 l

势在必行的方式

let sum l =
  let sum = ref 0 in
  List.iter (fun x -> sum := !sum +x) l;
  !sum

---

有没有更好/更快的方法来做到这一点？

我问这个是因为《Real World OCaml 》一书说：

# let sum list =
    let sum = ref 0 in
    List.iter list ~f:(fun x -> sum := !sum + x);
    !sum
  ;;
val sum : int list -> int = <fun>

This isn't the most idiomatic (or the fastest) way to sum up a list, but it shows how you can use a ref in place of a mutable variable.

Answer 1

这有点凉;）

let sum l = List.fold_left (+) 0 l;;

要查看性能：

open Printf

let sum1 l = List.fold_left (fun s x -> s+x) 0 l;;
let sum2 l = List.fold_left (+) 0 l;;
let sum3 = List.fold_left (+) 0;;

let rec make_list x acc = function
| 0 -> acc
| n -> make_list x (x :: acc) (n-1)

let l = make_list 1 [] 50000000;;

let _ = match Sys.argv.(1) with
| "1" -> printf "%d\n" (sum1 l)
| "2" -> printf "%d\n" (sum2 l)
| "3" -> printf "%d\n" (sum3 l)
| _ -> printf "Bad arg\n"
;;

给予

$ ocamlc foo.ml
$ time ./a.out 1
50000000

real    0m8.204s
user    0m7.211s
sys 0m0.848s
$ time ./a.out 2
time ./a.out 3
50000000

real    0m8.226s
user    0m7.325s
sys 0m0.818s
$ 50000000

real    0m8.472s
user    0m7.561s
sys 0m0.837s

sum1 和 sum2 具有完全相同的字节码：

    branch L2
    restart
L3: grab 1
    acc 1
    push
    acc 1
    addint
    return 2
L1: acc 0
    push
    const 0
    push
    closure L3, 0
    push
    getglobal List!
    getfield 14
    appterm 3, 4
L2: closure L1, 0
    push
    acc 0
    makeblock 1, 0
    pop 1
    setglobal Foo1!

sum3 的字节码更小，但速度更慢

    branch L2
    restart
L1: grab 1
    acc 1
    push
    acc 1
    addint
    return 2
L2: const 0
    push
    closure L1, 0
    push
    getglobal List!
    getfield 14
    apply 2
    push
    acc 0
    makeblock 1, 0
    pop 1
    setglobal Foo3!

有谁知道为什么？

Answer 2

使用电池：

let sum = BatList.reduce (+)

（实际上，Batteries 已经有 BatList.sum 函数，它完全符合您的要求 - 所以无需编写它：）

Answer 3

作者想到的替代方案可能是手动编写折叠：

let low_level_sum list =
  let rec loop sum = function
    | [] -> sum
    | x::xs -> loop (sum + x) xs in
  loop 0 list

这是丑陋且低级的，List.fold_left (+) 0除非您有具体的性能问题，否则您应该更喜欢。（甚至可能 - OCaml 编译器的递归函数内联正在处理中，可能没有性能优势。）