How to memoize recursive functions?

Question

Consider a recursive function, say the Euclid algorithm defined by:

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

(This is a simplified, very brittle definition.) How to memoize such a function? The classical approach of defining a high-order function memoize : ('a -> 'b) -> ('a -> 'b) adding memoization to the function is here useless, because it will only save time on the first call.

I have found details on how to memoize such function in Lisp or Haskell:

These suggestions rely on the ability found in Lisp to overwrite the symbol definition of a function or on the “call-by-need” strategy used by Haskell, and are therefore useless in OCaml.

Michaël Le Barbier · Accepted Answer · 2014-09-06 22:35:02Z

The winning strategy is to define the recursive function to be memoized in a continuation passing style:

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

Instead of defining recursively the gcd_cont function, we add an argument, the “continuation” to be called in lieu of recursing. Now we define two higher-order functions, call and memo which operate on functions having a continuation argument. The first function, call is defined as:

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

It builds a function g which does nothing special but calls f. The second function memo builds a function g implementing memoization:

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

These functions have the following signatures.

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

Now we define two versions of the gcd function, the first one without memoization and the second one with memoization:

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

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

Jackson Tale · Accepted Answer · 2014-09-07 12:05:23Z

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>

You should read the section here: https://realworldocaml.org/v1/en/html/imperative-programming-1.html#memoization-and-dynamic-programming in the book Real World OCaml.

It will help you truly understand how memo is working.

answered Sep 7, 2014 at 12:05

Jackson Tale

25.9k38 gold badges159 silver badges275 bronze badges

3 Comments

Adèle Blanc-Sec Over a year ago

How does this answer improves Michael Grünewald's answer?

Jackson Tale Over a year ago

@AdèleBlanc-Sec Pointed out a formal explanation from the book real world ocaml. It really explains in details how memo works. Honestly, continuation passing style in Michael's answer is a bit complicated or misleading if one doesn't really understand what is continuation passing

Alex Veleshko Nov 20 at 14:47

You still need gcd_cont in your answer. This is what goes as the f_norec argument in the memo_rec function you so diligently copied.

Collectives™ on Stack Overflow

How to memoize recursive functions?

2 Answers 2

Comments

3 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

3 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related