Arithmetic Recursion

Question

I'm a beginner to scheme and I'm trying to learn some arithmetic recursion. I can't seem to wrap my head around doing this using scheme and producing the correct results. For my example, I'm trying to produce a integer key for a string by doing arithmetic on each character in the string. In this case the string is a list such as: '(h e l l o). The arithmetic I need to perform is to:

For each character in the string do --> (33 * constant + position of letter in alphabet) Where the constant is an input and the string is input as a list.

So far I have this:

(define alphaTest
  (lambda (x)
    (cond ((eq? x 'a) 1)
          ((eq? x 'b) 2))))

(define test 
   (lambda (string constant)
      (if (null? string) 1
      (* (+ (* 33 constant) (alphaTest (car string))) (test (cdr string)))

I am trying to test a simple string (test '( a b ) 2) but I cannot produce the correct result. I realize my recursion must be wrong but I've been toying with it for hours and hitting a wall each time. Can anyone provide any help towards achieving this arithmetic recursion? Please and thank you. Keep in mind I'm an amateur at Scheme language :)

EDIT I would like to constant that's inputted to change through each iteration of the string by making the new constant = (+ (* 33 constant) (alphaTest (car string))). The output that I'm expecting for input string '(a b) and constant 2 should be as follows:

1st Iteration '(a): (+ (* 33 2) (1)) = 67 sum = 67, constant becomes 67
2nd Iteration '(b): (+ (* 33 67) (2)) = 2213 sum = 2213, constant becomes 2213

(test '(a b) 2) => 2280

Answer 1

Is this what you're looking for?

(define position-in-alphabet
  (let ([A (- (char->integer #\A) 1)])
    (λ (ch)
      (- (char->integer (char-upcase ch)) A))))

(define make-key
  (λ (s constant)
    (let loop ([s s] [constant constant] [sum 0])
      (cond
        [(null? s)
          sum]
        [else
          (let ([delta (+ (* 33 constant) (position-in-alphabet (car s)))])
            (loop (cdr s) delta (+ sum delta)))]))))

(make-key (string->list ) 2) => 0
(make-key (string->list ab) 2) => 2280

BTW, is the procedure supposed to work on strings containing characters other than letters—like numerals or spaces? In that case, position-in-alphabet might yield some surprising results. To make a decent key, you might just call char->integer and not bother with position-in-alphabet. char->integer will give you a different number for each character, not just each letter in the alphabet.

Answer 2

(define position-in-alphabet
  (let ([A (- (char->integer #\A) 1)])
    (lambda (ch)
      (- (char->integer (char-upcase ch)) A))))


(define (test chars constant)
  (define (loop chars result)
    (if (null? chars)
        result
        (let ((r (+ (* 33 result) (position-in-alphabet (car chars)))))
          (loop (rest chars) (+ r result)))))
  (loop chars constant))

(test (list #\a #\b) 2)

Answer 3

Here's a solution (in MIT-Gnu Scheme):

(define (alphaTest x)
  (cond ((eq? x 'a) 1)
    ((eq? x 'b) 2)))

(define (test string constant)
  (if (null? string) 
      constant
      (test (cdr string) 
        (+ (* 33 constant) (alphaTest (car string))))))

Sample outputs:

(test '(a) 2)
;Value: 67

(test '(a b) 2)
;Value: 2213

I simply transform the constant in each recursive call and return it as the value when the string runs out.

I got rid of the lambda expressions to make it easier to see what's happening. (Also, in this case the lambda forms are not really needed.)

---

Your test procedure definition appears to be broken:

(define test 
  (lambda (string constant)
    (if (null? string) 
    1
    (* (+ (* 33 constant) 
          (alphaTest (car string))) 
       (test (cdr string)))

Your code reads as:

• Create a procedure test that accepts two arguments; string and constant.

• If string is null, pass value 1, to end the recursion. Otherwise, multiply the following values:

  • some term x that is = (33 * constant) + (alphaTest (car string)), and
  • some term y that is the output of recursively passing (cdr string) to the test procedure

I don't see how term y will evaluate, as 'test' needs two arguments. My interpreter threw an error. Also, the parentheses are unbalanced. And there's something weird about the computation that I can't put my finger on -- try to do a paper evaluation to see what might be getting computed in each recursive call.