Define a static variable for a recursive function in OCaml

Question

I have a recursive function fact, which can be called from either an expression inside it or an expression outside it.

I would like to associate fact with a variable v, such that each time fact is called from outside (another function), v is initialized, and its value can be changed inside fact, but never can be initialized when fact is called from inside.

The following code suits my need, but one problem is that v is defined as a global variable, and I have to do v := init before calling fact from outside, which I do not find beautiful.

let init = 100
let v = ref init

let rec fact (n: int) : int =
  v := !v + 1;
  if n <= 0 then 1 else n * fact (n - 1)

let rec fib (n: int) : int =
  if n <= 0 then 0 
  else if n = 1 then (v := !v + 50; 1)
  else fib (n-1) + fib (n-2)

let main =
  v := init;
  print_int (fact 3);
  print_int !v; (* 104 is expected *)

  v := init;
  print_int (fib 3);
  print_int !v;; (* 200 is expected *)

Could anyone think of a better implementation?

Answer 1

You can hide the function and value definitions within the body of a containing function as follows:

open Printf

let init = 100

let fact n =
  let rec fact counter n =
    incr counter;
    if n <= 0 then 1 else n * fact counter (n - 1)
  in
  let counter = ref init in
  let result = fact counter n in
  (result, !counter)

let main () =
  let x, count = fact 3 in
  printf "%i\n" x;
  printf "counter: %i\n" count (* 104 is expected *)

let () = main ()

Answer 2

You can adapt Martin's solution so that data is shared across various calls:

let fact =
  let counter = ref 0 in
  fun n ->
    let rec fact = ... in     
    fact n

The idea is to transform let fact = fun n -> let counter = ... in ... into let fact = let counter = ... in fun n -> ...: counter is initialized once, instead of at each call of fact.

A classical example of this style is:

let counter =
  let count = ref (-1) in
  fun () ->
    incr count;
    !count

Beware however that you may get into typing trouble if the function was meant to be polymorphic: let foo = fun n -> ... is always generalized into a polymorphic function, let foo = (let x = ref ... in fun n -> ...) is not, as that would be unsound, so foo won't have a polymorphic type.

You can even generalize the counter example above to a counter factory:

let make_counter () =
  let count = ref (-1) in
  fun () ->
    incr count;
    !count

For each call to make_counter (), you get a new counter, that is a function that shares state across call, but whose state is independent from previous make_counter () counter creations.