Clojure Kata Two: Karate Chop (Pt. 1)

March 6, 2010

I thought it might be interesting to work through the code katas created by Pragmatic Programmer Dave Thomas to assist with my Clojure learning. If you’re looking for Kata One, don’t worry about searching – I started with Kata Two as I needed an actual coding exercise.

The instructions for the Kata can be found at: http://codekata.pragprog.com/2007/01/kata_two_karate.html

The task is to implement five different binary search algorithms, one per day. I don’t actually have five consecutive days to do this, so don’t expect the five parts to be written about each day. There will be gaps.

It’s been about 15 years since I wrote a binary search algorithm, using the language Modula-2. I was toying with the idea of going off and reading up on binary searches, but I decided the best way to approach it was from first principles – only allowing myself access to a Clojure reference manual. After all, I go on about the importance of learning basic algorithms even in this day and age… so about time I put my money where my mouth is!

The trickiest part of the kata wasn’t so much coming up with the algorithm, an iterative binary search is easy, but expressing the algorithm using Clojure’s syntax. That’s mainly the inexperience with the language showing, but the resulting code didn’t feel too elegant. In particular, the parentheses became more of a hindrance than a help – they start to look plain ugly, get in the way and I don’t think I’ve ever relied on my IDE’s parenthesis matching so much. I still don’t agree with Neal Stephenson that LISP is the only language which can truly be described as beautiful… despite all the power and flexibility it can yield in the right hands.

I may not have reached Clojure enlightenment yet, but gradually I built up a rhythm with the coding. Once the tests passed, I decided to stop rather than try to rework the code into something that looked and felt better. Take the lessons learnt and apply to the next algorithm – the work for this one has already been done.

First step with the coding was to create the tests. Although not a fan of Python’s doc tests, I opted to use Clojure’s equivalent for quickness – and I’ve decided I’m not a massive fan of them either. Moan, moan, moan. ;-)

(defn
 #^{:test (fn []
 (assert (= -1 (chop 3 []) ))
 (assert (= -1 (chop 3 [1]) ))
 (assert (=  0 (chop 1 [1]) ))

 (assert (=  0 (chop 1 [1 3 5]) ))
 (assert (=  1 (chop 3 [1 3 5]) ))
 (assert (=  2 (chop 5 [1 3 5]) ))
 (assert (= -1 (chop 0 [1 3 5]) ))
 (assert (= -1 (chop 2 [1 3 5]) ))
 (assert (= -1 (chop 4 [1 3 5]) ))
 (assert (= -1 (chop 6 [1 3 5]) ))

 (assert (=  0 (chop 1 [1 3 5 7]) ))
 (assert (=  1 (chop 3 [1 3 5 7]) ))
 (assert (=  2 (chop 5 [1 3 5 7]) ))
 (assert (=  3 (chop 7 [1 3 5 7]) ))
 (assert (= -1 (chop 0 [1 3 5 7]) ))
 (assert (= -1 (chop 2 [1 3 5 7]) ))
 (assert (= -1 (chop 4 [1 3 5 7]) ))
 (assert (= -1 (chop 6 [1 3 5 7]) ))
 (assert (= -1 (chop 8 [1 3 5 7]) )) ) }
 chop
 [item list]
 ...

I made the chop function a wrapper around the real action, meaning I could reuse it for different algorithms easily as well as keep the implementation separate. I opted to call a function called bsearch, passing the list of values, the value to search for, and a start and end index to define the “partition” under examination. The initial start and end indexes set the partition to be the whole of the list – since we have no idea where the value is to begin with.

(bsearch list item 0 (count list))

The initial check in bsearch is for an empty list. If we have nothing to search, we know for sure that the value doesn’t exist in it.

Next, we take our partition, or slice as I called it in the code, for examination. If the slice contains one item, we have a simple case to check: either that item is the one we’re looking for, or it isn’t.

If we have more than one item, our proper binary search comes into play. We find the mid-point and check the value of that item. As with the single item list, it’s either the value we want, or it isn’t. If it isn’t, we split the slice on that point and search the “left half” (values lower than the mid value) or the “right half” (values higher than the mid value) accordingly.

Although my intention was to do an iterative algorithm, Clojure’s syntax nudged me into a more recursive approach. For the tests supplied, blowing the stack is unlikely but for larger lists the algorithm won’t be the most efficient approach.

A couple of helper functions first:

(defn is-single-item? [ list ]
 (= 1 (count list)))

(defn mid-index [ list ]
 (quot (count list) 2))

These were just to make a couple of spots in the code slightly more readable at a glance.

And the bsearch function in all its nested glory:

(defn bsearch [ list value slice-start slice-end ]
 (if (empty? list)
  -1
  (let [ slice (subvec list slice-start slice-end)]
   (if (is-single-item? slice)
    (if (= value (first slice) )
     slice-start
     -1)
    (let [ mid (mid-index slice) ]
     (let [ mid-value (get slice mid) ]
      (if (= value mid-value)
       (+ slice-start mid)
       (if (< value mid-value)
        (bsearch list value slice-start (- slice-end mid))
        (bsearch list value (+ slice-start mid) slice-end)))))))))

Check out the multiple closing parentheses. That just looks wrong, but I see lots of example Clojure and LISP code like that. When writing the code, I ended up writing the parentheses in alignment for readability, then when I finish coding I reposition the closing parentheses to match the style above. I can’t help but think it’s a code smell indicator.

Certainly an interesting exercise and my first go at writing Clojure code from scratch, not following along with the Programming Clojure book. Definitely has room for improvement.

Now, how am I going to write my second binary search algorithm…?

About these ads

2 Responses to “Clojure Kata Two: Karate Chop (Pt. 1)”

  1. John C Says:

    I’ve created a public repository on BitBucket for the solutions as I create them: http://bitbucket.org/metaljoe/metaljoe_codekata/

  2. David Says:

    Are you an emacs person? Regarding paren matching, you should try emacs with paredit minor mode which allows you to do ‘pseudo-structural’ editing of lisp code, it is truly awesome! It allows you to think in terms of the structure of s expressions. Very interesting experience.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 626 other followers

%d bloggers like this: