Philip Potter

London Clojure Dojo, December 2011

Posted on 17 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-let and when-let with the seq function, relying on the behaviour that for empty sequences, seq returns 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 where init is not the same type as members of coll.
  • 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 map makes 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.