[gambit-list] "Number of arguments exceeds implementation

Guillaume Germain germaing at iro.umontreal.ca
Wed Sep 6 12:11:24 EDT 2006


On Wed, 6 Sep 2006, Bill Richter wrote:

> Thanks, Christian.  That's a very helpful way to put it: functions
> like map can't be tail-recursive if they preserve the order unless we
> use mutation. (Unless you throw in some `reverse's)

Why not?

(define (map* f lst)
   (define (m* lst k)
     (if (null? lst)
         (k '())
         (m* (cdr lst)
             (lambda (x)
               (k (cons (f (car lst)) x))))))
   (m* lst (lambda (x) x)))


No mutation, no 'reverse'.  I think tail-recursion isn't the property 
you're thinking about, but rather whether such an algorithm can be 
executed in O(1) space (then only mutation would help, not using 
'reverse').


Guillaume



More information about the Gambit-list mailing list