Scheme 编程/循环

简单递归

Scheme 在某种意义上非常奇怪，它没有为循环、重复或在一般级别上多次执行某些操作而设计的表达式。实现此目的的唯一简单方法是递归，即设计一个过程，使其满足两个条件

1. 该过程必须具有一个它停止的基线情况
2. 该过程必须调用自身，可能使用修改后的参数。

最简单的递归过程是尾递归过程。让我们考虑如何计算一个整数的阶乘。一个整数的阶乘是该整数乘以它下面的所有整数。

$n!=n\cdot (n-1)\cdot (n-2)\cdots 1$

现在，经过一点点巧妙的观察，我们发现这个函数有一个特殊之处

$n!=n\cdot (n-1)!$

现在我们需要做的就是有一个基线情况。0! 是 1（对此的数学解释超出了本书的范围）。现在我们有了阶乘和不同（更小）数字的阶乘之间的关系，以及一个基线情况，我们可以快速编写一个阶乘函数的递归定义

(define ! 
 (lambda (n) 
  (if (= n 0) 
    1 
    (* n (! (- n 1))))))

现在我们只需要测试一下它是否有效。

> (! 5)
120
> (! 6)
720

如您所见，这似乎有效。这展示了最基本递归函数的一般形式。

(define <Name>
 (lambda (<Params>)
  (if (<Base Predicate>)
    <Base Case Body>
    (<Operation> (<Name> <Modified Parameters>))))

但是，这会导致一种计算整数阶乘的低效方法，因为 Scheme 必须跟踪所有中间变量。例如，让我们看看 `(! 5)` 的执行流程

(! 5)
(* 5 (! 4))
(* 5 (* 4 (! 3)))
(* 5 (* 4 (* 3 (! 2))))
(* 5 (* 4 (* 3 (* 2 (! 1)))))
(* 5 (* 4 (* 3 (* 2 (* 1 (! 0))))))
(* 5 (* 4 (* 3 (* 2 (* 1 1)))))
(* 5 (* 4 (* 3 (* 2 1))))
(* 5 (* 4 (* 3 2)))
(* 5 (* 4 6))
(* 5 24)
120

请注意，它如何扩展和收缩，以及每个中间值是如何存储的。关于所需的空间量，这非常低效。想象一下尝试找到 1000 的阶乘。你需要 1000 个关于你到目前为止位置的小笔记。除非没有其他方法，否则通常不建议这样做。

让我们尝试实现一种稍微抽象一点的方法。想想将一系列值加在一起

$\sum _{n=Lower}^{Upper}f(n)$

它转化为

$f(Lower)+f(Lower+1)+\cdots +f(Upper)$

这也可以转换为一个 Scheme 过程

(define sum 
 (lambda (f lower upper)
  (if (> lower upper)
    0
    (+ (f lower) (sum f (+ 1 lower) upper)))))

同样，我们可以测试一下；

> (sum (lambda (x) x) 1 10) ; Using lambda here to only output the numbers 1 through 10
55

这也表现出与之前的阶乘过程类似的缺陷：它占用了大量的“堆栈空间”。

'do' 表达式

还有一个迭代结构 do，它可以简化编写某些函数。例如，此过程将给定列表中的所有元素加在一起

(define (sum/display lst)
  (do ((remaining lst (cdr remaining))
       (final-sum 0 (+ final-sum (car remaining))))
    ((null? remaining) final-sum)
    (display (car remaining))
    (newline)))

(sum/display '()) 
> 0

(sum/display '(1 2 3 7))
1
2
3
7
> 13

在这里，局部变量 remaining 和 final-sum 分别被赋予 lst 和 0 的初始值。然后测试用例，这里是 (null? remaining) 被评估。如果测试成功，则评估以下表达式，并成为整个 do 表达式的最终值。如果测试失败，Scheme 将评估 display 和 newline 行以获取它们的副作用，然后分别使用 (cdr remaining) 和 (+ final-sum (car remaining)) 的值重新定义 remaining 和 final-sum。我们可以概括如下

(do ((var1 base1 exp1) (var2 base2 exp2) ...)
  ((test? ...) final-exp)
 side-effecting-statements ...)

这首先创建变量 var1、var2、... 并赋予它们初始值 base1、base2、... 然后测试用例 (test? ...) 被评估，如果成功，则函数评估并返回 final-exp。如果测试失败，则执行副作用语句 ...，var1、var2、... 使用来自 exp1、exp2、... 的新值重新定义，然后再次评估测试用例。如果未提供适当的测试用例，则可能导致 Scheme 中的错误或无限循环。

map 和 for-each

Scheme 定义了两个函数来遍历列表。map 和 for-each 都遍历列表中的每个元素，并使用每个元素调用一个过程。Map 存储对该函数的每次调用的返回值，而 for-each 则不存储

(map (lambda (x) (* x 2)) '(1 2 3 4 5 6))
> (2 4 6 8 10 12)

(for-each (lambda (x)
            (display (* x 2))
            (newline))
  '(1 2 3 4 5 6))
2
4
6
8
10
12
>

实际上，for-each 类似于许多编程语言中的“foreach”循环。事实上，我们可以将这样的循环定义为新的语法，将其添加到语言中

(define-syntax foreach
 (syntax-rules ()
  ((_ ((variables lists) ...)
    body ...)
   (for-each (lambda (variables ...) body ...) lists ...))))

由此产生的“foreach”形式会并行遍历多个列表

(foreach ((number '(1 2 3 4 5))
          (letter '(a b c d e)))
 (display (list number letter))
 (newline))

(1 a)
(2 b)
(3 c)
(4 d)
(5 e)
>

迭代递归

我们可以使用迭代递归来减少许多过程的空间需求。我们将再次看一下阶乘过程。与其保留一个很长的要稍后乘以的所有值的列表，不如我们可以保留一个不断变化的答案，并将其传递给我们过程的下一个调用。让我们看看它在应用于阶乘函数时是如何工作的

(define !-it
 (lambda (n current)
  (if (= n 0)
    current
    (!-it (- n 1) (* n current)))))

现在我们可以检查一下它是否有效

> (!-it 5 1)
120
> (!-it 6 1)
720

如我们所见，这既有自动的优势，也有劣势。我们使它使用更少的空间，并且需要在调用时有效地指定基线情况。我们将首先调查它生成的计算过程。

我们将再次跟踪 5! 的计算，但这次使用迭代过程

(!-it 5 1)
(!-it 4 5)
(!-it 3 20)
(!-it 2 60)
(!-it 1 120)
120

注意，这个过程永远不会扩展然后收缩，并且没有“留待以后”的东西（通常被称为“延迟处理”），并且该过程的这个版本只跟踪两个变量，无论其输入大小如何。

现在我们将解决额外的不必要参数问题；这需要稍微重新定义一下过程，

(define !
 (lambda (x)
  (define !-internal
   (lambda (n current)
    (if (= n 0)
      current
      (!-internal (- n 1) (* n current)))))
  (!-internal x 1)))

这通过展示 Scheme 中一个以前未介绍的功能来解决这个问题。也就是说；函数可以在内部包含新函数和变量的定义。这些在过程外部是不可见的。这个新的过程解决了我们之前遇到的两个关于第一个递归阶乘过程的问题。它在恒定空间内运行，并且易于使用。

现在我们将展示 sum 也可以用非常类似的方式实现

(define sum
 (lambda (f lower upper)
  (define sum-int
   (lambda (f lower upper current)
    (if (> lower upper)
      current
      (sum-int f (+ lower 1) upper (+ (f lower) current)))))
  (sum-int f lower upper 0)))

有趣的一点是，阶乘和求和都可以抽象到一个更通用的过程中，该过程可以用于更多场景，而不仅仅是阶乘和求和。允许实现乘积、数值积分和其他有趣的方法。我把这留给读者练习（这并不难，但如果你以前从未做过编程，或者没有数学背景，那么这个练习可能很有挑战性）。

遍历列表

假设我们有一个列表，我们需要找到列表中是否包含某个元素。我们需要遍历列表中的每个元素，并将其与我们想要的结果进行比较。

(define exists-in?
 (lambda (ele lis)
  (cond ((null? lis) #f)
        ((equal? ele (car lis)) #t)
        (else (exists-in? ele (cdr lis))))))

注意我们首先检查是否还有元素可以进行比较，这防止我们尝试对空列表进行 cdr 操作（从而导致错误）。然后，我们检查是否匹配，否则继续搜索。除非你有无限列表（这在 Scheme 中是可能的，我们稍后会看到），否则此过程将得到一个确定的答案。

我们也可能遇到需要将每个列表元素加 2 的问题。

(define plustwo
 (lambda (lis)
  (cond ((null? lis) nil)
        (else (cons (+ (car lis) 2)
                    (plustwo (cdr lis)))))))

在这里，我们将列表的每个元素 '映射' 到某个值。在这个特定情况下，该值为每个列表元素的值加上 2。如果我们想要将列表中每个元素的值乘以 3？或者求平方根？我们每次都需要编写代码，而且每段代码看起来都非常相似。更合理的做法是抽象出特定函数，并允许程序员每次都进行替换。

(define map
 (lambda (f lis)
  (cond ((null? lis) nil)
        (else (cons (f (car lis))
                    (map f (cdr lis)))))))

现在我们可以更简洁地定义 plustwo

(define plustwo 
 (lambda (lis) 
  (map (lambda (x) (+ x 2)) lis)))

这展示了 Scheme 中一个非常重要的概念。函数可以像数字、字符串、原子和其他事物一样传递。利用这个思想，我们可以继续解决上面查找列表中是否存在元素的问题。

我们首先注意到函数的输出只能是 #t 或 #f，或者某个错误。忽略错误情况，我们可以开始编写一种方法来抽象出测试每个单独元素以判断其是否满足某个谓词的情况。然后，我们可以使用该函数来查找列表中是否有任何元素等于给定的值，使用 map。

我们希望能够将这样的值的列表 "折叠" 成一个单独的值：如果任何值是 #t，则为 #t，否则为 #f。我们将函数命名为 foldr。

(define foldr
 (lambda (f e lis)
  (cond ((null? lis) e)
        (else (f (car lis) 
                 (foldr f e (cdr lis)))))))

现在，我们可以使用这个折叠函数来定义一个名为 any 的函数，该函数告诉我们列表中是否有任何元素满足某个谓词（谓词是一个返回 #t 或 #f 的函数）。

(define any
 (lambda (pred lis)
  (foldr (lambda (x acc) (or x acc)) 
      #f 
      (map pred lis))))

使用这个函数，我们可以将 exists-in? 重写为一个更简单的函数。

(define exists-in?
 (lambda (ele lis)
  (any (lambda (x) (equal? x ele))
     lis)))

这更易于理解为 "列表 'lis' 中是否有任何元素等于 'ele'？"。它也更短，而且考虑到 foldr、map 和 any 已经正确实现，更容易找到任何问题。

折叠在函数式编程中经常用来以非常简洁的方式表达问题解决方案，或者避免重复编写相同的代码来定义递归。