github twitter linkedin email rss
Karate Chop Kata and coding practices in Clojure
Jan 30, 2012
8 minutes read

Introduction

Having used Scheme and LISP in university as well as Java I recently became interested in Clojure – Functional languages are an interesting paradigm which is not used as often as it should on the day to day development.

It’s also seen as a great work horse for big data and distributed environments so I wanted to know what could I learn from it.

This is my first contact with Clojure and I admit I haven’t looked back into LISP in years so you can consider this as starting from scratch.

This page is quite helpful showing how Clojure works for non LISP developers and I won’t be explaining details about Clojure synthax and semantic if there is a common direct replacement for it.

Setting up Clojure and the Kata

Googling Clojure I end up at Clojure.org and I soon walked into the Getting Started tutorial which advised to install Leiningen, a project automator.

Great! Being in Linux I could easily grab Clojure and Leiningen.

After that just create a new project.

% lein new myproject
Created new project in: /home/g/myproject

And it has tests out of the box - here is a good read on unit tests in Clojure and here is an article about Rich Hickey, creator of Clojure, talking about TDD – but I’m going with Leiningen.

% lein test
Copying 1 file to /home/g/myproject/lib
Testing myproject.test.core
FAIL in (replace-me) (core.clj:6)
No tests have been written.
expected: false
actual: false
Ran 1 tests containing 1 assertions.
1 failures, 0 errors.
Time to move the Kata to the test skeleton file.

The kata says that given an array and a number the Chop function should output the 0-based position of the number in the array or -1 if not available.

Here are test cases for multiple sizes of array including valid values for all positions as well as invalid values.

(deftest empty-array-is-false (is (= -1 (chop 3 []) )))
(deftest size-one-array-wrong-param-is-false (is (= -1 (chop 3 [1]) )))
(deftest size-one-array-right-param-on-0-is-0  (is (=  0 (chop 1 [1]) )))
(deftest size-three-array-right-param-on-0-is-0 (is (=  0 (chop 1 [1 3 5]) )))
(deftest size-three-array-right-param-on-1-is-1 (is (=  1 (chop 3 [1 3 5]) )))
(deftest size-three-array-right-param-on-2-is-2  (is (=  2 (chop 5 [1 3 5]) )))
(deftest size-three-array-wrong-param--0-is-false  (is (= -1 (chop 0 [1 3 5]) )))
(deftest size-three-array-wrong-param-2-is-false (is (= -1 (chop 2 [1 3 5]) )))
(deftest size-three-array-wrong-param-4-is-false  (is (= -1 (chop 4 [1 3 5]) )))
(deftest size-three-array-wrong-param-6-is-false  (is (= -1 (chop 6 [1 3 5]) )))
(deftest size-four-array-right-param-on-0-is-0 (is (=  0 (chop 1 [1 3 5 7]) )))
(deftest size-four-array-right-param-on-1-is-1  (is (=  1 (chop 3 [1 3 5 7]) )))
(deftest size-four-array-right-param-on-2-is-2  (is (=  2 (chop 5 [1 3 5 7]) )))
(deftest size-four-array-right-param-on-3-is-3  (is (=  3 (chop 7 [1 3 5 7]) )))
(deftest size-four-array-wrong-param-0-is-false  (is (= -1 (chop 0 [1 3 5 7]) )))
(deftest size-four-array-wrong-param-2-is-false  (is (= -1 (chop 2 [1 3 5 7]) )))
(deftest size-four-array-wrong-param-4-is-false  (is (= -1 (chop 4 [1 3 5 7]) )))
(deftest size-four-array-wrong-param-6-is-false  (is (= -1 (chop 6 [1 3 5 7]) )))
(deftest size-four-array-wrong-param-8-is-false  (is (= -1 (chop 8 [1 3 5 7]) )))

Starting the Kata

I did the Kata by commenting out the tests and adding one at a time trying to do the smallest possible step possible that allows for the full tests (at the moment) to pass.

Going to the skeleton main file I got enough to pass the first two tests (empty and false one sized array)

(defn chop [number array] -1)

Next step needs to get the valid scenario for the first element, this is how the failing test looks.

% lein test
Testing myproject.test.core
FAIL in (size-one-array-right-param-on-0-is-0) (core.clj:7)
expected: (= 0 (chop 1 [1]))
    actual: (not (= 0 -1))
Ran 3 tests containing 3 assertions.
1 failures, 0 errors.

And here is my solution.

(defn first-position-is-correct [number array]
    (= number (first array))
)
(defn chop [number array]
    (if (first-position-is-correct number array)
        0
       -1
    )
)

So this is interesting – Clojure looks ugly to a non-functional developer with ‘parenthesis everywhere’ but actually they bring out the code smells!

The amount of nesting increases for everything which means that even declaring a variable will increase nesting because it will make the scope stand out… If you don’t break things into smaller methods and keep variables under control it becomes unreadable.

Example: I want to print the variable before doing the if clause.

