4

私はやってみたいです

(filter-list-into-two-parts #'evenp '(1 2 3 4 5))
; => ((2 4) (1 3 5))

ここで、述語が true と評価されるかどうかに応じて、リストは 2 つのサブリストに分割されます。このような関数を定義するのは簡単です:

(defun filter-list-into-two-parts (predicate list)
  (list (remove-if-not predicate list) (remove-if predicate list)))

しかし、これを行うことができるLispの組み込み関数があるかどうか、またはこの関数を書くためのより良い方法があるかどうかを知りたいですか?

4

4 に答える 4

7

リストを2回走査し、各リスト要素の述語を2回呼び出すため、ビルトインはなく、バージョンは最適ではないと思います。

(defun filter-list-into-two-parts (predicate list)
  (loop for x in list
    if (funcall predicate x) collect x into yes
    else collect x into no
    finally (return (values yes no))))

リストの代わりに 2 つの値を返します。これはより慣用的です (リストを解析するために使用する代わりに、返された複数の値multiple-value-bindを抽出yesしてから使用するため、conses が少なくなり、高速になります)。nodestructuring-bind

より一般的なバージョンは

(defun split-list (key list &key (test 'eql))
  (let ((ht (make-hash-table :test test)))
    (dolist (x list ht)
      (push x (gethash (funcall key x) ht '())))))
(split-list (lambda (x) (mod x 3)) (loop for i from 0 to 9 collect i))
==> #S(HASH-TABLE :TEST FASTHASH-EQL (2 . (8 5 2)) (1 . (7 4 1)) (0 . (9 6 3 0)))
于 2013-08-08T02:34:37.810 に答える
7

使用REDUCE:

(reduce (lambda (a b)
          (if (evenp a)
              (push a (first b))
            (push a (second b)))
          b)
        '(1 2 3 4 5)
        :initial-value (list nil nil)
        :from-end t)
于 2013-08-08T07:34:38.807 に答える
2

には、あなたが求めることを正確にdash.el行う関数があります:-separate

(-separate 'evenp '(1 2 3 4)) ; => '((2 4) (1 3))

を使用する場合は、投稿の残りの部分を無視できます-separate。Haskell のパーティション関数をElispに実装する必要がありました。Elisp は多くの点で Common Lisp に似ている1ため、この回答は両方の言語のコーダーに役立ちます。私のコードは、Python の同様の実装に触発されました

(defun partition-push (p xs)
  (let (trues falses) ; initialized to nil, nil = '()
    (mapc (lambda (x) ; like mapcar but for side-effects only
            (if (funcall p x)
                (push x trues)
              (push x falses)))
          xs)
    (list (reverse trues) (reverse falses))))

(defun partition-append (p xs)
  (reduce (lambda (r x)
            (if (funcall p x)
                (list (append (car r) (list x))
                      (cadr r))
              (list (car r)
                    (append (cadr r) (list x)))))
          xs
          :initial-value '(() ()) ; (list nil nil)
          ))

(defun partition-reduce-reverse (p xs)
  (mapcar #'reverse ; reverse both lists
          (reduce (lambda (r x)
                    (if (funcall p x)
                        (list (cons x (car r))
                              (cadr r))
                      (list (car r)
                            (cons x (cadr r)))))
                  xs
                  :initial-value '(() ())
                  )))

pushリストする要素を先頭に追加する破壊的な関数です。add-to-list同じ要素を一度しか追加しないため、Elisp の は使用しませんでした。結果を蓄積しないmapcマップ関数2です。Elisp は、Common Lisp と同様に、関数と変数に対して別々の名前空間を持っているため3funcall 、パラメーターとして受け取った関数を呼び出すために使用する必要があります。は、キーワードを受け入れるreduce高次関数4:initial-valueであり、さまざまな使い方が可能です。append可変量のリストを連結します。

このコードでは、普及している「プッシュ アンドリバース」イディオムpartition-pushを使用する命令的な Common Lisp が使用されています。リストに 1 回追加すると、リストはコンス セルとして実装されるため、項目を追加すると. 最後に追加することを示しています。私は関数型プログラミングのファンなので、副作用のないバージョンをin で書きました。O(1)O(n)O(n)nO(n²)partition-appendreducepartition-reduce-reverse

Emacs にはプロファイリング ツールがあります。これら3つの関数に対して実行します。返されるリストの最初の要素は、合計秒数です。ご覧のとおり、リストへの追加は非常に遅く動作しますが、機能的なバリアントは最も高速です。

ELISP> (benchmark-run 100 (-separate #'evenp (number-sequence 0 1000)))
(0.043594004 0 0.0)
ELISP> (benchmark-run 100 (partition-push #'evenp (number-sequence 0 1000)))
(0.468053176 7 0.2956386049999793)
ELISP> (benchmark-run 100 (partition-append #'evenp (number-sequence 0 1000)))
(7.412973128 162 6.853687342999947)
ELISP> (benchmark-run 100 (partition-reduce-reverse #'evenp (number-sequence 0 1000)))
(0.217411618 3 0.12750035599998455)

参考文献

  1. Common Lisp と Emacs Lisp の違い
  2. 高階関数のマッピング
  3. 機能細胞と価値細胞の分離の技術的課題
  4. 高階関数の折り畳み
于 2014-03-14T05:43:44.323 に答える