opening it up with Common Lisp

Favorite weblogs

Lisp Related

Bill Clementson

Finding Lisp

Lemonodor

Lispmeister.com

Planet Lisp

Politics

Orcinus

Talking Points Memo

This Modern World

Working for Change

Other home

Polliblog

Recent Readings

Book review: Darwinia
Reviewed: Friday, August 11, 2006

Summer reading: Spin
Reviewed: Saturday, August 5, 2006

Runner
Reviewed: Tuesday, July 18, 2006

the Omnivoire's Delimma
Reviewed: Wednesday, July 12, 2006

the Golem's Eye
Reviewed: Wednesday, May 31, 2006





tinderbox
 width=

Iteration and Collecting
Friday, June 18, 2004

Lisp provides multiple mechanisms to iterate over its built in collections (`mapcar`, `mapc`, `dolist`, `loop`, `maphash`, `with-hash-table-iterator` and so forth). Some of these operate on the underlying data -- pure iteration; others collect and return the results -- iteration for collection. Note that you can write an iteration function if you have a collection one:

(defun iterate-using (collection-fn iteration-fn dataset)
  (dolist (item (funcall collection-fn dataset))
    (funcall iteration-fn item)))

This isn't a good idea, however, because it always conses up a new list just to iterate over it and throw it away. A better plan is to write iteration functions for your data structures and then write the collection in terms of them. In fact, if you plan ahead and structure all your iteration functions so that the function argument passed in is always last, then you can use a single function for all of your collecting:

(defun collect-using (map-fn filter &rest args)
  "Collects stuff by applying the map-fn to the arguments.
Assumes that the map-fn signature has the function to be 
applied as its last argument."
  (declare (dynamic-extent filter args))
  (let ((result nil))
    (apply map-fn 
           (append 
            args
            (list 
              (lambda (thing)
                (when (or (not filter) 
                          (funcall filter thing))
                  (push thing result))))))
    (nreverse result)))

You can use the same trick for other common dataset tasks like counting:

(defun count-using (map-fn filter &rest args)
  "Counts stuff by applying the map-fn to the arguments. 
Assumes that the map-fn signature has the function to be
applied as its last argument."
  (let ((result 0))
    (apply map-fn 
           (append 
            args 
            (list (lambda (thing)
                    (when (or (not filter)
                              (funcall filter thing))
                      (incf result))))))
    
    (values result)))

I've added a filter here because that's a pretty common need.

This sort of generic, I-don't-care-about-the-types, first class functions stuff is what makes dynamic languages like Lisp so beautiful.


|

Home | About | Quotes | Recent | Archives

Copyright -- Gary Warren King, 2004 - 2006