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

ifのthen-branchでfirstを関数（(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)が必要です。 リストがnullの場合、0を返します。すべての再帰呼び出しの最後にこの点に達するので、入力引数に0が追加されます。代わりにnilを返すべきです。 最後に、nconcの代わりに、consを見てください。

なお、関数remove-ifには、あなたが望む仕事を正確に行う機能がありますが、再帰呼び出しについて学ぶことを理解しています。 私はこれが役立つことを願っています。

Answer 3

filterを実装したい機能にします。 (filter nil)は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を使用してリスト全体を反復処理する必要があることに注意してください。これは必須ではなく、すべてのaproachを時間的に二次的にします。

コールスタックのサイズが入力リストのサイズに比例して大きくなるため、上記の関数には欠陥があります。あなたは、フィルタを呼び出すたびに、新しいフレームが簡単にTRACEで見ることができ、スタック、上に割り当てられている：あなたが再帰呼び出しを越えnumberの各中間値を覚えておく必要があるため

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) 

これは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を呼び出して破壊的に逆にすることもできます（つまり、メモリを割り当てずにインプレース）。 がの新しいリストが作成されているため、ここではOKです。そのため、発信者に渡す前に安全に変更できます。これは、最高の地元の関数の内部実装の詳細をラップすることにより行われます字句グローバルfilter関数内ローカル関数にバインドされ

(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こと。 LABELSも参照してください。

ただし、ループを実行するための再帰関数を記述するよりも時間を消費する方が効果的です。リストから要素を削除するとも簡単にREMOVE-IF-NOTで行われていること

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

注意：Common Lispはあなたは、単にこれを行うことができることを意味し、反復構造を、提供しています。

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)