使用映射，追加和遞歸調用的球拍功能解釋

Question

此過程使用非負整數n，並按照真值表所需的特定順序創建所有n 0或1的列表的列表。我只是想了解該過程的地圖部分如何工作。我特別困惑的是，在if的第二個參數中append，map和遞歸調用是如何一起工作的。任何幫助將非常感激！

(define all-lists 
    (lambda (n) 
    (if (= n 0) 
     '(()) 
     (append (map (lambda (k) (cons 0 k)) (all-lists (- n 1))) 
       (map (lambda (k) (cons 1 k)) (all-lists (- n 1))) 
      )))) 

Answer 1

瞭解遞歸函數的最佳策略是與sligthly比端子一個更復雜的情況下嘗試。所以，讓我們試試n=1。

在這種情況下，該函數變爲：

(append (map (lambda (k) (cons 0 k)) (all-lists 0)) 
     (map (lambda (k) (cons 1 k)) (all-lists 0)) 

那就是：

(append (map (lambda (k) (cons 0 k)) '(())) 
     (map (lambda (k) (cons 1 k)) '(()))) 

所以，第一個map應用功能(lambda (k) (cons 0 k))到列表'(()))，它只有中的所有元素元素'()，生成'((0))（該列表包含由,0和空列表獲得的元素），並以相同的方式第二張地圖產生'((1))。 這些列表附在一起產生列表'((0) (1))，換句話說，所有長度爲1的列表以及所有可能的組合0和1。

在n=2的情況下，遞歸情況下被施加到'((0) (1))：使第一地圖把一個0所有元素之前，獲得'((0 0) (0 1))，而所述第二地圖生成'((1 0) (1 1))。如果將這兩個列表附加在一起，則獲得'((0 0) (0 1) (1 0) (1 1))，這是所有可能組合的列表，長度爲2，0和1。

等等，等等...

實際上，功能不明確的，因爲它在每個遞歸計算(all-lists (- n 1))兩次不必要的價值，所以翻番的工作，這已經是指數。

(define all-lists 
    (lambda (n) 
    (if (= n 0) 
     '(()) 
     (let ((a (all-lists (- n 1)))) 
      (append (map (lambda (k) (cons 0 k)) a) 
        (map (lambda (k) (cons 1 k)) a)))))) 

Answer 2

分離與「調用println」一起報表可以幫助理解發生了什麼：

(define (all-lists n) 
    (if (= n 0) 
     '(()) 
     (let* ((a (all-lists (- n 1))) 
       (ol1 (map (λ (k) (cons 0 k)) a)) 
       (ol2 (map (λ (k) (cons 1 k)) a)) 
       (ol (append ol1 ol2))) 
      (println "---------") 
      (println ol1) 
      (println ol2) 
      (println ol) 
      ol))) 

(all-lists 3) 

所以它可能是通過計算值只有一次，例如通過以下方式更有效的製造輸出：

"---------" 
'((0)) 
'((1)) 
'((0) (1)) 
"---------" 
'((0 0) (0 1)) 
'((1 0) (1 1)) 
'((0 0) (0 1) (1 0) (1 1)) 
"---------" 
'((0 0 0) (0 0 1) (0 1 0) (0 1 1)) 
'((1 0 0) (1 0 1) (1 1 0) (1 1 1)) 
'((0 0 0) (0 0 1) (0 1 0) (0 1 1) (1 0 0) (1 0 1) (1 1 0) (1 1 1)) 
'((0 0 0) (0 0 1) (0 1 0) (0 1 1) (1 0 0) (1 0 1) (1 1 0) (1 1 1)) 

人們可以清楚地看到outlists（ol1，ol2和組合ol）在每一步如何變化。