Exercises in this lecture   Go to the notes, in which this exercise belongs -- Keyboard shortcut: 'u'   Alphabetic index   Course home   

Exercise solution:
A variant of string-of-char-list?


Here is the variant where the helping function is local - notice the use of letrec (using let will not work):

(define (string-of-char-list? str char-list) (letrec ((string-of-char-list-1? (lambda (str char-list i lgt) (if (= i lgt) #t (and (memv (string-ref str i) char-list) (string-of-char-list-1? str char-list (+ i 1) lgt)))))) (string-of-char-list-1? str char-list 0 (string-length str))))

Here is a variant of string-of-char-list? that does not apply a help function:

(define (string-of-char-list? str char-list) (let ((str-lgt (string-length str))) (if (= str-lgt 0) #t (and (memv (string-ref str 0) char-list) (string-of-char-list? (substring str 1 str-lgt) char-list)))))

It may be rather expensive to call string-length in this function. As a partial remedy, we bind str-lgt to the value of (string-length str) once and for all. It may be even cheaper to measure the length of the orginal string once - at top level - and to reduce this length by one for each recursive call. This, however, requires and extra parameter, and therefore it calls for a help function.

It may be even more expensive to call substring in each incarnation of string-of-char-list? With this we materialize a bunch of (shorter and shorter) suffixes of the original string. This should be avoided, and therefore our first version of the function is far better.