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 已經正確實現，更容易找到任何問題。

摺疊在函數語言程式設計中經常用來以非常簡潔的方式表達問題解決方案，或者避免重複編寫相同的程式碼來定義遞迴。