From Newsgroup: comp.lang.lisp

Tamas Papp wrote:

1. What would be the best name for this function? Is it already in a (Quicklisp) library? (could not find it, don't want to reinvent the wheel).

--8<---------------cut here---------------start------------->8---
(defun separate-sequence (sequence predicate)
"Return two sequences of the same type, containing elements that
do and do not satisfy PREDICATE. Ordering of elements is preserved."
(values (remove-if (complement predicate) sequence)
(remove-if predicate sequence)))

;; Example
(separate-sequence '(0 1 2 3) #'oddp) ; => (1 3), (0 2) --8<---------------cut here---------------end--------------->8---

2. Any suggestions for a better implementation (one that traverses the sequence only once)? I came up with

--8<---------------cut here---------------start------------->8---
(defun separate-sequence (sequence predicate)
"Return two sequences of the same type, containing elements that do and do not satisfy PREDICATE. Ordering of elements is preserved."
(let (yes
no
(type (typecase sequence
(list 'list)
(vector `(simple-array ,(array-element-type sequence) '*))
(t (return-from separate-sequence
;; generic sequence, let built-ins handle it
(values (remove-if (complement predicate) sequence)
(remove-if predicate sequence)))))))
(map nil (lambda (element)
(if (funcall predicate element)
(push element yes)
(push element no)))
sequence)
(values (coerce (nreverse yes) type)
(coerce (nreverse no) type))))

Gauche Scheme

gosh> (partition even? (iota 20))
(0 2 4 6 8 10 12 14 16 18)
(1 3 5 7 9 11 13 15 17 19)
--- Synchronet 3.21d-Linux NewsLink 1.2