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 .