CODEWITHSUNDEEP
functional-programminglispschemeracketmemoization
user998876
user998876

Reputation: 167

Writing a cached function in Racket

So I'm working on some code (going over a practice exam for a course on Racket), and I have to do the following:

Write a function cached-assoc that takes a list xs and a number n and returns a function that takes one argument v and returns the same thing that (assoc v xs) would return.

You should use an n-element cache of recent results to possibly make this function faster than just calling assoc. The cache should be a vector of length n that is created by the call to cached-assoc and used-and-possibly-mutated each time the function returned by cached-assoc is called.

The cache starts empty (all elements #f). When the function returned by cached-assoc is called, it first checks the cache for the answer. If it is not there, it uses assoc and xs to get the answer and if the result is not #f (i.e., xs has a pair that matches), it adds the pair to the cache before returning (using vector-set!).

The cache slots are used in a round-robin fashion: the first time a pair is added to the cache it is put in position 0, the next pair is put in position 1, etc. up to position n - 1 and then back to position 0 (replacing the pair already there), then position 1, etc.

I have no idea how to do this.

Upvotes: 1

Views: 1592

Answers (2)

dyoo
dyoo

Reputation: 12013

The question requires a few things from you. Here's a partial list:

  1. how to construct a function that has internal, non-global state.
  2. how to define a function that can search for an item in a vector.
  3. how to construct a function that acts as a wrapper for another one.
  4. know what assoc does.
  5. how to mutate a vector.
  6. how to mutate a local variable.

As a quiz question, it is really exercising several concepts at once, and if you don't have these concepts down cold, you are going to have difficulty.

Do do have problems with any of these, or is it something else that's getting you stuck?

Upvotes: 4

C. K. Young
C. K. Young

Reputation: 223003

Here's my implementation. It's just to give you an idea how to approach this problem; I wrote it in a way that probably wouldn't pass for a homework submission (not that I'm presuming that's your intent at all). :-)

(define (cached-assoc xs n)
  (define cache (make-vector n #f))
  (define index 0)
  (define (fetch-cache k i)
    (if (or (negative? i) (< i (- index n))) #f
        (let ((cur (vector-ref cache (modulo i n))))
          (if (equal? (car cur) k) cur
              (fetch-cache k (sub1 i))))))
  (define (update-cache val)
    (vector-set! cache (modulo index n) val)
    (set! index (add1 index))
    val)
  (lambda (k)
    (cond ((fetch-cache k (sub1 index)))
          ((assoc k xs) => update-cache)
          (else #f))))

Upvotes: 2

Related Questions