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.
always succeeds, and
might return null.
returns either an error or a result:
From imperative to pattern matching
to a functional language, such as Elm, we first assume the following type definitions for the functions
Now we can rewrite
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):
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.
Fortunately, there is another way to express the initial chain to catch early errors, using the
Maybe.fold, let's start over from pattern matching and express
convertData in another way:
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:
<| 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.
<< 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.
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:
Because of the callback-style workflow, it would be natural to write:
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:
To fully get rid of the
callback argument, we would have to make
nameIt accept it as second argument:
Thus the final function becomes:
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
Result as continuation passing style.
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