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?

Leshia

google.com/search?q=sheep+trick+from+the+pitmanual – Frenzy

maclisp.info/pitmanual/funnies.html#sheep_trick – Frenzy

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

Trattoria

Ahh, thanks, never knew you could return two values! What's the advantage compared to returning a list? Seems like it would be a bit more of a hassle to extract the multiple values. – Leshia

Multiple values are useful when there is a primary return value and additional values that would be discarded in most cases. The division related math functions all work that way, returning the quotient as the primary and the remainder as secondary value. When it is hard to determine which of the return values is "primary", I find it preferable to return the values in a list or in a structure that is self describing. Multiple values need to be handled at the call site with clunky mechanisms, whereas a list can easily be passed around. – Carolinecarolingian

Pattern matching reduces the need to return multiple values since you can just destructure pairs nicely instead. – Gastrostomy

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)

Chauvin

Answer 3

In dash.el there is a function -separate that does exactly what you ask:

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

You can ignore the rest of the post if you use -separate. I had to implement Haskell's partition function in Elisp. Elisp is similar¹ in many respects to Common Lisp, so this answer will be useful for coders of both languages. My code was inspired by similar implementations for 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 is a destructive function that prepends an element to list. I didn't use Elisp's add-to-list, because it only adds the same element once. mapc is a map function² that doesn't accumulate results. As Elisp, like Common Lisp, has separate namespaces for functions and variables³, you have to use funcall to call a function received as a parameter. reduce is a higher-order function⁴ that accepts :initial-value keyword, which allows for versatile usage. append concatenates variable amount of lists.

In the code partition-push is imperative Common Lisp that uses a widespread "push and reverse" idiom, you first generate lists by prepending to the list in O(1) and reversing in O(n). Appending once to a list would be O(n) due to lists implemented as cons cells, so appending n items would be O(n²). partition-append illustrates adding to the end. As I'm a functional programming fan, I wrote the no side-effects version with reduce in partition-reduce-reverse.

Emacs has a profiling tool. I run it against these 3 functions. The first element in a list returned is the total amount of seconds. As you can see, appending to list works extremely slow, while the functional variant is the quickest.

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)

References

1. Differences between Common Lisp and Emacs Lisp
2. Map higher-order function
3. Technical Issues of Separation in Function Cells and Value Cells
4. Fold higher-order function

Kirbee

Answer 4

I don't think that there is a partition function in the common lisp standard, but there are libraries that provide such an utility (with documentation and source).

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

Telefilm