Clojure: Koan to Kata
Recently, I went from knowing a bit of Clojure (a programming language) to writing a program that plays a word game invented by Lewis Carroll. Here’s what I learned.
I was first introduced to the idea of Koans by the Ruby Koans. In the context of programming, a koan is a small deliberate piece of incomplete code meant to teach the student a lesson about the language through its completion. Here’s an example:
(meditations "To understand reality, we must compare our expectations against reality" (= __ (+ 1 1)))
We went through them one by one, prompted by the “Meditations”, which are actually unit tests. The kata above is solved by substituting
__. Solving it reveals something about the curious way operations and comparisons are written in Clojure.1
The kata is another form of practice. Here, the student takes a larger problem or puzzle and solves it. Katas are meant to be revisited. Redone as a means to self-improvement. They raise the question: how could I better solve this problem. We solved two katas as a group at the Day of Functional.
Given two words with the same number of letters, find words that link those words, changing only one letter at a time. For example
(doublets "door" "lock") should result in something like:
(door boor book look lock).
Spoiler alert: solution ahead
Good solutions start with a plan. I had a vague one in mind. It was to start by defining the pieces I would need, starting with a function to tell if words were “neighbors”–one letter off from each other. That necessesitated a function to determine the distance. The culmination of the plan was to wire together everything in a doublets function that called itself until it either got to the end word or failed to find a doublet.
I kept fairly granular commits, so you can see my thought process in the history of my solution if you’re interested.
Executing the plan
For my first take on the kata, I wanted to see how far I could get with only the basic tools of clojure and problem solving. I restricted myself to the documentation and the cheatsheet. This was an artificial constraint, which I would not impose in a normal situation. In fact, it allowed me to pursue a partial, non-optimal solution.
I used LightTable as my interactive editor.
It works… kind of
My plan was not far off from a solution. The hardest thing to reason about for me was how to take the constituent functions and connect them in a
doublets function. Particularly I suspect, because I chose a recursive approach, where the
doublets function calls itself, filling in the missing parts until it hits a dead end or reaches the last word.
Climbing out of a hole
Partially out of frustration, I sometimes kind of brute forced the rules for things like the algorithm for
sufficient-neighbors, my function that returned candidates for the next word in the chain.
I started to make more progress when I isolated parts of those functions and called them with sample data in my repl/editor. If you go through the history, there are a couple times when I just got a conditional backwards.
Eventually, I was able to find that one of the constraints I put–that the words be increasingly close to the target word–didn’t always work. So, I relaxed the algorithm to allow it to meander.
To figure out a problem I was having with recursion that sometimes didn’t terminate, I turned to
clojure.tools.trace/dotrace, which prints a handy trace of described function calls to the console. This let me discover one of the more amusing ways my approach went wrong.
View the code that generated that trace.
Through all this, I eventually got to a version that works.
(doublets "snarl" "smile") ;=> ("snarl" "snare" "scare" "scale" "shale" "shole" "spole" "spile" "smile")
Here’s the code for this version if you want to try it.
A deficiency and a familiar shape
My solver still sometimes doesn’t find a doublet when it should. I discovered this when I tried to reverse one of the test cases, and it didn’t find the doublet.
The key mistake is that I didn’t recognize a familiar shape at the outset: finding doublets is a tree search. My initial plan missed that search algorithms sometimes hit dead-ends and need to backtrack, which my doublets function does not handle.
A normal step at this point would be to refactor the solution to make it more readable and understandable. However, given that the original approach has flaws, I am more likely to approach the problem from another angle, this time allowing for research into search algorithms.
I learned a few things, among them
- one way to write a recursive program in clojure
- how to debug clojure using clojure.tools.trace
- and a greater appreciation of stepping back, researching, and reflecting.
- Bonus: the”aardwolf” is an actual animal
1: In fact, it reveals the near totality of syntax in Lisp: the s-expression.
Thanks to Carin Meier for writing the kata and the encouragement.
Aardwolf photo by Greg Hume.