recur.scm

;; 非末尾再帰版map:
(define (map f xs)
  (if (null? xs)
    '()
    (cons (f (car xs)) (map f (cdr xs)))))

;; CPSによる末尾再帰版map (計算量同じ)
(define (map f xs)
  (define (rec xs k)
    (if (null? xs)
      (k '())
      (rec (cdr xs) (lambda (r) (cons (f (car xs)) r)))))
  (rec xs values))

;; 末尾再帰版map (consで逆順に結果が積まれる→reverseで逆転すればよい、という外部知識が必要。)
(define (map f xs)
  (define (rec xs r)
    (if (null? xs)
      (reverse r)
      (rec (cdr xs) (cons (f (car xs)) r))))
  (rec xs '()))