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

Question

I am trying to define a make-memoize function that has a function f as argument. The idea is that make-memoize would return a procedure f that runs with memoization. I have been able to return a procedure after defining make-memoize with the function f as parameter. However, I haven't been able to actually apply the function to say add, subtract or multiply a number. ie. If I apply make-memoize with add-one function as parameter to number 28, I should get 29 as the result.

Here is what I got so far:

(define (make-memoize f)
  (let ((memoized-values (make-hash)))
    (lambda (n)
      (if (hash-has-key? memoized-values n)
          (hash-ref memoized-values n)
          (f n)))))

When I run make-memoize with the function add-one to 28:

(make-memoize (add-one 28))

This is what I get:

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

It seems to be throwing me the procedure and its directory? Thanks for your help.

Answer 1

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>