Just yesterday I tried my hand at the bowling game kata in Clojure. It was ok. It worked. But what I produced felt more like a direct translation from a procedural implementation (confession: it was).
In a functional paradigm, solutions often resemble a series data transformations, like piping the output stream of a unix-like utility to the input stream of another, the output of which gets piped to yet another, and on and on until the right data comes out. For instance, have you every needed to know how many entries in a list matched certain criteria? How about this example, which counts the number of entries in a directory listing that end in z:
$ ls -1 | grep 'z$' | wc -l
3
Command 1: ls -al
This command sends a directory listing to its output stream. For the sake of this example we'll assume this was the output:
foo
bar
baz
fiz
buz
Command 2: grep 'z$'
This command filters the input stream it receives for lines that end in the z character. Given the output of command 1 above, this command will produce the following output stream:
-rw-r--r-- 84 mike staff 42 Aug 2 15:30 baz
-rw-r--r-- 84 mike staff 42 Aug 2 15:30 fiz
-rw-r--r-- 84 mike staff 42 Aug 2 15:30 buz
Command 3: wc -l
This command counts the number of lines from its input stream and sends that number to its output stream (along with some leading whitespace).
Now, back to bowling. Yesterday's solution was based on a single function with a big, fat 'loop/recur' to accumulate the score as it processed each 'frame' in the provided 'rolls' collection. A functional approach (using Clojure's thread-last macro), would look something more like this:
(defn bowl [rolls]
(->> rolls ; 1. [5 5 3 2 1 0 10 3 4 0 0 0 0 0 0 0 0 0 0]
rolls->frames ; 2. [[5 5 3] [3 2] [1 0] [10 3 4] [3 4] [0 0] [0 0] [0 0] [0 0] [0 0]]
(take 10) ; 3. No change in this case, but important when 10th frame has 3 throws!
flatten ; 4. [5 5 3 3 2 1 0 10 3 4 3 4 0 0 0 0 0 0 0 0 0 0]
(apply +))) ; 5. Sum: 43
- Start with the list of rolls.
- Transform it to a list of frames with all the strike/spare bonuses allotted.
- Ensure we only ever deal with 10 frames. This is very important when the 10th frame has 3 throws.
- Flatten the frames listing. (Where has this function been all my life??)
- Sum the flattened listing. Done!
Easy, right? Well, you might be wondering about the 'hand-waivy' nature of step 2. In pairing with my mentor, Micah Martin, here's what we came up with first:
(defn rolls->frames [rolls]
(loop [result []
rolls rolls]
(cond (empty? rolls) result
(= 10 (first rolls))
(recur (conj result (take 3 rolls)) (rest rolls))
(= 10 (apply + (take 2 rolls)))
(recur (conj result (take 3 rolls)) (drop 2 rolls))
:else
(recur (conj result (take 2 rolls)) (drop 2 rolls)))))
There's a lot going on. We are setting up a recursion-based loop and accumulating the resulting list of frames. This was a good approach because it allowed the high-level thread form shown above, but having to accumulate the entire listing of frames feels clunky. Often, clojure data transformations are lazily-evaluated and this implementation doesn't allow for that. To be fair, no one's worried about running out of memory in this case, but the next step was for us is to generate a lazily-evaluated collection using lazy-seq:
(defn rolls->frames [rolls]
(cond
(empty? rolls) []
(= 10 (first rolls))
(cons (take 3 rolls) (lazy-seq (rolls->frames (rest rolls))))
(= 10 (+ (first rolls) (second rolls)))
(cons (take 3 rolls) (lazy-seq (rolls->frames (drop 2 rolls))))
:else
(cons (take 2 rolls) (lazy-seq (rolls->frames (drop 2 rolls))))))
Notice that this new approach doesn't accumulate a named list or use loop/recur (but it is definitely still recursive). Also notice that the output of this function will differ from the loop/recur implementation in that the listing of frames will be reversed, but this doesn't have any bearing on the final outcome because of the associative property of addition.
Here's today's version: