recursion - una - ¿Cómo memorizar funciones recursivas?

sintaxis de recursividad

Question

Considere una función recursiva, digamos el algoritmo Euclid definido por:

let rec gcd a b =
let (q, r) = (a / b, a mod b) in
if r = 0 then b else gcd b r

(Esta es una definición simplificada y muy frágil). ¿Cómo memorizar tal función? El enfoque clásico de definir una memoize : (''a -> ''b) -> (''a -> ''b) función de alto orden memoize : (''a -> ''b) -> (''a -> ''b) agregar memoria a la función es aquí inútil, ya que solo ahorrará tiempo en la primera llamada.

He encontrado detalles sobre cómo memorizar tal función en Lisp o Haskell:

• ¿Cómo puedo memorizar una función recursiva en Lisp?
• Memoración con recursión

Estas sugerencias se basan en la capacidad encontrada en Lisp para sobrescribir la definición de símbolo de una función o en la estrategia de "llamada por necesidad" utilizada por Haskell, y por lo tanto son inútiles en OCaml.

Answer 1

La estrategia ganadora es definir la función recursiva para ser memorada en un estilo de continuación de paso :

let gcd_cont k (a,b) =
let (q, r) = (a / b, a mod b) in
if r = 0 then b else k (b,r)

En lugar de definir recursivamente la función gcd_cont , agregamos un argumento, la "continuación" a ser llamada en lugar de recurrir. Ahora definimos dos funciones de orden superior, call y memo que operan en funciones que tienen un argumento de continuación. La primera función, call se define como:

let call f =
let rec g x =
f g x
in
g

Construye una función g que no hace nada especial, pero llama a f . La segunda función memo construye una función g implementando la memorización:

let memo f =
let table = ref [] in
let compute k x =
let y = f k x in
table := (x,y) :: !table; y
in
let rec g x =
try List.assoc x !table
with Not_found -> compute g x
in
g

Estas funciones tienen las siguientes firmas.

val call : ((''a -> ''b) -> ''a -> ''b) -> ''a -> ''b = <fun>
val memo : ((''a -> ''b) -> ''a -> ''b) -> ''a -> ''b = <fun>

Ahora definimos dos versiones de la función gcd , la primera sin memoria y la segunda con memoria:

let gcd_call a b =
call gcd_cont (a,b)
let gcd_memo a b =
memo gcd_cont (a,b)

Answer 2

# let memoize f =
let table = Hashtbl.Poly.create () in
(fun x ->
match Hashtbl.find table x with
| Some y -> y
| None ->
let y = f x in
Hashtbl.add_exn table ~key:x ~data:y;
y
);;
val memoize : (''a -> ''b) -> ''a -> ''b = <fun>
# let memo_rec f_norec x =
let fref = ref (fun _ -> assert false) in
let f = memoize (fun x -> f_norec !fref x) in
fref := f;
f x
;;
val memo_rec : ((''a -> ''b) -> ''a -> ''b) -> ''a -> ''b = <fun>

Debes leer la sección aquí: https://realworldocaml.org/v1/en/html/imperative-programming-1.html#memoization-and-dynamic-programming en el libro Real World OCaml .

Le ayudará a comprender realmente cómo funciona la memo .