Определите статическую переменную для рекурсивной функции в OCaml

Question

У меня есть рекурсивная функция fact, которую можно вызывать либо из выражения внутри нее, либо из выражения вне ее.

Я хотел бы связать fact с переменной v, так что каждый раз, когда fact вызывается из извне (другая функция), v инициализируется, и его значение может может быть изменено внутри fact, но никогда не может быть инициализировано, когда fact вызывается из внутри .

Следующий код удовлетворяет моим потребностям, но одна проблема заключается в том, что v определен как глобальная переменная, и мне нужно сделать v := init перед вызовом fact извне, что я не нахожу красивым.

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

Кто-нибудь может подумать о лучшей реализации?

Answer 1

Вы можете скрыть определения функций и значений в теле содержащей функции следующим образом:

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

Вы можете адаптировать решение Мартина так, чтобы данные распределялись между различными вызовами:

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

Идея состоит в том, чтобы преобразовать let fact = fun n -> let counter = ... in ... в let fact = let counter = ... in fun n -> ...: счетчик инициализируется один раз, а не при каждом вызовеfact.

Классическим примером этого стиля является:

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

Однако учтите, что вы можете столкнуться с проблемами при наборе текста, если функция должна была быть полиморфной: let foo = fun n -> ... всегдаОбобщенный в полиморфную функцию, let foo = (let x = ref ... in fun n -> ...) не является, так как это было бы неправильно, поэтому foo не будет иметь полиморфного типа.

Вы можете даже обобщить приведенный выше пример счетчика на counterfactory :

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

Для каждого вызова make_counter () вы получаете новый счетчик, который является функцией, которая разделяет состояние по вызову, но состояние которой не зависит от предыдущих make_counter () созданий счетчика.

Answer 3

С объектами Окамля вы можете сделать:

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;;

Тогда вы можете получить:

# 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

Надеюсь, вы легко поймете, как адаптировать myCounter для включения fib ...