Within the context of using bloom filters for spell checkers in Racket, I have e

Question

Within the context of using bloom filters for spell checkers in Racket, I have everything (including the ctv function) set up except for the hash function. It's supposed to look like this:

key  <-- 5187
for each character c in w
reading from right to left do
key  <-- 29 key + ctv(c)
end for

where ctv ("character-to-value") maps `a' to 1, `b' to 2, ... and `z' to 26.

My current code does this reading from left to right:

(define key
(lambda (w)
     if (null? w)
        5187
       (+ (* 29 (key(cdr w))) (ctv(car w))))
))

I need to know how to do this from right to left.

So for example, if I do (key '(m a y))

i would get "y" then i will compute 5187 * 29 + 25 =150448

then get "a", compute 150448 * 29 + 1 = 4362993

and then get "m", computer 4362993 * 29 + 13 = 126526810?

Explanation / Answer

(define (key word)
(let loop ((chars (string->list word)) ; list of chars
(idx 0) ; current index
(acc 0)) ; accumulated result
(if (null? chars) ; if the list is empty
acc ; return the accumulator
(loop (cdr chars) ; otherwise go to the next char
(add1 idx) ; advance the index
(+ acc (* (expt 7 idx) (ctv (car chars)))))))) ; compute result
Assuming that the ctv procedure is correctly implemented, it should work as expected:

(key "day")
=> 1236

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.