(define (filter-map/tail fn tail lis . morelis) [...] )
Christian, your code isn't tail-recursive, right?
No it's not - it can't be if the order of the output should be the same as the input (and mutation isn't used).
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) I had noted that mutation was used in various tail-recursive map-like functions, but I had only dimly noted the rule.
I have my Sudoku code working now. It takes too long, but 1) quite likely that's because of beginner tail-recursion problems 2) The real problem was some "infinite loops" that I fixed.
Afficher les réponses par date
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
Thanks, Guillaume! So I was wrong. Would you call your definition of map* CPS? I think of your k as the continuation. Is it any faster than reverse first & then do the easy recursive function?
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').
That might be what Christian meant :-D I generally get confused by words like O(1). But I wouldn't think your CPS code was going to be very fast. I'd say that the usual recursive program was using a lot of stack space, as there are so many pending operations. I'd say that your CPS version was just storing this stack space in the body of a lambda, and that's gotta be stored somewhere, right?