[plt-scheme] critique of some code

From: Prabhakar Ragde (plragde at uwaterloo.ca)
Date: Mon Dec 7 10:01:14 EST 2009

Matthias Felleisen wrote:

> Accumulator-based design doesn't stand by itself. It is always added to structural or generative recursion, meaning you have this grid: 
>              plain | w/ accu 
>  structural        |
>  --------------------------
>  generative        |
> There are examples in the book for all four kinds of things. 
> ;; --- 
> To recognize "structural w/ accumulator", ask yourself whether the conditional dispatch takes the changing argument (here the index into the string) into account. If so, you are looking at a multi-argument structural design. If not, you should look for the second symptom of accumulator design, namely, whether the second argument describes a fixed relationship between those parts of the first changing argument and its original value. A good designer writes down an accumulator statement for this. See my code. 

I do point these things out when I teach.

In this case, however, your invariant is expressed in terms of the 
length of strings/lists bound to identifiers, and not their "contents", 
so you can replace the one use of i (which is in providing the answer, 
not in conditional tests) with that computation, and eliminate the 
parameter i (whether an accumulator or not) entirely.

           ;; [Listof String] -> Nat u false
           ;; does l2 occur in l
           (define (each-position l)
               [(empty? l) -1]
               [else (if (> l l2)
                         (- (string-length str) (length l))
                         (each-position (rest l)))])))


Posted on the users mailing list.