3 ms·
The map definition that OP uses doesn't look like a pure tail-recursive one: ; map-kuro5hin : (X -> Y) * (listof X) -> (listof Y) ; http://www.kuro5hin
by d0mine 18y ago
The map definition that OP uses doesn't look like a pure tail-recursive one:
; map-kuro5hin : (X -> Y) * (listof X) -> (listof Y)
; http://www.kuro5hin.org/story/2004/3/17/93442/8657
(define (map-kuro5hin func a-list)
(cond
[(null? a-list) null]
[else (cons (func (car a-list)) (map-kuro5hin func (cdr a-list)))]))
In a simple substitution model it unwraps to:
(define sq (lambda (x) (* x x)))
(map-kuro5hin sq '(1 2 3))
(cons (sq 1) (map-kuro5hin sq '(2 3)))
(cons (sq 1) (cons (sq 2) (map-kuro5hin sq '(3))))
(cons (sq 1) (cons (sq 2) (cons (sq 3) (map-kuro5hin sq '()))))
(cons (sq 1) (cons (sq 2) (cons (sq 3) '())))
(cons (sq 1) (cons (sq 2) '(9)))
(cons (sq 1) '(4 9))
'(1 4 9)
In this model it uses stack to store the result list. Of cause an actual Scheme implementation might perform the calculation without using stack.
Here's a pure tail-recursive variant:
; make external definition to allow unwrapping demonstration
(define (map-iter func lst result)
(if (null? lst) result
(map-iter func (cdr lst) (cons (func (car lst)) result))))
(define (map-tr func a-list)
(map-iter func (reverse a-list) '()))
That translates to:
(map-tr sq '(1 2 3))
(map-iter sq (reverse '(1 2 3)) '())
(map-iter sq '(3 2 1) '())
(map-iter sq '(2 1) (cons (sq 3) '()))
(map-iter sq '(1) (cons (sq 2) '(9)))
(map-iter sq '() (cons (sq 1) '(4 9)))
'(1 4 9)