僅使用「小小的Schemer」中的表單展開列表

Question

我正在通過輕鬆的Schemer學習Scheme（作爲一名老C程序員），並且作爲一個練習，我試圖編寫一個使用只有 The Little Schemer中的表格;即，define，lambda，cond，car，cdr，and，or等，但不append。我認爲這很容易，但我還沒有能夠提出解決方案。我怎樣才能做到這一點 ？

Answer 1

我只使用「第一原則」業務，並有效版本（不要求超過一個穿過任何名單中的，不像append基於解決方案） 。 :-)

它通過定義兩個簡單的積木（fold和reverse），然後定義flatten（及其助手，reverse-flatten-into）之上的（並注意各功能是如何一兩行代碼）做到這一點：

;; Similar to SRFI 1's fold 
(define (fold1 kons knil lst) 
    (if (null? lst) 
     knil 
     (fold1 kons (kons (car lst) knil) (cdr lst)))) 

;; Same as R5RS's reverse 
(define (reverse lst) 
    (fold1 cons '() lst)) 

;; Helper function 
(define (reverse-flatten-into x lst) 
    (if (pair? x) 
     (fold1 reverse-flatten-into lst x) 
     (cons x lst))) 

(define (flatten . lst) 
    (reverse (reverse-flatten-into lst '()))) 

使用的唯一外部功能是：cons，car，cdr，null?，和pair?。

從這個功能的關鍵洞察是，fold是一個非常強大的操作，應該是任何Schemer的工具包的一部分。而且，正如在上面的代碼中所看到的那樣，從第一原則構建起來非常簡單！

Answer 2

我不熟悉Little Schemer原語，所以您可能需要調整它以適應。

我不知道這是否是你想要的答案，但你可以寫append使用原語：

(define (append l1 l2) 
    (cond 
    ((null? l1) l2) 
    (else (cons (car l1) (append (cdr l1) l2))))) 

的flatten功能，可以在隨後的這個方面來寫。

不知道這是否超出規則或不:)

Answer 3

這是一個嘗試。它利用cons和避免追加來獲得利益，因爲它只是將第一個非對和第一個非對結合在一起，並將其變爲它已經構建的新尾部的扁平化。有時它會重寫列表，然後再次調用flatten。不是最有效的方法。

固定碼：

(define (flatten x) 
    (cond 
    ((null? x) x) 
    ((and (pair? x) 
      (not (pair? (car x)))) 
    (cond 
     ((null? (car x)) (flatten (cdr x))) 
     (else (cons (car x) (flatten (cdr x)))))) 
    ((and (pair? x) 
      (pair? (car x))) 
    (flatten (cons (caar x) 
        (cons (cdar x) (cdr x))))) 
    (else (cons x '()))))