I’ve been slowly but surely working through the problems on The excellent 4clojure website. If you’re doing the same, I should warn you that there are spoilers below…

Some of my difficulties are learning a strange API, some are adapting to a functional way of thinking.

An essential part of the learning process is, once you’ve completed a problem, reviewing the other solutions. I’ve selected a few members of the clojure/core team as exemplars to compare myself against. I’m pretty happy if I’m within about an order of magnitude for length of solution compared to the top ranked guys.

So far, when a problem comes up, I can often arrive at a working algorithm, but struggle to express it in a sensible way in clojure. Today’s problem, Pascal’s Trapezoid is such an example. I realised quite quickly that because clojure allows you to map over multiple collections at the same time, I can add the input vector to a copy offset by 1 and i’ll be very close to the solution.

Let’s look at producing one value first. The next value for an input of [2 3 2] should be [2 5 5 2]

1
2
3
4
5

(defn pascals-trapezoid [v]
               (map + v (rest v)))

;=> (pascals-trapezoid [2 3 2])
(5 5)

so far so good, we have the middle values. Lets add the first and last values in…

1
2
3
4
5

(defn pascals-trapezoid [v]
                     (concat [(first v)] (map + v (rest v)) [(last v)]))

;=> (pascals-trapezoid [2 3 2])
(2 5 5 2)

Hmmm, seems to work, code looks a bit messy, maybe we can use destructuring on the arguments to improve things…

1
2
3
4

(defn pascals-trapezoid [[f & rest :as v]]
                     (concat [f] (map + v rest) [(last v)]))
;=> (pascals-trapezoid [2 3 2])
(2 5 5 2)

Hmmm, code doesn’t look any better. Messy code is a code smell.

Let’s make this thing work as a lazy sequence and see what effect that has.

1
2
3
4
5
6

(defn pascals-trapezoid [v]
        (cons v (lazy-seq (pascals-trapezoid
                          (concat [(first v)] (map + v (rest v))
                          [(last v)])))))
;=> (take 3 (pascals-trapezoid [2 3 2]))
([2 3 2] (2 5 5 2) (2 7 10 7 2))

Well, it works but it looks an absolute mess…

Let’s go back to first principles. We realised that basically we want to add the sequence to an offset by one copy. The problem is the first and last digits. How can we handle that?

Well if we could somehow include an unmodified first and last digit that should do it. Of course addition of 0 to the front of one collection and the end of the other fits the bill, so for an input of [ 2 3 2 ] we want to map + over [ 0 2 3 2 ] and [ 2 3 2 0 ]

So that might look something like this:

1
2
3
4
5

(defn pascals-trapezoid [v]
   (cons v (lazy-seq
       (let [s1 (concat [0] v)
             s2 (concat v [0])]
         (pascals-trapezoid  (map + s1 s2))))))

So we have a working version, but the meaning of the code is not immediately evident.

There must be a better way!

Of course it turns out that there is…

1
2
3

(defn pascals-trapezoid [v]
   (cons v (lazy-seq
            (pascals-trapezoid (map + `(0 ~@v) `(~@v 0))))))

What’s going on here? Well the ~@ is the unquote-splice macro, ~@v means take the elements of sequence v and splice them in at this point. so if v is [ 2 3 2 ] then `(0 ~@v) -> (0 2 3 2)

Compare to the bindings of s1 and s2 in the previous verion and you’ll see the similarities.

So are we there yet? Not quite. It turns out that there’s a function in clojure/core called iterate which generates a lazy sequence of values by passing the previous result back into the supplied function. This gives a final version that looks like this:

1
2

(defn pascals-trapezoid [v]
  (iterate #(map + `(0 ~@%) `(~@% 0)) v))

Once you understand what’s going on with the unquote splicing, this code looks very clear indeed. Checking with the solutions on 4clojure.com and we see that we’re there!

This ability to splice like this is because of the Code is Data nature of clojure (and other LiSPs). Very powerful….