改进方案中的迭代函数

Question

我经常在 scheme 中编写迭代函数时遇到困难：它使编写递归过程变得更加简单。下面是一个尝试使用迭代过程对列表中的项目进行平方的示例：

(define square (lambda (x) (* x x)))
(define (square-list items)
  (define result nil) ; set result
  (define (iter items-remaining)
    (if (null? items-remaining)
        result
        (set! result (cons (car items-remaining) (iter (cdr items-remaining))))))
  (iter items))

(square-list '(1 2 3 4 5))
; (4 9 16 25)

我的主要问题是：

有没有一种方法可以执行此过程 而无需 必须在内部过程之前先定义 result？我试图使迭代过程具有 define (iter items-remaining answer) 的函数原型，但很难以这种方式实现它。
如果不能，那为什么不可能呢？

Answer 1

发布的代码无效；但即使修复后确实工作，这也不是惯用的 Scheme 解决方案。

要使发布的代码正常工作：

nil 必须替换为 '()，因为 Scheme 不表示空列表 nil
square 必须在 items-remaining

car

set! 应该通过添加平方数来修改 result，而不是尝试添加递归调用的结果。这在这里根本不起作用，因为 set! returns 未指定的值；但即使它确实工作了，这也不会是尾递归的（即，这不会是迭代过程）
result的值必须返回，并且必须先反转，因为result实际上是一个累加器

这是一个修复后的版本：

(define (square-list-0 items)
  (define result '()) ; set result
  (define (iter items-remaining)
    (cond ((null? items-remaining)
           result)
          (else
           (set! result (cons (square (car items-remaining))
                              result))
           (iter (cdr items-remaining)))))
  (iter items)
  (reverse result))

更好的解决方案是不使用变异，也不需要 (define result '()):

(define (square-list-1 xs)
  (define (iter xs acc)
    (if (null? xs)
        (reverse acc)
        (iter (cdr xs) (cons (square (car xs)) acc))))
  (iter xs '()))

此处将累加器 acc 添加到 iter 过程的 lambda 列表中。在计算结果时，它们被放入 acc，这意味着在此过程结束时，acc 中的第一个数字基于 xs 中的最后一个数字。因此，累加器在返回之前被反转。

另一种方法，可能是更惯用的解决方案，是使用 命名为 let:

(define (square-list-2 xs)
  (let iter ((xs xs)
             (acc '()))
    (if (null? xs)
        (reverse acc)
        (iter (cdr xs) (cons (square (car xs)) acc)))))

这样更简洁一些，它允许您在 iter 过程定义的开头将参数绑定到它们的参数。

以上三个解决方案都定义了迭代过程，并且三个都给出了相同的结果：

> (square-list-0 '(1 2 3 4 5))
(1 4 9 16 25)
> (square-list-1 '(1 2 3 4 5))
(1 4 9 16 25)
> (square-list-2 '(1 2 3 4 5))
(1 4 9 16 25)

当然，你可以只使用map:

> (map square '(1 2 3 4 5))
(1 4 9 16 25)

改进方案中的迭代函数

Improving an iterative function in scheme

scheme

lisp

sicp