[plt-scheme] critique of some code

From: Matthias Felleisen (matthias at ccs.neu.edu)
Date: Mon Dec 7 10:37:11 EST 2009

On Dec 7, 2009, at 10:01 AM, Prabhakar Ragde wrote:

> 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)
>            (cond
>              [(empty? l) -1]
>              [else (if (> l l2)
>                        (- (string-length str) (length l))
>                        (each-position (rest l)))])))

Yes, and this particular design is plain structural recursion while  
mine was "structural with". (There's almost always more  than one way,  
question is what it costs.)

(I had confused myself into thinking I needed to do this on every  
iteration, which is why I jumped to the "with accumulator" design.  
Which just shows that "slow down you'll get there faster" is much  
better -- and I preach this to my students all the time!!!)

-- Matthias

Posted on the users mailing list.