What is the most idiomatic (or the fastest) way to sum up a list in OCaml?

Question

Here is what I would implement

functional way

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

imperative way

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

---

Is there even a better/faster way to do it?

I asked this because the book Real World OCaml says:

# 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

This is slightly cooler ;)

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

To see performance:

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"
;;

Giving

$ 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 and sum2 have exactly the same bytecode:

    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 has smaller bytecode but is slower

    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!

Anyone know why?

Answer 2

Using Batteries:

let sum = BatList.reduce (+)

(actually, Batteries already have BatList.sum function which does exactly what you want - so no need to write it :)

Answer 3

The alternative the author had in mind may have been to manually write the fold:

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

This is ugly and low level, and you should prefer List.fold_left (+) 0 unless you have a concrete performance concern. (And possibly even then - the OCaml compiler's inlining of recursive functions is being worked on and there may not be a performance advantage.)