Why try functional programming?

September 2, 2016

“Mind-blowing” - that is how I’d most often heard functional programming described before trying it. Now that I have tried it, I absolutely agree. However, the mind-blowing parts are not the first things you learn about a new programming language. That’s why I decided to write this teaser post - I’ll try to explain in the most straightforward way the parts of Haskell and Clojure that blew my mind, without requiring any background in either:

code is data, data is code: what is a homoiconic language and why is it so powerful?
haskell’s fascinating type system and how anyone who likes math will feel haskell is the programming language they’ve been missing their whole life
more on math and haskell: a little bit of category theory

Note that none of these points are what people will tell you is good about functional programming (concurrency, immutability, laziness, etc…) - although these are all very true, my point is to focus on the cool parts rather than the useful parts!

Code is Data: Homoiconicity

Lisps, Parentheses, and Trees

Some programming languages are Lisps. This essentially means that their syntax has a lot of parentheses, like so:

(map #(if (even? %) (+ 2 %) (+ 1 (* 3 %))) (range 10))

All right, that’s pretty confusing on a first parse. We’ll look at this expression in detail, but I’ll tell you what it does right now: it takes an list of numbers from 0 to 10, then performs one iteration of the Collatz conjecture algorithm on each of its elements:

\[\begin{eqnarray} f(n) =\begin{cases} n/2, & \mbox{if } n\mbox{ is even} \\ 3n+1, & \mbox{if } n\mbox{ is odd} \end{cases} \end{eqnarray}\]

The way Lisp (and Clojure) work is that the parentheses serve to separate tree nodes. Each node is of the form (function expr1 expr2 ...), where expr can be either data or another tree node. For example, we can represent (function1 (function2 expr2) expr1) as:

Also, this means that the function always comes first. If you want to add 2 and 3 in clojure, you’ll have to write (+ 2 3). This sounds contrived but we’re getting to why this works so well in an instant!

Two last things before we can parse our Collatz code snippet: #(function %) is an anonymous function, i.e. it is a function that applies function to its argument %. For example, #(+ 2 %) is a function that adds 2 to its argument. And map takes as argument a function and a list, and returns a list where the function has been applied to all elements. For example:

(map #(+ 2 %) (range 10))

> (2 3 4 5 6 7 8 9 10 11)

We can now parse our original code snippet:

(map #(if (even? %) (/ 2 %) (+ 1 (* 3 %))) (range 10))

map will apply the function defined within the #() to (range 10), which is a list of numbers from 0 to 9. The anonymous function tests if its argument is even. If it is even, it adds 2 to it. If not, it multiplies its argument by 3, then adds 1 to the result of that.

In tree form, this looks like this:

At this point, it is hard not to notice that the nodes of a tree are sometimes functions, sometimes data. This is the heart of the “code as data” paradigm!

Homoiconicity

We saw above that we can understand the construction of nested clojure expressions as trees, where (usually) the leaves are data, and the other nodes are functions. The functions are evaluated from the bottom-up and the result of the function’s evaluation is fed into the higher level of the tree.

So, we have data on some nodes, functions on the others, functions are evaluated, the program runs, and everyone is happy. But what if we had a way to block the evaluation of a tree branch, and instead of passing the result of the evaluation to the rest of the tree, we could pass the code itself to the rest of the tree? We could then manipulate the code data structure as we wanted!

It turns out that this is exactly possible, and that there is a way, in our Clojure trees, to pass up, not only lists like (1 2 3) or ("foo" "bar") but also to pass up expressions like (+ 1 2) or (map inc (range 10)), and to grab their elements, exactly as if these expressions were data lists. For example, I can grab the first and rest elements of a list:

(first (range 10))

> 0

(rest (range 10))

> (1 2 3 4 5 6 7 8 9)

So far so good. We can now unlock the homoiconic power of Lisp with the help of a tiny quote, ' placed before the expression that we want to treat as data:

(first '(range 10))

> range

(rest '(range 10))

> (10)

This means that we can now treat '(range 10) as data, and use all Clojure functions we want directly on this expression! This is the definition of a homoiconic language. But what is this good for?

Unlocking the Power of Homoiconicity with Macros

We have seen that in Clojure, code is stored in the same data structures as data. Using the quote ', we can prevent the execution of code branches in the evaluation tree, and thus manipulate these expressions as if they were data, to execute them later. We are now going to show the usefulness of this through an example.

Going back to the Collatz conjecture iteration:

\[\begin{eqnarray} f(n) =\begin{cases} n/2, & \mbox{if } n\mbox{ is even} \\ 3n+1, & \mbox{if } n\mbox{ is odd} \end{cases} \end{eqnarray}\]

The Collatz conjecture is that if you apply, sequentially, this transformation to your data enough times, all numbers will converge to 1. What is fun is that this conjecture seems to work for all numbers for which computers can simulate it, but that mathematicians can’t seem to rigorously prove that all numbers converge to 1. Hence the name conjecture.

Now imagine your job is to find sequences like Collatz’s sequence for potential convergences. You want to make your life as easy as possible. But your boss is a Lisp fan and forces you to use Clojure. If you want to test the application of several functions f1, f2, f3.. in a row to your initial data, the clojure syntax is a little burdensome:

(f1 (f2 (f3 ... fn (data))))

You’d rather not have to deal with counting and matching parentheses, so in your favorite language the syntax would look like this:

(mypipe data  f1  f2  f3 ...)

Macros to the rescue:

(defmacro mypipe
  [x & forms]
  (loop [x x, forms forms]
    (if (not forms)
     x 
      (let [form (first forms)
            threaded (list form x)]
          (recur threaded (next forms))))))

Once again the goal here is not to delve into Clojure syntax so I’ll be brief, but what this macro does is it takes our data x and a list of functions forms then recursively applies the first element of forms to x by building a list (list form x) then feeding that as our new data x to mypipe.

We can now do some serious collatz iterations by defining two little Collatz helper functions:

(defn col
  [x]
  (if (even? x)
    (/ x 2)
    (if (= 1 x)
       x
       (+ 1 (* 3 x)))))

(defn mapcol
  [xs]
  (map onecol xs ))

And we can happily write this horror:

(mypipe (range 10) mapcol mapcol mapcol mapcol mapcol mapcol mapcol mapcol
mapcol mapcol mapcol mapcol mapcol mapcol mapcol mapcol mapcol mapcol
mapcol)

> (0 1 1 1 1 1 1 1 1 1)

…which verifies Collatz’s conjecture, at least for numbers less 10!

Ok, I won’t lie: there are way better methods to do this in Clojure. But you get the gist: we were able to write our own little programming syntax in a couple of lines of code, due to the fact that we can manipulate the code tree in the same way as we manipulate data!

If you like this idea and want to dig deeper into Clojure, I highly recommend Clojure for the brave and true.

Haskell and math

Programming languages are usually thought of as a way to implement mathematical or numerical concepts. However, some languages, like Prolog or Haskell, have, for me, completely flipped that paradigm on its head. When I started learning Haskell, I was first amazed by how rigorous the language was, as well as by the very natural way the language adapted itself to the mathematics formalism I was so familiar with. I’ll illustrate this briefly by demonstrating Haskell’s powerful list comprehension syntax.

But Haskell is much more than that. Haskell is better at math that you are and trying to learn Haskell is much more like trying to understand set theory abstractions again than it is like learning a new programming language. Many Haskell programmers are drawn to these mathematical abstractions like flies to a flame. I’ll try to explain as plainly as I can the beginnings of category theory below, and show how category theory is elegantly implemented by Haskell’s type system. Unfortunately, plainly, in this case, means through math rather than analogies. Metaphors for Monads and Monoids abound but really, they are pure mathematical concepts, which can be best understood, in my opinion, by embracing their abstraction.

Rough category theory

A category is, very roughly, a collection of objects, and a type of arrows between these objects. For example, the category Set is the collection of sets, and the arrows are functions between sets. The category Grp has for objects groups (essentially a set that has an invertible operation such as addition or multiplication). The arrows for Grp are functions which preserve the operation: \(f(x * y) = f(x) * f(y)\).

Another category which will be less familiar to those with math backgrounds is Mon, the category of Monoids. Monoids are just a simpler group, with an operation that is not necessarily invertible.

These mathematical concepts are familiar and almost basic. The goal of category theory is to formalize the relationships within and between different categories. Functors, for example, are a concept in category theory that are somewhat similar to functions between categories.