[plt-scheme] Re: Some fine distinctions

On May 13, 2009, at 9:58 AM, wooks wrote:

>
>
> On May 13, 2:47 pm, Robby Findler <ro... at eecs.northwestern.edu> wrote:
>> (but it is an arity error so maybe that doesn't count...)
>>
> Ach!!
>
> fixed the arity error and the incorrect base case.
>
> sumlists :: listoflists -> number
> (define sumlists
>   (lambda (a-list)
>      (let sumlists ([a-list a-list] [accum 0])
>        (cond
>         [(empty? a-list) accum]
>         [(list? (first a-list)) (sumlists (rest a-list)
>                                  (+ accum (sumlists (first a-list))
> 0))]
>         [else (sumlists (rest a-list) (+ accum (first a-list)))]))))
>
> So I repeat. It's not tail recursive and I don't see how it could be
> made to be.
> If I'm right about the first two, isn't one better off writing it
> stack recursively.

*Anything* can be made tail-recursive.

Here's an off-the cuff version:

;;sumlists :: listoflists -> number
(define sumlists
   (lambda (a-list)
      (let sumlists ([a-list a-list] [accum 0] [stack empty])
        (cond
         [(empty? a-list) (cond [(empty? stack) accum]
                                [else (sumlists (first stack) accum  
(rest stack))])]
         [(list? (first a-list)) (sumlists (first a-list) accum (cons  
(rest a-list) stack))]
         [else (sumlists (rest a-list) (+ accum (first a-list))  
stack)]))))

My one test case suggests that it works.

John Clements

-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/pkcs7-signature
Size: 2484 bytes
Desc: not available
URL: <http://lists.racket-lang.org/users/archive/attachments/20090513/6d92b7d7/attachment.p7s>