How to make a function a memoized version of it in racket

I see several issues:

• You don't update the hash table with the computed value
• make-memoize is a function which create a new function from a function

So the proper use is something like this:

(define (add-one n)
  (+ n 1))

(let ((fast-add-one (make-memoize add-one)))
  (fast-add-one 1)
  (fast-add-one 1)
  (fast-add-one 1))

The full code is available below, could be executed from Racket IDE:

(define (add-one n)
  (+ n 1))

(define (make-memoize f)
  (let ((memoized-values (make-hash)))
    (lambda (n)
      (if (hash-has-key? memoized-values n)
          ;; Get and return the value from hash-table
          (let ((previous-value (hash-ref memoized-values n)))
            (printf "READ VALUE ~A->~A~%" n previous-value)
            previous-value)
          ;; Update the value in the hash table
          (let ((new-value  (f n)))
            (printf "SET  VALUE ~A->~A~%" n new-value)
            (hash-set! memoized-values n new-value)
            new-value)))))

(let ((fast-add-one (make-memoize add-one)))
  (fast-add-one 1)
  (fast-add-one 1)
  (fast-add-one 1))

The result of the evaluation should be the following:

SET  VALUE 1->2 ;; Here, this is the first computation of add-one
READ VALUE 1->2 ;; Here, we just read from hash table
READ VALUE 1->2 ;; Here, we just read from hash table

EDIT: the answer to your error question

> (make-memoize (slow-add-one 28))
#<procedure:...s/rack-folder/test-file.rkt:26:4>

This is not an error, the Racket interpreter just return a procedure (a function) which is defined in the given filename/line.

In the code I provided, the function call (make-memoize add-one)) also returns a procedure.

> (make-memoize add-one))
#<procedure>

One of the most common uses of memoization is to reduce computation in recursive procedure calls. Even when fixed up the posted code alone will not allow this. Further, binding a procedure created with make-memoize to a new identifier will have no effect since the un-memoized procedure is still used in all of the recursive calls.

As for the original posted code, given some key, the goal is to update the hash table with a new key unless that key is already found in the table (indicating that the calculation has already been made and stored. If the key is not found, then a value should be calculated for the key, and the results stored in the table. In either case, the value associated with the key should be returned.

This is a very literal transcription of what was just described:

(define (memo f)
  (let ((lookup (make-hash)))
    (lambda (x)
      (unless (hash-has-key? lookup x)
        (hash-set! lookup x (f x)))
      (hash-ref lookup x))))

Here, memo returns a procedure that, when called with x, checks lookup for the key x. If x is not found, it is added to lookup and associated with the value of (f x). Finally, the value associated with x is returned.

let-Binding Only Works for Limited Cases

When the memo-ized procedure is recursive, the desired effect is not obtained. Each recursive call uses f, not the memo-ized version of f, so there are no further lookups beyond the initial call. For example, given:

(define (fibonacci n)
  (cond ((= n 0) 0)
        ((= n 1) 1)
        (else (+ (fibonacci (- n 2))
                 (fibonacci (- n 1))))))

This will not work as desired:

(let ((fast-fib (memo fibonacci)))
  (fast-fib 40))

Here fast-fib is bound to the memo-ized procedure, but fibonacci is invoked for the recursive calls, since that is how fibonacci is defined. This will not work either:

(let ((fibonacci (memo fibonacci)))
  (fibonacci 40))

Here fibonacci is rebound to the memo-ized procedure, but fibonacci called the original version of fibonacci at the time of definition, and continues to do so.

You need to find a way to change the definition of fibonacci so that it is itself the memo-ized procedure. You can do this by using set!. You could just evaluate (set! fibonacci (memo fibonacci)) before using fibonacci. It would be nicer to have a macro which does this for you:

(define-syntax-rule (memoize! f)
  (set! f (memo f)))

This is a very simple macro that simply redefines the given procedure so that it is memo-ized. Here are some examples comparing the failed approaches with the successful approach:

memoize.rkt> (time (fibonacci 40))
cpu time: 2780 real time: 2780 gc time: 0
102334155

memoize.rkt> (time (let ((fast-fib (memo fibonacci))) (fast-fib 40)))
cpu time: 2800 real time: 2800 gc time: 1
102334155

memoize.rkt> (time (let ((fibonacci (memo fibonacci))) (fibonacci 40)))
cpu time: 2789 real time: 2789 gc time: 0
102334155

memoize.rkt> (memoize! fibonacci)

memoize.rkt> (time (fibonacci 40))
cpu time: 0 real time: 0 gc time: 0
102334155

From the above you can see that the failed approaches have not improved the run time of the fibonacci procedure at all; in fact it appears that these incorrectly memoized versions are a little bit slower than the naked calls to fibonacci. This is because of the extra overhead incurred by calling memo on fibonacci, which creates a pointlessly memoized version that is called only on the initial call (all subsequent calls are really calling the naked fibonacci procedure). But the successfully memoized version calls itself on recursive calls, and it shows quite a lot of improvement.

To underscore the value of memoization, and the penalty for getting it wrong, consider (fibonacci 45). This seems like a small increase over the previous (fibonacci 40):

memoize.rkt> (time (let ((fast-fib (memo fibonacci))) (fast-fib 45)))
cpu time: 31042 real time: 31042 gc time: 11
1134903170

memoize.rkt> (memoize! fibonacci)

memoize.rkt> (time (fibonacci 45))
cpu time: 0 real time: 0 gc time: 0
1134903170

And since the properly memoized version caches results between calls, I restarted the REPL for this next test:

memoize.rkt> (memoize! fibonacci)

memoize.rkt> (time (fibonacci 1000))
cpu time: 1 real time: 1 gc time: 0
43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875

The fast-fib version took almost 3 seconds to calculate (fast-fib 40), and 31 seconds to calculate (fast-fib 45). That is an order-of-magnitude slowdown for merely increasing the input value by 5. However, the properly memoized version of fibonacci took less than 1 microsecond to calculate (fibonacci 40), less than 1 microsecond again to calculate (fibonacci 45), and about 1 microsecond to calculate (fibonacci 1000) (starting from an empty lookup table in all three cases; performance is even better when calling fibonacci multiple times without clearing the cache). You would be waiting a very, very long time for (fast-fib 1000) to complete.

There are a lot of ways that this could be improved; you might want to be able to memoize procedures of more than one argument, or you might want to be able to clear the lookup table for a memoized procedure, or you might want to be able to un-memoize a procedure, etc. There is quite a lot of literature about memoization stretching back at least to the 1960s for anyone who wants to delve deeper. This particular topic of creating a memoized procedure from another procedure is called automatic memoization. Here is a paper by Peter Norvig that includes a nice discussion of the technique; note that this paper uses Common Lisp as the implementation language.