定義「級別」功能的Scheme（Pretty Big）

Question

我試圖在Scheme中定義一個函數，使用漂亮的Big語言（在Dr. Racket中）將列表並將所有'atoms'轉換爲頂級元素。例如，如果給定：

(level '(a b (c d) (e f (g 4 h)))) 
;=> (a b c d e f g 4 h) 

這裏是我到目前爲止的代碼：

;;level -takes list and returns list w/all elements as top-level 
(define level 
    (lambda (L) 
    (cond ((null? L) L) 
      ((not(pair? L)) L) 
      (else (append (level(car L)) (level(cdr L))))))) 

我的錯誤如下：

append: contract violation 
    expected: list? 
    given: d 

誰能幫我解決這個問題？

Answer 1

欲瞭解更多有關如何實現flatten（這是這種功能通常被稱爲），看看

• Writing flatten method in Scheme

至於您的特定錯誤， append預計其所有參數（通常可能需要兩個以上）是列表。例如，

> (append '(1 2 3) '(4 5 6)) 
;=> (1 2 3 4 5 6) 
> (append '(1 2 3) '(4 5 6) '(7 8 9)) 
;=> (1 2 3 4 5 6 7 8 9) 

現在，你寫你的函數，和你說level應該返回一個列表。這意味着如果level有幾個不同的執行路徑，每個需要產生一個列表。所以，讓我們來看看你的實現。

(define level 
    (lambda (L) 
    (cond ((null? L) L) 
      ((not(pair? L)) L) 
      (else (append (level(car L)) (level(cdr L))))))) 

在的問題，你說你寫的應該採取列表的功能，所以L可以是兩件事情之一;它可以是空列表，也可以是一對。目前，您的cond有三個個案，但。

(cond ((null? L) L)         ; handle an empty list 
     ((not(pair? L)) L) 
     (else (append (level(car L)) (level(cdr L))))) ; handle a pair 

如果你總是用列表調用level，你並不需要的第二種情況。然而，由於在第三種情況下，你做呼叫(level (car L))，你不知道要不要(car L)是否將是一個列表，好像你做最終調用level與非名單。您需要決定是否合適，例如(level 'a)是否合法，以及是否應該合法。目前，您似乎想要使(level 'a)合法，並返回(a)。這很好，但你應該指定合同。如果這是你想要做的，那麼你確實需要第二種情況在你的cond，但因爲(level 'a)應該返回(a)，你實際上需要這種情況下返回(list L)，而不是L。

這裏的另一種選擇，如果你做想level要嚴格，並總是需要一個列表作爲參數，那麼你需要添加一些邏輯來確定(car L)是否是一個列表，如果是，遞歸調用level，並調用append的結果。這樣做的一個方法是這樣的：

(define (level L) 
    (cond 
    ((null? L) L) 
    ((pair? L) (append (if (list? (car L)) 
          (level (car L)) 
          (list L)) 
         (level (cdr L)))))) 

Answer 2

追加列表中的作品。如果您撥打level並列出'(1 2 3)第一次迭代，它將執行(append (level '1) (level (cdr '(2 3)))。現在'1是沒有對，因此將評估爲1，這是而不是的一個列表。這就像打電話給(append '1 ...)這是違反合同。

編輯

這裏是flatten在大漂亮的一個實現。這是基於Chris Jester-Young的answer for a similar question。它比append版本更有效率。

(define (flatten lst) 
    ;; helper function that accumulates 
    (define (reverse-flatten-into x lst) 
    (if (pair? x) 
     (foldl reverse-flatten-into lst x) 
     (cons x lst))) 

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

Answer 3

每當你定義一個遞歸函數，每個條款都應該回到一個相似類型的對象。在你的情況下，第三個子句中的遞歸調用需要返回一個列表（供append使用），但第二個子句返回一個'atom'。因此，編譯器/運行時會抱怨'期望列表'。

修復此問題的方法是在第二個cond子句中返回(list L)。