A round of golf

Last weekend, I played a round of golf with Lewis.

Out of context, this activity isn’t surprising; I’m originally from South Florida, and Lewis is originally from near Coeur d’Alene, Idaho.

However, the savvy reader might wonder exactly how two students living in Philadelphia in early February could play a round of golf. I suppose I should, in that case, clarify — we didn’t play the sport of golf, but instead engaged in code golf.

Code golf is a game in which a programmer tries to fully write a function in as few characters as possible. Comments don’t count toward length, nor does whitespace. (Brevity and readability are two entirely different concepts.) Lewis had a code golf homework assignment for CIS 194, Penn’s introductory Haskell class, and he invited me to code alongside him.

I tend to be a pretty conservative Haskell programer; my top priority is writing understandable code. I’m not personally a huge fan of pushing complex one-liners into production code; eventually, someone else will read your code, and they shouldn’t have to spend ten minutes figuring out exactly what one line of Haskell does.

However, playing code golf last weekend showed me some of its benefits that I think apply universally to programming.

Refactoring

Nobody breaks par on their first attempt at a challenging golf hole. Likewise, nobody writes a function with optimal brevity on the first try. Therefore, code golf is a useful practice because it forces a programmer to think about efficient code re-writes. Specifically in functional languages like Haskell, refactoring code into more modular, uncoupled parts is a great way to shorten your code.

As an example, let’s examine the Haskell function transpose. It takes a list of lists and runs a 2D matrix transposition on it. Here’s how it’s implemented in Data.List:

transpose []             = []
transpose ([]   : xss)   = transpose xss
transpose ((x:xs) : xss) = (x : [h | (h:_) <- xss]) : transpose (xs : [ t | (_:t) <- xss])

This is pretty verbose, don't you agree? Lewis thought so. Here's his first shot at a one-line implementation.

transpose m = foldr (\r n -> map (\(x,y) -> x:y) (zip r n)) (replicate (length $ head m) []) m

Lewis's line of logic was that he should make a list of empty matrices of the output length — replicate (length $ head m) — and then iterate over the input list, consing one element at a time on to each output list.

He then realized that, by mapping over a call to zip, he had explicitly coded a common higher-order function, zipWith.

transpose m = foldr (zipWith (\x y -> x:y)) (replicate (length $ head m) []) m

Finally, a cryptographer and assistant professor that Lewis knew showed him an even shorter solution by encapsulating the replication and fold into a second map:

transpose m = map (\i -> (map (\v -> v !! i)) m) [0..((length $ head m) - 1)]

The point here is not to belabor the transpose function — clearly this gets a bit hard to understand. However, playing code golf forces you to think about how to refactor your code to significantly shorten it. Refactoring out common design patterns is a much better way to reduce character count in a function than trying to play with parentheses, currying, and flipping. Thus, code golf builds your skills at identifying reusable patterns in code, specifically in a functional language that allows such abstractions to be made.

Test cases

Students don't write test cases. Put yourselves in the shoes of Billy, a first-year CS student. Billy is a reasonably intelligent 18-year old, and he can code decently well. He also knows that after this week, he's never going to touch his homework again, so why bother testing the functions? I can't say I blame him for that. However, not writing test cases is obviously an awful habit to get into.

Code golf forces you to write test cases because you're rapidly iterating on a function, and you need to ensure its correctness after making drastic changes. Given that code golf involves making relatively radical changes to how you've written a function, you need some test cases to verify that your new implementation is correct. It is incredibly difficult to eyeball a code-golfed function and determine its correctness. Hell, I wouldn't believe that the shortest transpose implementation made any sense had I not tested it myself.

Testing your code is especially satisfying in Haskell, where you can easily use QuickCheck properties to rapidly test hundreds of different inputs for you. This would be a great way to find out that Lewis's code does not work for asymmetric 2D matrices.

Competition

I am firmly of the belief that the power of the human mind is augmented by a healthy dose of competition. (One could call me an Objectivist.) Humans thrive on competition; this is why we play sports, this is why we found start-ups, and this is why we surround ourselves with intelligent and talented people.

Lewis has more experience with computer science than me, and he can definitely beat me in a game of code golf most days. However, I'll never pass up the opportunity to play. The competitive aspect of code golf — trying to write a function in fewer characters than anyone else — encourages our creative juices to flow. You won't sit back and say, "This is good enough"; you'll iterate and contemplate until you are positive you can't excise another character from your implementation.

Speaking personally, this precise notion is what enabled me to give Lewis a run for his money in code golf. I wanted to beat him. As a result, I found new heuristics I could use in the future (for example, y > max x z is a cleaner way of saying x < y && y > z). Moreover, when we finally stopped playing and compared our scores and implementations, we were both able to learn from each other's successes and errors.

Conclusion

Code golf isn't directly useful in that the code you write isn't put in real-world production code. Other people have to read your production code, and it's obviously more efficient for them to read a three-liner in 30 seconds than a one-liner in five minutes.

However, code golf gives you a better eye for patterns of abstraction and encapsulation that a high-level language will allow you to abstract away. Our example of transpose showed incremental abstractions from explicit recursion to folding over a map and zip to folding over a zipWith. We wrote rigorous test cases for our function to provide strong evidence for correctness of code. By making this a game against each other, we mutually learned from each other.

My recommendation — play a round of golf this weekend, no matter which language you pick.

Max and Lewis are sophomores at the University of Pennsylvania. Lewis would like to add that list comprehensions are a great abstraction to shorten and clarify your code. Follow them both on Twitter @MaxScheiber and @LewisJEllis.

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>