github twitter linkedin email rss
Karate Chop Kata and coding practices in Clojure 2
Feb 6, 2012
4 minutes read

Following my last post I was left with a solution of the Kata that can be translated to a non-functional language.

(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]
        (if (number-is-out-of-bounds number sub-array)
            -1
            (if (= number (first sub-array))
                position
                (recur (+ position 1) (rest sub-array))
            )
        )
    )
)

This solution allowed me to prevent side effects and dependencies between the order on which the calls of loop are ordered so that recurcould re-bind the function.

# Divide and conquer

So a call that looks like this

(chop 1 [1 2 3])

Can also be described as this

((chop 1 [1]) (chop 1 [2]) (chop 1 [3])

The way to get the same result and remove the sequencing is by calling mapand Clojure translates that as

(map #(chop 1 %) [1 2 3])

Being stateless is a very important part of mapas implementations differ in the order they run through the array and some even return once they grab the first valid result.

Conquer and unify

Running map won’t get me the exact same result but actually just an array of running chopon each element. Something like

(0 -1 -1)

Which is not what I want, but having no knowledge of what is a valid result, I have decoupled it! For that we use fold (also known as reduce or some other variations like filter) So let’s abstract foldaway into another function, we will be calling it a way similar to

(valid-result (run-chop 1 [1 2 3]))

Yes, functional language will allow you to use dependency injection out of the box by splitting the way you iterate from the way you pick data from the way you decide on the result of the data. This page has a very simple diagram of map-reduce.

# Solving the Kata yet again

Now that I’ve explained the basis you can see that in the next commit I did some changes like splitting out:

how to check the position anywhere in the array; filter out all non valid results; how to display the result; Actual call.

(defn check-position [position-value number]
    (when (= number (last position-value))
        (first position-value)
    )
)
(defn get-valid-positions [result-set-from-map]
        (filter
            #(not (nil? %))
            result-set-from-map
        )
)
(defn return-result [list-valid-positions]
    (if (empty? list-valid-positions)
        -1
        (first list-valid-positions)
    )
)
(defn chop [number array]
    (let [list-valid-positions
        (get-valid-positions
                (map
                    #(check-position % number)
                    (map-indexed vector array)
                )
            )
        ]
        (return-result list-valid-positions)
    )
)

After that I decided to make up some more features - allowing for multiple valid results

;homework, add multiple valid positions
(deftest size-four-array-right-param-on-0-and-1 (is (=  [0 1] (chop 1 [1 1 5 7]) )))
(deftest size-four-array-right-param-on-1-and-2  (is (=  [1 2] (chop 3 [1 3 3 7]) )))
(deftest size-four-array-right-param-on-2-and-3 (is (=  [2 3] (chop 5 [1 3 5 5]) )))
(defn check-position [position-value number]
    (when (= number (last position-value))
        (first position-value)
    )
)
(defn get-valid-positions [result-set-from-map]
        (filter
            #(not (nil? %))
            result-set-from-map
        )
)
(defn return-result [list-valid-positions]
    (if (empty? list-valid-positions)
        -1
        (if (= (count list-valid-positions) 1)
            (first list-valid-positions)
            list-valid-positions
        )
    )
)
(defn chop [number array]
    (let [list-valid-positions
        (get-valid-positions
                (map
                    #(check-position % number)
                    (map-indexed vector array)
                )
            )
        ]
        (return-result list-valid-positions)
    )
)

And skipping a few steps again I went onto this solution which allows me to clearly see what functions map, filter and shows conditionsto display the final result.

(defn position-check [position-value number]
    (when (= number (last position-value))
        (first position-value)
    )
)
(defn reduce-to-valid [result-set-from-map]
        (filter #(not (nil? %)) result-set-from-map)
)
(defn return-result [list-valid-positions]
    (cond
        (empty? list-valid-positions)   -1
        (= (count list-valid-positions) 1)  (first list-valid-positions)
        :else   list-valid-positions
    )
)
(defn map-position-check [number array]
        (map #(position-check % number) (map-indexed vector array))
)
(defn chop [number array]
    (return-result  (reduce-to-valid (map-position-check number array)))
)

How important is map-reduce

Well, it’s important enough for Google have their own implementation as well as Apache.

While all the advances I mentioned until now show us the way map-reduce enforces best practices the most recent advantage is that besides being stateless, injected and unordered it can also be distributed.

If instead of chop we had a very resource intensive function then it would allow us to break it down and run it on any number of servers. As long as we have a way to retrieve the results - we don’t even have to wait for all the results if the valid one is quicker (i.e. DB searching first valid ID).

We could also have smaller indexes that would be server specific (or shared in combinations of servers).

For more details on current uses check the wikipedia entry.

Other references I utilised include this page and this one.


Back to posts