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