Определить статическую переменную для рекурсивной функции в 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

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

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 не будет иметь полиморфного типа.

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

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

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

Answer 2

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

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 3

с объектами OCaml, вы можете сделать:

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, чтобы включить...