CODEWITHSUNDEEP
filterlispcommon-lisp
wrongusername
wrongusername

Reputation: 18918

Filter a list into two parts by a predicate

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?

Upvotes: 5

Views: 2151

Answers (4)

sds
sds

Reputation: 60044

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

Upvotes: 8

Mirzhan Irkegulov
Mirzhan Irkegulov

Reputation: 18065

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 similar1 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 function2 that doesn't accumulate results. As Elisp, like Common Lisp, has separate namespaces for functions and variables3, you have to use funcall to call a function received as a parameter. reduce is a higher-order function4 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

Upvotes: 2

stackman
stackman

Reputation: 360

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

Upvotes: 1

Rainer Joswig
Rainer Joswig

Reputation: 139311

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)

Upvotes: 8

Related Questions