clisp正數創始人

Question

我想從使用clisp的函數參數列表中返回一個包含非負數的列表。

(defun recursive (L) 
    (setq ret (list)) 
    (setq first (car L)) 
    (setq rest (cdr L)) 
    (if (null L) 
     0 
     (if (>= first 0) 
      (nconc ret (first)) 
      (recursive rest)))) 

(setq mylist (list 1 2 3 -1 0 -3)) 
(write (recursive mylist)) 

我寫了這一點，並希望輸出爲(1 2 3 0)

什麼是錯誤的代碼？

Answer 1

首先，你的代碼不能正常工作，因爲你的方法是使用first在你if當時的分支功能（(first)）。

除此之外，每當您撥打recursive時，您都會將ret重新初始化爲空列表。而且裏面的if你只，如果數字是不是一個使用cond一個可行的解決方案大於0

這裏遞歸：

(defun filter-non-negative (l) 
    (cond 
    ((null l)     ;; empty list 
    nil) 
    ((>= (first l) 0)  ;; number >= 0 
    (cons (first l) (filter-non-negative (rest l)))) 
    (t       ;; all other cases 
    (filter-non-negative (rest l))))) 

(write (filter-non-negative '(1 2 3 -1 0 -3))) 
;; (1 2 3 0) 

Answer 2

首先，變量ret，first和rest應該被定義本地與let。在你的版本中，它們是全局變量。請注意，根本不需要這些變量，您可以直接使用函數調用。 在最後一行中，您有(first)，這將表示錯誤，因爲此函數需要參數。但是，您要的不是函數first而是變量first，因此您需要(list first)。 當列表爲空時，您返回0。由於您將在每次遞歸調用結束時到達此位置，因此將爲任何輸入參數添加0。你應該返回零。 最後，而不是nconc看功能cons。

順便說一句，請注意，有一個功能remove-if將完成您想要的工作，但我知道您正在嘗試瞭解遞歸調用。 我希望這可以幫助。

Answer 3

讓filter成爲您想要實現的功能。 然後(filter nil)應該返回零。 在一般情況下，你遞歸地編輯(filter (number . tail))。假設filter計算列表中的正數列表，則可以解決tail的問題，並調用(filter tail)。爲了解決當前的問題，您必須考慮number是否爲正值，並相應地將該元素添加到遞歸結果中。

(defun filter (list) 
    (etypecase list 
    (null nil) 
    (cons (destructuring-bind (number . tail) list 
      (if (plusp number) 
       (cons number (filter tail)) 
       (filter tail)))))) 

我使用ETYPECASE，PLUSP，DESTRUCTURING-BIND，但您可以採用不同表達相同。請注意，您使用的是NCONC，它需要遍歷整個列表，這不是必需的，並且可以使您的整個問題在時間上保持二次方。

上述函數存在缺陷，因爲調用堆棧的大小隨輸入列表的大小線性增長。每次調用過濾器時，一個新的幀分配在棧，可與TRACE很容易地看到：

CL-USER> (trace filter) 
(FILTER) 
CL-USER> (filter '(0 1 -2 3 -4 -5 6 7 -8 9)) 

0: (FILTER (0 1 -2 3 -4 -5 6 7 -8 9)) 
    1: (FILTER (1 -2 3 -4 -5 6 7 -8 9)) 
    2: (FILTER (-2 3 -4 -5 6 7 -8 9)) 
     3: (FILTER (3 -4 -5 6 7 -8 9)) 
     4: (FILTER (-4 -5 6 7 -8 9)) 
      5: (FILTER (-5 6 7 -8 9)) 
      6: (FILTER (6 7 -8 9)) 
       7: (FILTER (7 -8 9)) 
       8: (FILTER (-8 9)) 
        9: (FILTER (9)) 
        10: (FILTER NIL) 
        10: FILTER returned NIL 
        9: FILTER returned (9) 
       8: FILTER returned (9) 
       7: FILTER returned (7 9) 
      6: FILTER returned (6 7 9) 
      5: FILTER returned (6 7 9) 
     4: FILTER returned (6 7 9) 
     3: FILTER returned (3 6 7 9) 
    2: FILTER returned (3 6 7 9) 
    1: FILTER returned (1 3 6 7 9) 
0: FILTER returned (1 3 6 7 9) 

這是因爲你需要記住的跨遞歸調用number到cons每一箇中間值，爲了他們以遞歸結果。如果您可以在下降到遞歸調用之前完成所有工作，那麼不需要保留中間值，並且該函數將是遞歸終端並且可以服從於所謂的尾部呼叫優化。 爲了做到這一點，你必須調用遞歸調用，通過蓄能器之前，建立結果列表：

(defun filter (list accumulator) 
    (etypecase list 
    (null accumulator) 
    (cons (destructuring-bind (head . tail) list 
      (if (plusp head) 
       (filter tail (cons head accumulator)) 
       (filter tail accumulator)))))) 

注意重複，可重構爲：

(filter tail (if (plusp head) (cons head accumulator) accumulator)) 

這裏以上，我們添加了一個accumulator，其中包含新列表。最初，你應該通過一個空的列表。當您到達輸入列表的末尾時，您將返回累加器。否則，在遞歸調用filter之前，將該數字添加到累加器。區別在於您不需要在調用堆棧中存儲中間值。跟蹤宏產生這樣的：

0: (FILTER (0 1 -2 3 -4 -5 6 7 -8 9) NIL) 
    1: (FILTER (1 -2 3 -4 -5 6 7 -8 9) NIL) 
    2: (FILTER (-2 3 -4 -5 6 7 -8 9) (1)) 
     3: (FILTER (3 -4 -5 6 7 -8 9) (1)) 
     4: (FILTER (-4 -5 6 7 -8 9) (3 1)) 
      5: (FILTER (-5 6 7 -8 9) (3 1)) 
      6: (FILTER (6 7 -8 9) (3 1)) 
       7: (FILTER (7 -8 9) (6 3 1)) 
       8: (FILTER (-8 9) (7 6 3 1)) 
        9: (FILTER (9) (7 6 3 1)) 
        10: (FILTER NIL (9 7 6 3 1)) 
        10: FILTER returned (9 7 6 3 1) 
        9: FILTER returned (9 7 6 3 1) 
       8: FILTER returned (9 7 6 3 1) 
       7: FILTER returned (9 7 6 3 1) 
      6: FILTER returned (9 7 6 3 1) 
      5: FILTER returned (9 7 6 3 1) 
     4: FILTER returned (9 7 6 3 1) 
     3: FILTER returned (9 7 6 3 1) 
    2: FILTER returned (9 7 6 3 1) 
    1: FILTER returned (9 7 6 3 1) 
0: FILTER returned (9 7 6 3 1) 

請注意，該函數是尾遞歸，但並不像它被優化掉，因爲有一個箭頭狀的痕跡。然而，跟蹤並不是一種可靠的方式來知道函數是否是尾遞歸的，因爲跟蹤行爲改變了帽子實際上完成了。或者，debug的質量可能很高，以至於不會應用尾部呼叫優化。這取決於你的實現。請注意，跟蹤清楚地顯示了中間列表是如何構建的，以及結果如何從深度級別傳遞到更高級別。另請參見該列表正在反向構建，因爲我們一直使用累加器調用cons（與nconc相反，這是有效的）。 由於您沒有指定是否希望列表中的元素保留與輸入列表相同的順序，因此我認爲這不是必需的。

但是，您也可以撥打NREVERSE結果列表上破壞性扭轉它（即就地，不分配內存）。如果這裏沒關係，因爲你的擁有新的列表正在建立，所以你可以安全地修改它，然後把它給予調用者。這是最好的包裝本地函數內部的實現細節做：

(defun filter (list) 
    (labels ((filter (list accumulator) 
      (etypecase list 
       (null accumulator) 
       (cons (destructuring-bind (head . tail) list 
         (filter tail (if (plusp head) 
             (cons head accumulator) 
             accumulator))))))) 
    (nreverse (filter list nil)))) 

注意filter在詞法綁定到本地功能的全球filter函數內。另見LABELS。

但是，你可以更好地花你的時間比寫遞歸函數來執行循環。 Common Lisp中提供重複建設，這意味着你可以簡單地這樣做：

(defun filter (list) 
    (loop for number in list 
     when (plusp number) 
      collect number)) 

注意去除列表元素也很容易與REMOVE-IF-NOT完成。

Answer 4

你想保留正數。正數大於0。

讓我們移除哪些不是正面的所有號碼：

CL-USER 24 > (remove-if-not #'plusp (list 1 2 3 -1 0 -3)) 
(1 2 3) 

或

CL-USER 25 > (remove-if (complement #'plusp) (list 1 2 3 -1 0 -3)) 
(1 2 3)