Following on from my look at basic looping syntax in various languages I thought I’d take a look at various methods of looping in Ocaml to make amends for the Ocaml solution.
gcd is the same as in the previous post.
let rec gcd a b = if b = 0 then a else gcd b (a mod b);;
Using one function for one loop is nicer than cramming both into one which felt too much like coding using if and goto.
Most of the solutions use the following recursive function.
let count_for_denom denom = let rec loop num count = if num >= (denom/2+1) then count else loop (num+1) (count + if gcd num denom = 1 then 1 else 0) in loop (denom/3+1) 0;;
The first solution is a pure recursive function. This is really just mental masturbation – needlessly exchanging loops for more verbose recursion.
let solve_it max_denom = let rec loop denom count = if denom > max_denom then count else loop (denom+1) count+count_for_denom denom in loop 5 0;; Printf.printf "%d solutions\n" (solve_it 10000);; $ time ./a.out XXX solutions real 0m1.138s user 0m1.108s sys 0m0.000s
Functional programming includes a bunch of higher level functions such as
fold. In a strict language it would be wasteful to construct a list before iterating over it with one of these higher-order functions.
How about a fold-like function that folds over a range of numbers?
let collector s e acc f = let rec loop s acc = if s > e then acc else loop (s+1) (f acc s) in loop s acc;; Printf.printf "%d solutions\n" (collector 5 1000 0 (fun acc denom -> acc+count_for_denom denom));;
Here is one with a reference and a for next loop. I think this is quite nice – I like that Ocaml is a pragmatic language and includes this kind of stuff.
let count = ref 0 in for i = 5 to 1000 do count := !count + count_for_denom i done; Printf.printf "%d solutions\n" !count;;
And finally the pure nested for loop solution which is about 20% faster than the recursive versions.
let count = ref 0 in for i = 5 to 10000 do for j = (i/3+1) to (i/2) do if gcd i j == 1 then count := !count + 1 done done; Printf.printf "%d solutions\n" !count;; $ time ./a.out XXX solutions real 0m0.934s user 0m0.928s sys 0m0.004s
So, is there anything I missed? What other types of loops are there in Ocaml?