Seth's Picture

Picking the Right Data Structure

Sat 09 March 2013
By Seth

Recently I’ve gotten serious about learning Clojure. One of the things that attracted me to the language was Rich Hichey’s talk “Simple Made Easy”. In it he makes the case that the tools we use to write our software are much more complex than they need to be.

Since watching that talk I’ve been trying to figure out how these ideas actually apply to real code. The talk is about ideas more than it is about specific code examples or techniques but it’s useful to look at the definition of simple: the word “simple” comes from the word “simplex” which means “one braid” or “one twist”. So the idea is to find places where two (or more) things have been combined together when they could be separate.

Whenever I try a new language I end up implementing John Conway’s Game of Life. It’s pretty easy to write the code for it and it’s one of the first programs that I wrote in when I was learning how to program (QBasic using asterisks to represent the live cells). At the time it was a huge struggle to write so it’s always fun to see how it constantly seems to get easier.

For my first cut at Life in Clojure I didn’t want to get any ideas from people who had already done it. After all, the point is just to start tinkering with the language. I did barrow most of the rendering code from Rich’s ants demo because I’m not familiar with Java Swing and don't really plan on learning it.

I went with an almost direct translation a naive approach in an imperative language and used a vector of vectors which I treated like a 2d array:

(def board [[0 1 0] [0 1 0] [0 1 0]])

Here's my code to produce the next generation of a board:

(defn cell-next
  "compute the generation of the given cell"
  [board x y]
  (let [n (neighbor-count board x y)]
        (cond
          (= n 3) 1 ;birth
          (and (= n 2) (= 1 (cell board x y))) 1 ;survival
          :else 0
          )))

(defn step
  "compute the next generation for the board"
  [board]
  (vec (for [y (range dim)]
        (let [row (board y)]
          (vec (for [x (range dim)]
                         (cell-next board x y)))))))

The function cell returns the state of a cell at a given position in the grid and the function neighbor-count returns the numbers of live neighbors of a cell.

That works but I doubt anyone would call it idiomatic Clojure plus the grid is a fixed size and it always uses up the maximum amount of space based on the grid size.

At this point I searched for existing ideas. Christophe Grand wrote a Life example on his blog. His solution takes a set of pairs instead of a vector of vectors like mine. Each pair represents the x-y coordinates of a live cell:

(def board #{[1 0] [1 1] [1 2]}) ;Christophe's board

Here's the complete code for calculating the next generation:

(defn neighbours [[x y]]
  (for [dx [-1 0 1] dy (if (zero? dx) [-1 1] [-1 0 1])]
        [(+ dx x) (+ dy y)]))

(defn step [cells]
  (set (for [[loc n] (frequencies (mapcat neighbours cells))
                         :when (or (= n 3) (and (= n 2) (cells loc)))]
                 loc)))

That code is shorter but that's actually not very important to me. All else being equal, shorter code is better but when is all else actually equal? Brevity of code is a programmer focused metric (see Ask the Right Question). The more interesting thing to me is that now more of the code is actually working on solving the problem as opposed to code that's wrangling data into the right shape. The reason for this that the data structure Christophe has chosen is simple. It's simple in the sense that things aren't combined. The position is no longer tied to the meaning of the data like it was in my vector of vectors. This type of logic would apply equally well with other types of cellular automata (in fact I think Christophe does extend this example in his book).

Of course this is a trivial example but it's easy to extrapolate from this to bigger examples. Very often there's a core set of data structures that our programs operate on and if those structures are complex then that complexity infects all of the code that touches it.

Interested in learning more about Clojure?

Sign up for occasional emails related to learning Clojure

comments powered by Disqus