When writing tests for an application which involves a database, one of the first things you need to do is ensure sure that all of database integration tests start from a known state. Now, understandably, there are already libraries that can do this for us, such as theÂ Database CleanerÂ gem. However, when we started the project, I didn’t really see the value in importing a ~1000 line library when about 10 or so lines of Ruby would do the trick, and result in a helper which was quickly comprehensible without having to hunt down the defining Gem.
Preferences class provides a common place for all parts of a Squeak Smalltalk image to register their switches: Which update stream do we want to follow? What colour do we want our Browsers? Do we allow assignments to block parameters? Do we allow underscores in selector names? Preferences range from low level things that affect the language’s grammar, all the way to trivial things.
In the old days we would create a preference by adding a getter/setter pair that would expose a key-value pair in a dictionary. That sounds great. It’s certainly simple. It’s only when a system evolves organically over decades that we realise the trap: such a dictionary is a giant chain, coupling together otherwise independent packages that simply wish to store something configurable. Even though we can store the preference accessors within each package, the packages still share the backing dictionary. It’s a recipe for trouble. Let’s see how we can untangle the chain.
When playing with a new bit of language, it can be helpful to restrict the problem space to an old, well understood algorithm. For me at least, learning one thing at a time is easier! For this post, It’ll be prime sieves, and I’ll be exploring clojure reducers.
A quick recap, the sieve of eratosthenes is a not-maximally-non-optimal way of finding primes. It’s usually expressed as follows:
To find primes below n:
generate a list of n integers greater than 1
while the list is not empty:
take the head of the list and:
add it to the output
remove all numbers evenly divisible by it from the list
In clojure, something like:
([n] (sieve  (range 2 n)))
(if-let [prime (first xs)]
(recur (conj primes prime) (remove #(zero? (mod % prime)) xs))
;= [2 3 5 7]
Which is fine, but I’d like it lazy so I only pay for what I use, and I can use as much as I’m willing to pay for. Let’s look at lazy sequences. Luckily for us, there is an example of exactly this on the lazy-seq documentation, which we slightly modify like so:
(defn lazy-sieve [s]
(cons (first s)
(lazy-seq (lazy-sieve (remove #(zero? (mod % (first s))) (rest s))))))
(defn primes 
(lazy-seq (lazy-sieve (iterate inc 2))))
(take 5 (primes))
;= (2 3 5 7)
So now we have a nice generic source of primes that grows only as we take more. But is there another way?
A few months ago Rich Hickey introduced reducers. By turning the concept of ‘reducing’ inside out the new framework allows a parallel reduce (fold) in some circumstances. Which doesn’t apply here. But let’s see if we can build a different form of sieve using the new framework. First a quick overview (cribbing from the original blog post):
Collections are now ‘reducible’, in that they implement a reduce protocol. Filter, map, etc are implemented as functions that can be applied by a reducible to itself to return another reducible, but lazily, and possibly in parallel. So in the example below we have a reducible (a vector), that maps inc to itself to return a reducible that is then wrapped with a filter on even? which returns a further reducible, that reduce then collects with +.
(require '[clojure.core.reducers :as r])
We’ll be referring to r here and there – just remember it’s the clojure.core.reducers namespace
(reduce + (r/filter even? (r/map inc [1 1 1 2])))
These are composable, so we can build ‘recipes’.
;;red is a reducer awaiting a collection
(def red (comp (r/filter even?) (r/map inc)))
(reduce + (red [1 1 1 2]))
into uses reduce internally, so we can use it to build collections instead of reducing:
(into  (r/filter even? (r/map inc [1 1 1 2])))
;= [2 2 2]
So here’s the core of ‘reducer’, which “Given a reducible collection, and a transformation function xf, returns a reducible collection, where any supplied reducing fn will be transformed by xf. xf is a function of reducing fn to reducing fn.”
(coll-reduce [_ f1 init]
(clojure.core.protocols/coll-reduce coll (xf f1) init)))))
And we can then use that to implement mapping as so:
(defn mapping [f]
(fn [result input]
(f1 result (f input)))))
(defn rmap [f coll]
(reducer coll (mapping f)))
(reduce + 0 (rmap inc [1 2 3 4]))
Fine. So what about sieves? One thought is we could build up a list of composed filters, built as new primes are found (see the lazy-seq example above). But there’s no obvious place to do the building, as applying the reducing functions is left to the reducible implementation. Another possibility is to introduce a new type of reducing function, the ‘progressive-filter’, which keeps track of past finds and can filter against them.
(defn prog-filter [f]
(let [flt (atom )]
(fn [result input]
(if (not-any? #(f input %) @flt)
(swap! flt conj input)
(f1 result input))
(defn progressive-filter [f coll]
(reducer coll (prog-filter f)))
And we then reduce with a filtering function that is a function of the current candidate and one of the list of found primes (see the #(f input %) bit above)
(into  (progressive-filter #(zero? (mod %1 %2)) (range 2 10))
;= [2 3 5 7]
It’s nicely lazy, so we can use iterate to generate integers, and take only a few (r/take, as it’s operating on a reducer):
(into  (r/take 5 (progressive-filter #(zero? (mod %1 %2)) (iterate inc 2))))
;= [2 3 5 7 11]
(def primes (progressive-filter #(zero? (mod %1 %2)) (iterate inc 2)))
(into  (r/take 5 primes))
;= [2 3 5 7 11]
You get the idea.
You are currently browsing the LShift Ltd. blog archives for July, 2013.