Reversi in Clojure…functional

Reversi in Clojure w/ Three Alternative User Interfaces is the type of blog entries I enjoy the most – it inspired me to think about functional programming in Clojure and found it a great “platform” to work on my understanding of Clojure’s way to functional programming. I hope I didn’t mess it up and am on my way to functional programming nirvana.

The idea was to find all the places where mutation happens or may be incurred (due to a type/data structure used) and find their functional counterparts.

The very first finding was the if statement in the function opposite-piece. As I wrote in the blog entry Protocols more functional than if in Clojure?, I tend to believe that the if function resembles the imperative if statement so much that whenever I find it in a code, it encourages me to think about another approach.

What about this version of the opposite-piece function?

(defn opposite-piece-with-map [piece]
  "Change white to black and vice versa"
  (let [conversion-map {:w :b :b :w}]
    (conversion-map piece)))

To me it looks more functional.

The other piece of the code I found intriguing was the function initialize-board which uses a less functional data structure – a vector – not an immutable list – the truly functional data structure (which was the foundation for Lisp and later Clojure). I think a list (or a sequence in general) invites to a thinking in a functional way, with no way to mutate its content since it’s immutable by design (so is a vector in Clojure, but it may easily mislead an untrained reader coming from Java or another OOP language).

I consider a vector an imperative data structure and a sort of mutable list or vice versa – a list as an immutable vector (even though the distinction doesn’t exist in Clojure). I’ve seen lists used instead and whenever it happened it was a mental challenge for me. I enjoyed it and was keen on introducing it in the game.

So, from that moment on, I was using a list not a vector in initialize-board. And the fun began!

As a starter, let’s consider the following 3×3 board with 0′s.

(def board (repeat 9 0))

I wish I could have a picture of a board to accompany the snippets.

You may also use the function partition.

How could you change, say increase, the 0′s in the position you’d call (2,2) – the central 0? Let’s assume we start counting the rows and the columns from 1 onwards.

The pure function could look as follows:

(defn inc-at-v1 [board row col]
  (let [split-pos  (+ (* 3 (dec row)) col)
        f inc]
    (concat (take (dec split-pos) board)
            (list (f (nth board (dec split-pos))))
            (drop split-pos board))))

Let’s see how it works.

user=> (inc-at-v1 board 2 2)
(0 0 0 0 1 0 0 0 0)

It works! My very first take on refactoring of the game to a more functional version works well.

There’s a serious issue, though. We iterate over the sequence board three times – once when we calculate the elements for the left side of the output sequence, another to get at the value to increment and yet another for the right side. It’s certainly not very efficient.

The other solution was a recursion with a counter – a sort of functional for (not to be confused with the for function for list comprehension).

(defn inc-at-v2
  ([board row col]
    (let [split-pos  (dec (+ (* 3 (dec row)) col))
          split-fn (fn [idx e]
                     (cond (< idx split-pos) e
                           (= idx split-pos) (inc e)
                           (> idx split-pos) e))]
      (map-indexed split-fn board))))

Let’s give it a shot!

user=> (inc-at-v2 board 2 2)
(0 0 0 0 1 0 0 0 0)
user=> (inc-at-v2 board 2 3)
(0 0 0 0 0 1 0 0 0)
user=> (inc-at-v2 board 3 3)
(0 0 0 0 0 0 0 0 1)

It works fine again. Is it better? I’m still unconvinced, esp. the split-fn looks terribly. I need a version without any mutation, even with atoms, refs or agents. Would you mind lending me a helping hand? How would you change the function inc-at-v2 to be more effective and look prettier?

Be Sociable, Share!
This entry was posted in Languages.

7 Responses to Reversi in Clojure…functional

  1. Cameron says:

    Hi Jacek!

    I was glad my original post got you going on this. I’m going to update my post to include a link to your page, as I think it may include approaches to the game that some people may find lacking in my post.

    – Cam

  2. Mark Engelberg says:

    List is really not the appropriate data structure to use for your board representation. You should either use a vector, or better yet use a hash map that maps [row col] pairs to 0 or 1.

    If you use a more appropriate data structure, you’ll end up with more elegant, functional code. For example, with the hash map representation:

    (def inc-at [board row col] (assoc board [row col] (inc (get board [row col] 0))))

  3. sb says:

    I’m pretty sure the idiomatic way is to use a map where each key is a [x y] pair or nested vectors (which one depends on other operations you want to preform) + assoc-in and/or update-in:

    (defn inc-at-v2
    [board row col]
    (update-in board [row col] inc))

  4. Thank you Cam, Mark and sb! Your comments whetted my appetite even more for delving into transforming the game into a functional one. They say it’s achievable and the state of an application is just a state of our thinking about a problem. We’ll see how it works out.

  5. Jacek,
    You may want to use a zipper. Here is a version of inc-at-… which uses it.

    (require ['clojure.zip :as 'z])
    (def board (repeat 9 0))
    (defn inc-at-gb [board row col]
    (let [pos (+ (* 3 (dec row)) col)
    board-zipper (z/seq-zip board)
    functions (flatten (list z/children (repeat pos z/prev) #(z/edit % inc) (repeat pos z/next)))]
    ((apply comp functions) board-zipper)))

    user=> (inc-at-gb board 1 1)
    (1 0 0 0 0 0 0 0 0)
    user=> (inc-at-gb board 1 2)
    (0 1 0 0 0 0 0 0 0)
    user=> (inc-at-gb board 2 2)
    (0 0 0 0 1 0 0 0 0)
    user=> (inc-at-gb board 3 2)
    (0 0 0 0 0 0 0 1 0)

  6. This is even better:

    (defn inc-at-gb [board row col]
    (let [pos (+ (* 3 (dec row)) col)
    board-zipper (z/seq-zip board)
    functions (flatten (list z/root #(z/edit % inc) (repeat pos z/next)))]
    ((apply comp functions) board-zipper)))

Leave a Reply

%d bloggers like this: