Int64 usage in recursive functions

Question

I have the following code written in Ocaml to try and generate the first 50 catalan numbers:

let rec f n:int64=
 if n<1 then 1L
 else (4*n-2)*f((n-1L))/(n+1L)
;;
for i = 0 to 50 do
  Printf.printf "%d\n"(f i)
done;

But the problem is that the recursion function doesn't seem to accept Int64 values and seems to want Int instead despite me notating n as int64:

File "/proc/self/fd/0", line 3, characters 19-21:
3 |  else (4*n-2)*f((n-1L))/(n+1L)
                       ^^
Error: This expression has type int64 but an expression was expected of type
         int
exit status 2

Is there a way to ensure I can int64 numbers here with recursion?

Answer 1

Your problem isn't recursion per se, it's that the operators in OCaml are strongly typed. So the - operator is of type int -> int -> int.

Without getting into lots of fussing with the syntax, the easiest fix is probably to use the named functions of the Int64 module. You can use Int64.sub rather than -, for example.

You can use the notation Int64.(... <expr> ...) to avoid repeating the module name. If you rewrite your code this way, you get something like this:

let rec f (n : int64) : int64 =
    Int64.(
        if n < 1L then 1L
        else
            mul (sub (mul 4L n) 2L)
                (f (div (sub n 1L) (add n 1L)))
    )

Looking at the results computed by this function, they don't look like Catalan numbers to me. In fact the 50th Catalan number is too large to be represented as an int64 value. So there is still some work to do. But this is how to get past the problem you're seeing (IMHO).

If you really want to work with such large numbers, you probably want to look at the Zarith module.

Answer 2

Submitted as an additional suggestion to Jeffrey's answer: whether using Int64 or Zarith, you might create a module defining arithmetic operators and then locally open that to clean up your code.

E.g.

module Int64Ops =
struct
  let ( + ) = Int64.add
  let ( - ) = Int64.sub
  let ( * ) = Int64.mul
  let ( / ) = Int64.div
end

let rec f n =
  Int64Ops.(
    if n < 1L then 1L
    else (4L * n - 2L) * f (n - 1L) / (n + 1L)
  )

Or you could use a functor to make it easier to work with multiple different types of numbers.

module type S =
sig
  type t
  val add : t -> t -> t
  val sub : t -> t -> t
  val mul : t -> t -> t
  val div : t -> t -> t
end

module BasicArithmeticOps (X : S) = 
struct
  type t = X.t
  let ( + ) = X.add
  let ( - ) = X.sub
  let ( * ) = X.mul
  let ( / ) = X.div
end

# let module A = BasicArithmeticOps (Float) in
A.(8. + 5.1);;
- : float = 13.1
# let module A = BasicArithmeticOps (Int) in
A.(8 + 3);;
- : int = 11
# let module A = BasicArithmeticOps (Int64) in
A.(4L + 3L);;
- : int64 = 7L