CODEWITHSUNDEEP
variablesrecursionocaml
SoftTimur
SoftTimur

Reputation: 5520

Define a static variable for a recursive function in OCaml

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?

Upvotes: 3

Views: 3540

Answers (3)

gasche
gasche

Reputation: 31459

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.

Upvotes: 3

Francois G
Francois G

Reputation: 11985

With Ocaml's objects, you can do:

class type fact_counter = object ('self)
  method get : int
  method set : int -> unit
  method inc : unit
  method fact : int -> int
end;;

class myCounter init : fact_counter = object (self)
  val mutable count = init
  method get = count
  method set n = count <- n
  method inc = count <- count + 1
  method fact n =
    self#inc;
    if n <= 0 then 1 else n * self#fact (n - 1)
end;;

Then you can obtain:

# let c = new myCounter 0;;
val c : myCounter = <obj>
# c#fact 10;;              
- : int = 3628800
# c#get;;                  
- : int = 11
# c#set 42;;               
- : unit = ()
# c#fact 10;;              
- : int = 3628800
# c#get;;    
- : int = 53

I hope you can easily see how to adapt myCounter to include fib ...

Upvotes: 1

Martin Jambon
Martin Jambon

Reputation: 4939

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 ()

Upvotes: 5

Related Questions