Iterating over FSet Collections (Modern Common Lisp with FSet)

Next: Generic Function convert, Previous: FSet API Reference, Up: Modern Common Lisp with FSet [Contents][Index]

7 Iterating over FSet Collections ¶

FSet provides a plethora of ways to iterate over a collection once you have created it:

procedural macros (do-*)
the higher-order operators image, filter, and reduce
iterators, both stateful and functional
the at-index operation
the versatile GMap macro (described below)
the popular Iterate macro
there’s even a third-party library, CL-Transducers, with FSet support

Just to give a taste of these, here’s an example. Suppose nums holds a seq of numbers, and you want to compute their sum. Here are the ways you could do it:

;;; procedurally
(let ((sum 0))
  (do-seq (n nums :value sum)
    (incf sum n)))
;;; using ‘reduce’
(reduce #'+ nums)
;;; using a stateful iterator
(do ((it (iterator nums))
     (sum 0 (+ sum (funcall it ':get))))
    ((funcall it ':done?) sum))
;;; using a functional iterator
(do ((it (fun-iterator nums) (funcall it ':rest))
     (sum 0 (+ sum (funcall it ':first))))
    ((funcall it ':empty?) sum))
;;; using ‘at-index’
(let ((sum 0))
  (dotimes (i (size nums) sum)
    (incf sum (at-index nums i))))
;;; using GMap
(gmap (:result sum) :id (:arg seq nums))
;;; using Iterate
(iter (for n in-seq nums) (sum n))
;;; using CL-Transducers
(transduce #'pass #'+ nums)

I wouldn’t recommend picking a favorite based just on this very simple example, but I can make a few general comments:

If all you want is a reduction, as in this example, it’s hard to beat reduce for elegance.
Using an iterator manually is rather verbose; I don’t recommend it unless you really need it.
Iterate, though it reads somewhat procedurally, is concise and clear.
GMap and CL-Transducers have a similar flavor, at least in this simple case.

Every collection has an iteration order that reflects how the elements or pairs are stored internally. For the CHAMP collections, this order is arbitrary; it’s based on the hash values of the elements or keys, so while it is actually deterministic — two collections with the same elements and hash function will have the same iteration order — it will appear random at first glance. For the WB collections, it’s determined by their comparison function. The default comparison function, compare, imposes an ordering that’s designed more for performance than for usefulness to clients, but you can override it. Also, there are “replay” collections that keep track of the order in which elements or keys were added, and use that order for iteration. In any case, all of the different ways to iterate over a given collection will use the same ordering.

If performance is a concern, the procedural macros are the fastest way, but they can’t always be used (for example, you can’t use two instances of them to iterate over two collections in parallel). The stateful iterators are the next fastest; the functional iterators are third. All of these take amortized constant time per element. GMap uses the procedural iterators when possible, else the stateful iterators, so for the cases that fit naturally into its structure, you won’t be able to improve on it by writing the iteration some other way. Iterate uses the stateful iterators.