Feeds:
Posts

## Loops in Ocaml

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?

### 3 Responses

1. on July 12, 2009 at 03:41 Matías Giovannini

“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:

```begin try while true do
(* calculations *)
if condition then raise Exit
done; assert false
with Exit -> (* result *) end
```

In these cases, a tail-recursive function is more succint.

2. on July 15, 2009 at 07:10 Jared

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.

3. on July 31, 2009 at 11:10 sashang

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
#