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 map
and 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?
“What other types of loops are there in Ocaml?”
You can also use
while
loops, with syntax
while condition do statements done
. The problem with imperative loops is that there is no way to break out early of them, leading to unsightly idioms like:In these cases, a tail-recursive function is more succint.
Ah, the while loop. I knew I had missed one! I think my brain probably glossed over it when the tutorial I was reading said it was not very useful.
Thanks.
The while, for, etc loop expressions in ocaml always have a unit return type. That’s the fundamental difference between them and a tail-recursive loop construct.
# let rec loop idx = if idx == 5 then idx else loop (idx + 1);;
val loop : int -> int =
# x;;
– : unit = ()
# let x () = for i = 0 to 5 do i done;;
Warning S: this expression should have type unit.
val x : unit -> unit =
# x ();;
– : unit = ()
# loop 0;;
– : int = 5
#