The essence of functional programming

2019/02/08 — Mikaël Mayer.
This article requires readers to be familiar with the notion of functional programming. It is written in Elm. If you prefer Haskell, you can also read the Haskell version of the article.

Programming is an art. There are many ways to achieve the same purpose. In this article, I will informally review some of the common idioms when it comes to chaining operations on data.

Let us look at the following function in Javascript. It converts the input using three converters: convert might return null, convert2 always succeeds, and convert3 might return null. convertData returns either an error or a result:

From imperative to pattern matching

To rewrite convertData to a functional language, such as Elm, we first assume the following type definitions for the functions convert, convert2 and convert3: Now we can rewrite convertData using pattern matching:

From pattern matching to monadic style

However, besides type-checking, pattern matching does not provide that much benefit. For example, we still have intermediate names. To avoid intermediate names, we can re-write our function in a monadic style (press Next> to view the refactoring step by step): The operator |> passes the computation to its left as the last argument of the expression to the right, and the operator >> composes functions such that the function on its left is executed first.
This formulation is useful, because now we don't need to name intermediates, we can just chain functions.

From pattern matching to continuation-passing style

There are several drawbacks to the monadic approach. First, compared to pattern matching, it reports problems at the end and in reverse order, which is not intuitive. Second, it still needs indentation that will increase if we add conversions, which we did not need in the JavaScript imperative version.

Fortunately, there is another way to express the initial chain to catch early errors, using the Maybe.fold operator:

Using Maybe.fold, let's start over from pattern matching and express convertData in another way:

<Previous—Next>Last>>

It might seem that we cannot refactor further. Fortunately, we can define with that transforms function application to callback style:

so that now we can continue the transformation:

<Previous—Next>Last>>

The operator <| passes the expression at its right (in our case, always a callback) as the last argument of the expression to its left.
In general, callbacks have also the advantage of being immediately compatible with asynchronous computations.
Moreover, what if convertData also accepted a callback as the first argument? Then we would be able to express it concisely as well.

<Previous—Next>Last>>

The operator << composes functions naturally, meaning (f << g) x = f (g x).

At this point, it's normal to pause and marvel a bit. We use the operator << which is normally used to chain functions from right to left, that is,
(f << g) x = f (g x). In our case, because they are callbacks, the chaining makes the callbacks to be executed left to right, because
(f << g) callback x =
(f <| g callback) x =
f (g callback) x =
f (\y -> g callback y) x
which guarantees that g is executed with the result of f, not the other way round.

Non-linear workflows

The previous style is great, but what if we need to refer to some of the intermediate results to parametrize a further computation? Although named disappeared, it's possible to reintroduce them.
Suppose that the new signature for convert3 is the following:

<Previous—Next>Last>>

Because of the callback-style workflow, it would be natural to write:

<Previous—Next>Last>>

However, it is hard to see how to reduce that further, and remove the b after parentheses. Looking closely, we see that the callback is in any case applying b to some function. This means we can give a name to this construct. Let us introduce the nameIt operator that builds a callback by applying the value twice to it:

Now, the workflow can be rewritten:

<Previous—Next>Last>>

To fully get rid of the callback argument, we would have to make nameIt accept it as second argument:

Thus the final function becomes:

<Previous—Next>Last>>

Because << has higher precedence over <|, we cannot remove the final parentheses. So choosing the earlier "<|" version vs. the "<<" version just above is a matter of taste.

Epilogue: Towards Church encoding

It is surprising that, using default operators such as <<, we obtain a code as concise as the imperative style, with error catching in the correct order.

In his minimalistic functional language where only functions are values, Church naturally encodes datatypes Maybe and Result as continuation passing style.
Therefore, a Just x becomes a (\onNothing onJust -> onJust x), whereas a Nothing becomes a (\onNothing onJust -> onNothing).
Continuation-passing style is therefore not something new, but the ancestral way of writing functional code.

The inspiration of this article came from the build file itself I used to build this blog (here and here).

---

This work was supported by Swiss National Science Foundation Early Postdoc.Mobility Fellowship No. 175041