How to code it? - Functional programming & problem solving heuristics

Opinions differ about the relationship of mathematics and programming. Depending on temperament, one might say that they are essentially the same as both strive for understanding in a precise formal manner. Or, it can be argued that practical engineering goals are rather different from aiming for unquestionable proofs. Functional programmers, in particular, are probably more comfortable with the connection. They tend to know that some mathematical constructs like lambda calculus, or whole theories like category theory form the basis of their favourite languages. In any case, there is little merit in trying to answer a philosophical question. It is more beneficial to concentrate on what we can get out of the relationship.

I recently taught a Clojure course targeted for students who had no previous programming experience at all. There, students had to solve problems ranging from very simple arithmetic calculations to more challenging ones, like finding the number smaller than 1000 with longest run under the iterated Collatz function. When facilitating their coding efforts, I quickly found myself repeating the same pieces of advice. They felt rather familiar.

Indeed, I was using ideas from the classical problem solving heuristics book in mathematics: “How to Solve It: A New Aspect of Mathematical Method” by George PĆ³lya, first published in 1945. It is still in print. As you might guess from the year of publishing, new is not that new any more. However, the principles of problem solving are not subject to change (at least until the appearance of direct augmentation of brains). I do recommend reading this book, despite the fact it only talks about solving math problems on the high school level. If you need someone whose words have some more weight, Rich Hickey, the author of Clojure, highly recommends the book in his classic talk “Hammock Driven Development”

On the other hand, we are in the era of tl;dr, where blog posts have to announce in advance how much time it will take to read them. Reading the book might take a couple of days, hmm…, this might be a tall order. I certainly couldn’t extend the reading lists of my students, so I decided to reread the book myself and summarise its ideas in a rehashed form, in the context of functional programming languages. Here is the result:

“How to Code It?”

It was originally prepared for a beginner Clojure course, but it applies to any functional programming language with a REPL (read-eval-print-loop). It is relevant for solving practise problems up to programming contest level. These guidelines are not for structuring bigger applications, so they are most useful in the process of learning a new language, or solving isolated problems in a big software system.