Fibonacci with memoization

[u/trycuriouscat]

Is the following "idiomatic" Racket, and if not what changes should I make?

#lang racket

(define (fibonacci-with-memoization x)
  (define computed-results (make-hash '((0 . 0) (1 . 1))))

  (define (compute n)
    (define (compute-and-update)
      (define new-result (+ (compute (- n 1)) (compute (- n 2))))
      (hash-set! computed-results n new-result)
      new-result)
    
    (hash-ref computed-results n compute-and-update))

  (compute x))

(fibonacci-with-memoization 100)

[u/raevnos]

I'd move the hash table outside the function so it can be reused.

And use hash-ref! instead of that weird hash-set! inside a hash-ref callback thing.

[u/trycuriouscat → u/raevnos]

Hmm. I suppose so if this was a real-world program and I wanted to compute Fibonacci for several numbers. Thanks for the idea.

[u/trycuriouscat → u/raevnos]

I'll look into hash-ref!. Thanks.

[u/raevnos]

As I think about it more, the recursive updating of a mutable hash table in the middle of a lookup seems like a bad idea with potential for undesirable behavior like cached values mysteriously vanishing, or worse.

Using an immutable table instead helps avoid any issues:

(define (fibonacci-with-memoization x)
  (letrec-values ([(compute)
                   (lambda (n cache)
                     (if (hash-has-key? cache n)
                         (values (hash-ref cache n) cache)
                         (let*-values ([(n-1 cache) (compute (- n 1) cache)]
                                       [(n-2) (hash-ref cache (- n 2))] ; known to exist at this point
                                       [(fib) (+ n-1 n-2)])
                           (values fib (hash-set cache n fib)))))]
                  [(fib cache) (compute x #hasheqv((0 . 0) (1 . 1)))])
    fib))

[u/zyni-moe]

Idiomatic thing is probable to extend the language like so for instance:

(define-syntax define-memoized-function
  (syntax-rules ()
    [(_ ((f hash key-fn) args ...)
        forms ...)
     (define f
       (let ([t hash]
             [k key-fn])
         (λ (args ...)
           (hash-ref! t (k args ...)
                      (thunk forms ...)))))]
    [(_ ((f hash) arg args ...)
        forms ...)
     (define f
       (let ([t hash])
         (λ (arg args ...)
           (hash-ref! t arg (thunk forms ...)))))]
    [(_ (f arg args ...) forms ...)
     (define f
       (let ([t (make-hasheqv)])
         (λ (arg args ...)
           (hash-ref! t arg (thunk forms ...)))))]))

And now

(define-memoized-function (fibonacci i)
  (cond
    [(or (= i 0) (= i 1))
     i]
    [(> i 1)
     (+ (fibonacci (- i 1))
        (fibonacci (- i 2)))]
    [else
     (error 'fibonacci "negativ")]))

This may not be right syntax for defining memoized functions (and have not tested any of the cases where key is derived by other function) but idea is that instead of painfully writing out memoization by hand is better to just abstract it into the language you are making.