4

我想要做

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

根据谓词的计算结果是否为真，一个列表被分成两个子列表。定义这样一个函数很容易：

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

但我想知道 Lisp 中是否有一个内置函数可以做到这一点，或者可能是编写这个函数的更好方法？

4

4 回答 4

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 回答
7

我不认为有一个内置的，你的版本是次优的，因为它遍历列表两次并调用每个列表元素上的谓词两次。

(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))))

我返回两个值而不是其列表；这更惯用（您将使用从返回的多个值multiple-value-bind中提取yes和提取，而不是使用来解析列表，它占用更少且更快）。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 回答
2

其中dash.el有一个功能-separate可以完全按照您的要求进行：

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

如果您使用-separate. 我必须在Elisp中实现 Haskell 的分区函数。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是一个破坏性功能，它预先列出一个元素。我没有使用 Elisp 的add-to-list，因为它只添加了一次相同的元素。是一个不累积结果mapc的映射函数2 。由于 Elisp 与 Common Lisp 一样，为函数和变量3提供了单独的命名空间，因此您必须使用它funcall来调用作为参数接收的函数。是一个接受关键字reduce的高阶函数4:initial-value，它允许多种用途。append连接可变数量的列表。

在代码partition-push中是命令式的 Common Lisp，它使用广泛的“推倒”O(1)习语，您首先通过在列表前添加 in和反转 in来生成列表O(n)。向列表追加一次将是O(n)由于列表实现为cons 单元格，因此追加n项目将是O(n²). partition-append说明添加到末尾。由于我是函数式编程reduce爱好者，因此我使用in编写了无副作用版本partition-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 回答
1

我认为通用 lisp 标准中没有分区函数，但有些库提供了这样的实用程序（带有文档和源代码）。

CL-USER> (ql:quickload :arnesi)
CL-USER> (arnesi:partition '(1 2 3 4 5) 'evenp 'oddp)
((2 4) (1 3 5))
CL-USER> (arnesi:partition '(1 2 b "c") 'numberp 'symbolp 'stringp)
((1 2) (B) ("c"))
于 2013-08-10T16:14:19.313 回答