0
\$\begingroup\$

This is an experiment to see what's involved in adding new functional capability to the Common Lisp baseline. In this case, it's adding a sequence function to select elements from a sequence satisfying a predicate. I don't regard such baseline functions as simple utilities, because they seem more foundational, better optimized, and better at handling all corner cases.

The function select-if below is patterned after the standard -if sequence functions--namely, remove-if, delete-if, substitute-if, find-if, position-if, count-if (and their -if-not counterparts). If there's a way to combine these functions to easily select items from an arbitrary sequence without inventing a new function, I don't see it (although loop does cover some cases). But in any event select-if seems like a good test case.

(defun select-if (predicate sequence &key from-end (start 0) end
                   count (key #'identity))
  "Return elements from a sequence satisfying a predicate."
  (let* ((tally 0)
         (max-tally (or count most-positive-fixnum))
         (subsequence (if from-end
                        (nreverse (subseq sequence start end))
                        (subseq sequence start end)))
         (marker (gensym))
         (items (delete marker
                  (map 'list
                    (lambda (elem)
                      (cond ((and (< tally max-tally)
                                  (funcall predicate (funcall key elem)))
                               (incf tally)
                               elem)
                            (t marker)))
                    subsequence))))
    (declare (fixnum tally max-tally))
    (etypecase sequence
      (list items)
      (bit-vector (coerce items 'bit-vector))
      (string (format nil "~{~A~}" items))
      (vector (coerce items 'vector)))))

I'm particularly interested in whether there are better ways to do sequence selection, better optimization, and corner cases. Thanks for your time.

\$\endgroup\$
5
  • \$\begingroup\$ “If there's a way to combine these functions to easily select items from an arbitrary sequence...” it seems to me that your function has the same semantics as remove-if-not. So a good starting point could be looking at the definition of such a function in your Common Lisp environment of choice (in emacs-slime, after the name of the function press Meta-.) \$\endgroup\$
    – Renzo
    Apr 13 at 7:11
  • \$\begingroup\$ To me the semantics seem subtly different. For example, (select-if #'evenp '(0 1 2 3 4 5) :count 2) => (0 2). How would you write the equivalent remove-if-not? \$\endgroup\$
    – davypough
    Apr 14 at 20:42
  • \$\begingroup\$ Ops, you are right, when there is a :count parameter the results are different. \$\endgroup\$
    – Renzo
    Apr 15 at 7:46
  • 1
    \$\begingroup\$ Note that at the end if from-end is true then the result must be reversed. \$\endgroup\$
    – Renzo
    Apr 15 at 10:16
  • \$\begingroup\$ @Renzo Yes, you're right. Thanks. My (select-if #'evenp '(0 1 2 3 4 5) :count 2 :from-end t) => (4 2), when the result should be (2 4), to follow the hyperspec for remove-if-not. \$\endgroup\$
    – davypough
    Apr 15 at 15:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.