方案中的迭代映射

Question

我正在观看 SICP 视频讲座，我来到了一个部分，其中导师正在展示使用列表的程序，因此，这是其中之一：

(define (map p l)
   (if (null? l) 
       (list)
       (cons (p (car l))
                    (map p (cdr l)))))

我想问的是：有没有办法以map迭代方式定义，或者cons需要正确执行延迟评估？

Answer 1

你的原始代码几乎是尾递归的......唯一使它不是的就是cons部分。如果计划有平等的要求，对具有TRMC优化，因为它有TCO的要求，你可以留下你的代码是和实现将使它尾递归你。

由于这不是必需的，我们需要进行我们自己的 TRMC 优化。通常，当在循环中迭代列表并使用累加器对其进行尾递归时，您会得到相反顺序的结果，因此您可以进行反向线性更新：

(define (map proc lst)
  (let loop ((lst lst) (acc '()))
    (cond ((null? lst) (reverse! acc) acc)
          (else (loop (cdr lst) 
                      (cons (proc (car lst)) acc))))))

或者您可以一次性完成所有操作：

(define (map proc lst)
  (define head (list 1))
  (let loop ((tail head) (lst lst))
    (cond ((null? lst) (cdr head))
          (else (set-cdr! tail (list (proc (car lst))))
                (loop (cdr tail) (cdr lst))))))

现在，在这两种情况下，您只改变过程本身创建的结构，因此对于用户来说，它也可能以与您的示例相同的方式实现。

当您使用更高阶的程序时，比如map您的实现，它可能会发生这样的实现。通过比较map具有很长列表的不同实现的性能，很容易找到。执行之间的差异会告诉您它是 TRMCO 还是所提供的map可能是如何实现的。