(defn first-position-is-correct [number array]
    (do
        (println number array)
        (if (integer? array)
            (= number array)
            (= number (first array))
        )
    )
)

There goes another level of nesting, plus it’s strange to thing about a list (it’s all lists) with a print and an if clause and that’s the point.

Solving the Kata

Adding the scenarios for the second element.

(defn first-position-is-correct [number array]
    (if (integer? array)
        (= number array)
        (= number (first array))
    )
)
(defn chop [number array]
    (if (first-position-is-correct number array)
        0
        (if (first-position-is-correct number (rest array))
            1
            -1
        )
    )
)

first picks the first element of an array, rest does a new list with the remaining elements.

It’s frowned upon to set variables and that will make more sense closer near the end of this post, everything should be immutable - here is a good read about some best practices with Clojure.

I nested the ifs … and kept on going for the third element – NEST ALL THE THINGS.

(defn first-position-is-correct [number array]
    (if (integer? array)
        (= number array)
        (= number (first array))
    )
)
(defn chop [number array]
    (if (first-position-is-correct number array)
        0
        (if (first-position-is-correct number (rest array))
            1
            (if (first-position-is-correct number (rest (rest array)))
                2
                -1
            )
        )
    )
)

Fair enough, I can admit that this is horrible and even though I don’t have variables that can be set I still have the ifs and rest nesting, I’m going to get rid of that repetition.

In the following example loop says that it starts on position 0 with sub-array array – there is no difference between data, built-in functions and the developer’s functions so loop is just another built-in function with a list of arguments that can be used in the inner scope, we can even re-define loop.

If it finds the number returns, if it’s empty returns … otherwise calls loop recursively with recur.

(defn chop [number array]
    (loop [position 0 sub-array array]
        (if (= number (first sub-array))
            position
            (if (= 0 (count sub-array))
                -1
                (recur (+ position 1) (rest sub-array))
            )
        )
    )
)

So this now works with all arrays and has no movable parts – the kata is done.

Not your average loop method

But there is something more interesting happening: recur does not keep the previous calls of loop open but actually re-binds the arguments and does a new call which means the stack will never have a larger size and you’ll have a smaller and smaller array – it’s close to an iterative call but you don’t even keep state of the current position, you just move along.

This can be done easily because even thought I could create variables I tried not to use them, now we don’t call anything outside the scope of the loop (the arguments are the original ones) so it can be easily be extracted out into a new method – or in this case it’s a re-bind.

Clojure is about list manipulation, you sort it, you chop it and you don’t keep state – you never re-assign anything so there are no side effects which makes refactoring so much nicer.

You can still see how ugly it still looks with the nested ifs and that recur in the end.

Using Clojure to guide my refactoring

From this point onward it’s all about how Clojure helped me get some nicer code.

I went on to try to trim the number of steps used to run all tests (not a request in the kata but I’m trying to introduce more features). Moving the -1 case from the middle of the loop

(defn chop [number array]
    (loop [position 0 sub-array array]
        (if (= 0 (count sub-array))
            -1
            (if (= number (first sub-array))
                position
                (recur (+ position 1) (rest sub-array))
            )
        )
    )
)

A few steps ahead getting rid of arrays I know will fail and stopping when we need it isn’t necessary.

(defn chop [number array]
    (if (or (= 0 (count array)) (< (last array) number))
        -1
        (loop [position 0 sub-array array]
            (if (or (= 0 (count sub-array)) (< number (first sub-array)))
                -1
                (if (= number (first sub-array))
                    position
                    (recur (+ position 1) (rest sub-array))
                )
            )
        )
    )
)

Also I sacrificed having to check the last element all the time in order to get all conditions in the same function – this is because checking the same elements in different places creates more nesting – keeping them together helps me extract a new function – readability is of higher importance than premature optimisation.

(defn number-is-out-of-bounds [number array]
    (or (= 0 (count array)) (< number (first array)) (> number (last array)))
)
(defn chop [number array]
    (loop [position 0 sub-array array]
        (if (number-is-out-of-bounds number sub-array)
            -1
            (if (= number (first sub-array))
                position
                (recur (+ position 1) (rest sub-array))
            )
        )
    )
)

After joining all uses of the validation it was easier to get rid of the nested if in exchange for a switch condition – the language is forcing you to make it clearer and now this option seems more obvious than before.

(defn number-is-out-of-bounds [number array]
    (or (empty? array) (< number (first array)) (> number (last array)))
)
(defn chop [number array]
    (loop [position 0 sub-array array]
        (cond
            (number-is-out-of-bounds number sub-array) -1
            (= number (first sub-array) position
            :else   (recur (+ position 1) (rest sub-array)
        )
    )
)

Conclusion

So there’s the final result of the kata – no state, no moving parts and won’t blow up the stack if it has an impossibly large array.

We know the switch condition is a code smell, that is because the Clojure way would be map-reduce … that will be the next post.

We could always just use the built-in function :-)

(defn chop [number array]
    (.indexOf array number)
)

Back to posts