Filter a list into two parts by a predicate

Question

I want to do

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

where a list is split into two sub-lists depending on whether a predicate evaluates to true. It is easy to define such a function:

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

but I would like to know if there is a built-in function in Lisp that can do this, or perhaps a better way of writing this function?

Answer 1

I don't think there is a built-in and your version is sub-optimal because it traverses the list twice and calls the predicate on each list element twice.

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

I return two values instead of the list thereof; this is more idiomatic (you will be using multiple-value-bind to extract yes and no from the multiple values returned, instead of using destructuring-bind to parse the list, it conses less and is faster, see also values function in Common Lisp).

A more general version would be

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

Answer 2

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