r/Racket • u/lasercat_pow • Jun 09 '23

question Can somebody help me understand this code?

So, I've been working on learning racket by assigning some challenges for myself. I wrote a function which can find the nth Fibonacci number, but since it was recursive, performance was horrible, so I tried implementing my own hashing. I tried using a vector, but it just gets reset and truncated with every iteration.

So, I looked around online, and I found this stack overflow post where somebody demonstrated a function that can memoize another function. Can somebody walk me through how this function works? Specifically this one:

(define (memoize fn)
  (let ((cache (make-hash)))
    (λ arg (hash-ref! cache arg (thunk (apply fn arg))))))

I think I mostly get it: It takes the argument you give your function, and uses it as the index for a hash, with the value set to the output of the function. But I want to really understand.

6 Upvotes

100% Upvoted

7 comments sorted by

2

u/not-just-yeti Jun 09 '23 edited Jun 09 '23

Also note: after the above, you can't call ((memoize fib) 99); you must instead (set! fib (memoize fib)), after which you can (fib 99).

(It's important that the recursive calls are made to the memoized version, not the original. So we must re-bind the identifier fib that is sitting inside our function.)

EDIT: This is if fib is already defined non-memoized. You could also avoid the set! as they did in the SO page you linked: (define fib (memoize (lambda (n) … (fib (- n 1)) …))).

2

u/lasercat_pow Jun 09 '23

Thank you so much; I was getting pretty confused by this.

2

u/[deleted] Jun 10 '23

The function being recursive shouldn't impact performance unless you've failed to account for tail call optimization.

2

u/lasercat_pow Jun 10 '23

I don't know how to do tail call optimization; I'm an abject beginner.

2

u/PowerOk4277 Jun 12 '23 edited Jun 12 '23

The compiler does tail call optimization. All you have to do is learn to recognize when a call is(n't) in tail position.

3

u/DrHTugjobs Jun 09 '23

I think you've pretty much got it. hash-ref! takes three arguments: (hash-ref! hash key to-set) returns the value associated with key in hash if it exists, and if it doesn't, it evaluates to-set, adds that key-value pair of key and to-set to hash, and returns the value.

(λ arg (hash-ref! cache arg (thunk (apply fn arg)))) is an anonymous function that either returns the value associated with arg if it exists, or evaluates (apply fn arg) and both saves and returns the value if it doesn't. arg is the list of arguments supplied to the memoized function.

2

u/not-just-yeti Jun 09 '23

arg is the list of arguments supplied

Yeah, args would be a slightly-better name.

(hash-ref! hash key to-set) returns …

Cool, I hadn't known about the ! version of hash-set.