リストを反復処理するときに現在の要素を削除できないのはなぜですか？

Question

私はリストを反復し、要素でアクションを実行し、いくつかの基準に基づいて、アクティブな要素を取り除きたいと思います。しかし、以下の関数を使用すると、無限ループに終わります。

(defun foo (list action test) 
    (do ((elt (car list) (car list))) 
     ((null list)) 
    (funcall action elt) 
    (when (funcall test elt) 
     (delete elt list)))) 

(setq list '(1 2 3 4)) 
(foo list #'pprint #'oddp) 
-> infinite loop 

それはそれ自体を指していますか？最後にeltは(car list)です。

これは正しい評価ですか？そして、私はこれをいかに効率的に解決できますか？あなたは何を反復処理されていないので、

Answer 1

実際には、リストの反復処理中にリストの状態を変更できます。あなただけのdeleteに加えてrplacdを使用する必要があり、ない反復句ではなく、やる体内のリストに沿って進展を制御します：

(defun nfoo (lst action test) 
    (do* ((list (cons 1 lst)) 
     (elt (cadr list) (cadr list))) 
     ((null (cdr list)) 
     (if (funcall test (car lst)) (cdr lst) lst)) 
    (funcall action elt) 
    (if (funcall test elt) 
     (rplacd list (delete elt (cddr list))) 
     (setf list (cdr list))))) 

したくない場合は、copy-listを経由して、それを呼び出す必要がありますそれは引数リストを破壊する。

あなたははテストに合格することなく、すべてのテストに合格したeltに等しい要素ではなく、すべてがそのようなあなたのリストから削除したい場合は、delete呼び出しが:testとしてtest機能を渡す必要があります引数。

（編集：）もはるかに簡単でわかりやすい、この（非破壊）版のように：

(defun foo (list action test) 
    (do* ((elt (car list) (car list))) 
     ((null list)) 
    (funcall action elt) 
    (if (funcall test elt) 
     (setf list (delete elt list)) 
     (setf list (cdr list))))) 

Answer 2

ループを使用すると、繰り返しactionを適用し、無限であるが、それは要素を変異させていない場合は、明らかにpprintがないようtest結果が否定的である場合、それは残りますリストを削除しようとしてもリストは空になりません。

DELETEは破壊的な機能です。 Common Lispの破壊操作では、はそれらの引数を破壊することができます。引数への参照を破棄し、戻り値のみを使用するはずです。操作が完了した後、引数の状態についての保証はありません。特に、実装が非破壊的な対応と同じように動作することが許可されているため、影響はないかもしれませんが、通常、シーケンスのコンポーネント部分は、予測が困難な方法で再アセンブリされます。あなたの例では、未定義の振る舞いを持つリテラルも破壊されているので、避けるべきです。

一般的に、Common Lispのリストは、不変で破壊的な操作として、何かを破壊しないと確信している場合にのみ使用すべきマイクロオプティマイゼーションとして扱うのが最善です。この問題のために、条件リストCOLLECTで結果リストをアセンブルするLOOPを使用してリストを反復することができます。 LOOP chapter of PCLを参照してください。

Answer 3

私はlispに少し新しいですので、おそらく私が欠けていますあなたの質問の何か。まだ、私はと思っています私はあなたが何を求めているのか理解しています、なぜあなたはこれのためにいくつかの既存の構造を使用していないのだろうか... ... remove-if-not（または私が後方に物事がある場合はremove-if）とmapcar ...

(mapcar #'pprint (remove-if-not #'oddp '(1 2 3 4)) 

上記プリント1と3（と(nil nil)を返しますが、おそらくあなたはそれを無視することができます...またはあなたが上記を行い、(values)で終わる関数定義を行うことができます）。 （もしあなたがevensを望むなら、remove-if-notをremove-ifに変更してください。）

これは教育的理由からこれをやっていない限り、その中で私はかなり可能であると認めます。 :)

P.S. Hyperspec info on remove-if, remove-if-not, etc.