Scheme：返回可以使用汽車和CDR的任意組合獲得的表達式的所有元素

Question

我試圖在我的CS類的Scheme（R5RS）中編寫一個過程，該過程需要一個表達式（符號或列表）作爲參數，並返回（1）可以通過在表達式上使用car和cdr形成的所有可能表達式和（2）以及表達如何獲得原始表達式的每個這些分量的表達式的列表。如果一件作品可以以多種方式獲得，則應該多次返回。

Examples 

(pieces '()) => ((() x)) 

(pieces 'apple) => ((apple x)) 

(pieces '(apple)) => (((apple) x) (apple (car x)) (() (cdr x))) 

(pieces '(a (b c))) => 
       (((a (b c)) x) 
       (a (car x)) 
       (((b c)) (cdr x)) 
       ((b c) (car (cdr x))) 
       (b (car (car (cdr x)))) 
       ((c) (cdr (car (cdr x)))) 
       (c (car (cdr (car (cdr x))))) 
       (() (cdr (cdr (car (cdr x))))) 
       (() (cdr (cdr x)))) 

由於我們剛剛開始計劃，我們僅限於這個任務相當基本的語法。這是我到目前爲止有：

(define pieces 
    (lambda (exp) 
    (cond 
     ((symbol? exp) 
     (list exp 'x)) 
     ((null? exp) 
     (list '() 'x)) 
     ((list? exp) 
     (let ((b (pieces (car exp))) (c (pieces (cdr exp)))) 
      (list exp 'x b c)))))) 

(pieces '()) => (() x) 

(pieces 'apple) => (apple x) 

(pieces '(apple)) => ((apple) x (apple x) (() x)) 

(pieces '(a (b c))) => ((a (b c)) x (a x) (((b c)) x ((b c) x (b x) ((c) x (c x) (() x))) 
         (() x))) 

過程返回所有適當的元素，但每個遞歸導致嵌套在一個額外的組件列表中。有什麼辦法可以防止這種情況發生？

此外，我不知道從哪裏開始解決問題的第二部分（顯示每個元素是如何從原始使用汽車和CDR獲得的）。我嘗試了一百萬種不同的方法，他們中的任何一個都沒有接近工作。如果任何人有任何關於如何實現該功能的提示或建議，我會非常感激。萬分感謝。

Answer 1

(pieces 'apple) => (apple x) 

但它應該是((apple x))，對吧？你應該得到一個列表，其中第一個也是唯一的元素是列表(apple x)。

cond特殊條款，終止遞歸（EXP是一個符號或空）回報的項目，應該在列表中，而在car和cdr嘗試復發的子句創建項目列表。作爲pieces可以返回項目的兩個項目，並列出它是一種很難做的項目列表的是從它的返回值的：當你做(list exp 'x b c)你不知道，如果b和c是應該進入項目項目清單或列表。

如果您確定pieces總是返回一個項目列表（例如(list (list exp 'x))），它會變得更容易。當您在car和cdr上再次發生時，您想要執行類似append的列表a和b，並將「當前」（(list exp 'x)）項目添加到該列表（可能使用cons或其他）。

對於第二部分，pieces必須知道它是如何得到當前項目。您可以使pieces將當前項目的「路徑」作爲（可選）參數。如果路徑是一個列表，那麼當你在(car exp)叫pieces你可以添加一個car符號你發送作爲參數的路徑，併爲(cdr exp)您可以添加符號cdr。然後，您使用該路徑創建一些很好的內容以替換(list exp 'x)中的'x。

Answer 2

我知道這不是計劃，但也許尋找類似的語言會有所幫助。我這樣做更多的練習自己，所以把它與鹽的點滴，但它似乎在做的正是你追求的：

(defun parse-list (whatever) 
    (labels ((pieces (expression &optional path) 
     (cond 
      ((null expression) 
     `((,path . nil))) 
      ((listp expression) 
     (append (list 
      `(,path . ,expression)) 
      (pieces (car expression) 
       (cons 'car path)) 
      (pieces (cdr expression) 
       (cons 'cdr path)))) 
      (t `((,path . ,expression)))))) 
    (dolist (output (pieces whatever)) 
     (format t "path ~a => result ~a~&" 
      (car output) (cdr output))))) 

(parse-list '(a (b c))) 

然後產生這樣的輸出：

path NIL => result (A (B C)) 
path (CAR) => result A 
path (CDR) => result ((B C)) 
path (CAR CDR) => result (B C) 
path (CAR CAR CDR) => result B 
path (CDR CAR CDR) => result (C) 
path (CAR CDR CAR CDR) => result C 
path (CDR CDR CAR CDR) => result NIL 
path (CDR CDR) => result NIL 

對不起，我沒有得到SO的代碼格式比這更好:)