London Clojure Dojo, December 2011
Apologies for lack of November post; I’ve been somewhat snowed under recently. Normal service now resuming…
December’s Clojure dojo focused on difficult problems from 4clojure. I had dabbled with 4clojure before on some of the easier problems, but I honestly hadn’t anticipated just how difficult the hard problems can get!
Our team decided to go in gently, going for medium-difficulty problems rather than hard problems. This turned out to be one of our better ideas of the evening, since we only managed to complete one and a half medium problems in the time available!
Juxtaposition
The first problem we tackled was
Juxtaposition, in which you have
to reimplement the juxt function. Our team took an approach where we
tried to develop solutions from first principles, rather than looking
up (source juxt), so I think it might be enlightening to compare our
solutions with the clojure.core model answers. First, our solution:
(defn juxt [& fns] (fn [& args] (vec (map #(apply % args) fns))))
And the output of (source juxt) produces something like this:
(defn juxt [& fs] (fn [& args] (reduce #(conj %1 (apply %2 args)) [] fs)))
…except that the original source has special cases for small numbers of arguments.
It’s interesting the difference of approaches here. We both use the
form (apply % args) to apply the variable number of arguments to
each function in turn; however, we use map to do this, producing a
sequence, which we then must traverse in order to convert to a vector.
The clojure.core version, by contrast, starts with an empty vector
[], and conjes each further result into the vector; in doing so,
it avoids traversing the list twice.
Reductions
The second problem we attempted was Reductions. Here’s our attempt:
(defn my-red ([f coll] (if (seq coll) (cons (first coll) (map #(f % (first coll)) (my-red f (rest (seq coll))))) [])) ([f init coll] (my-red f (cons init coll))))
It performs well enough for bounded-length sequences:
(my-red + [1 2 3 4 5]) ;=> (1 3 6 10 15)
But it fails when it comes to infinite lazy sequences:
(take 5 (my-red + (range))) ;=> StackOverflowError
We were very confused on the night as to why this should fail. Isn’t
map lazy by default? Why, then, do we get a stack overflow?
The problem, which I have only found out today, 4 days after the
event, is that map is a function, and therefore its arguments are
evaluated before map itself is. Therefore, every call to my-red
necessarily makes a recursive call, and thus exhausts the stack. The
solution is to add a lazy-seq to the recursive call:
(defn my-red ([f coll] (if (seq coll) (cons (first coll) (map #(f % (first coll)) (lazy-seq (my-red f (rest (seq coll)))))) [])) ([f init coll] (my-red f (cons init coll))))
And thus, the previous example now works fine:
(take 5 (my-red + (range))) ;=> (0 1 3 6 10)
It still doesn’t pass all of the 4clojure unit tests, though. Work for another time, perhaps.
The clojure.core/reductions source looks like this:
(defn reductions "Returns a lazy seq of the intermediate values of the reduction (as per reduce) of coll by f, starting with init." {:added "1.2"} ([f coll] (lazy-seq (if-let [s (seq coll)] (reductions f (first s) (rest s)) (list (f))))) ([f init coll] (cons init (lazy-seq (when-let [s (seq coll)] (reductions f (f init (first s)) (rest s)))))))
It’s a very similar approach to the problem, with some important differences:
- It actually works (!)
- It uses
if-letandwhen-letwith theseqfunction, relying on the behaviour that for empty sequences,seqreturns nil, but also binding the returned seq simultaneously. - It treats the
[f init coll]version as the primitive form and expresses[f coll]in terms of[f init coll]. We do it the other way, purely because we implemented[f coll]first. It’s ugly, though, particularly in cases whereinitis not the same type as members ofcoll. - It has special case handling for the
(reductions f [])case — where an empty sequence is provided, it returns(list (f)). - I believe our use of
mapmakes our solution quadratic rather than linear in the length of the input sequence, because the item in the nth position must be transformed by (n-1) fns and we don’t reuse the intermediate results like the clojure.core version does.
Summary
This has made me want to go back and give 4clojure a closer look. I had tried the first few problems, which seemed trivially easy, but now that I’ve seen that even the “Medium” problems present a significant challenge and raise all sorts of issues around laziness, algorithmic complexity, and efficiency, I can see I’ve a lot to learn from 4clojure.
The London clojure dojo happens on the last Tuesday of every month. During the dojo, we split into groups of four or five around a single computer, and each person takes a turn at the keyboard. This ensures that even if you have zero clojure experience, you will get the opportunity to write some code at the event.
Entry to the dojo is free, but advance booking is required. Listen for announcements on the London clojurians mailing list.
