A gentle introduction to functional programming

This year, I and several other folks at Tooploox decided to participate in Advent of Code. It’s a month-long challenge in December, in which each day you get a new exercise to solve.

To keep things interesting, each of us decided to use a language that’s new to us. This way we get a chance to try out things we rarely practice in day-to-day job. Plus we can discuss solutions, compare languages and generally have fun.

For me, the choice was quite obvious: since university, I’ve had a particular fondness for functional languages. I decided to use F#.

In this blog post, I’d like to describe how I arrived at my solution to (part of) the problem from day 16. It involved a couple of patterns that occur frequently in functional programming. I’ll introduce you to them as gently as possible.

What’s a functional language?

Like natural languages (e.g. English, Russian, Vulcan, Sindarin), programming ones have various flavours. Some of them are older, some newer. Some were developed early, and thus lack concepts present in newer ones. Some are more suited for solving a particular class of problems than others. Some are popular because they fit the current culture, some by chance. It’s hard to objectively say that one is better than the other.

Most contemporary languages are object-oriented, that is, they focus on nouns (objects) and approach problems by modelling how they interact with each other. Say, there’s a jungle, which is home to multiple gorillas and various species of trees, some of which have bananas. The jungle would be a container for all these objects, and things happening inside would be defined as methods on objects, like Gorilla#eat(banana). That method could somehow modify the jungle, to which a given gorilla belongs, to somehow show that total happiness increased (or count of bananas decreased).

In stark contrast, functional languages focus on verbs, which take objects as arguments and return other objects. The same scenario would be defined as bananaEaten(jungle, gorilla, banana) → Jungle, signifying that an entirely new state of the jungle is returned — one with more happy gorillas and fewer bananas.

This might suggest that functional languages forbid modification of objects, while object-oriented ones encourage it. Such notion is called pure language and is not true for most functional languages. That’s because banning modification incurs a high-performance penalty (and more generally, requires very different language design to enable efficient implementation of some algorithms). That said, most of the functional code is pure and uses mutation as a means of code optimisation (while keeping facade pure). A pure code is essentially a mathematical function, thus it can be reasoned about in a more structured way.

Why would you like functional languages?

Some languages strive to read like English, others try to be explicit. I’d like my ideal language to be easy to reason about. It’s the whole “simple vs easy” thing. Reading a code that looks like English might be easy, and knowing what it tries to do is easy, but truly understanding what it does is hard. A simple code, on the other hand, can be analysed. Even better, a pure code can be analysed using mathematical tools.

The weird corollary of mathematical approach is that many academics tend to prefer functional languages, and thus sheer amount of innovation in this field is staggering. Over the past years (decades even?), the trend has been to add features from functional languages into widely adopted ones, like C++, or Java.

One last thing is the approach to solving problems. A given language defines what tools you have at your disposal to solve everyday challenges. Every language provides a myriad of different opportunities, with some of them being provided as a language feature, and others via libraries. Some of these are more powerful, and some are less. Some make further code modifications easier or harder. Some make code harder to debug. Each day, you have to decide which tool should be used for a specific problem. I feel that overall trend in language design is to provide as powerful language features as possible, with little consideration as to how convoluted the code becomes (and dealing with that via design patterns). Functional languages tend to provide small, simple features out of the box, and depend on libraries to provide more powerful ones. “The Simplest Solution is Almost Always The Best Solution.”

What was the task?

As usual with Advent of Code tasks, the first part was simple enough: there is a circle of dancers, who follow pretty simple dance rules. Dancers always start in the same pattern, and a list of moves is given. The final pattern should be calculated.

The dancers are given single-letter names: from “a” to “p”. They always start in the circle, and their positions are indexed with integers.

There are three distinct moves that dancers follow.

First of them is called “spin”: it moves the whole circle counter-clockwise a given amount of positions.

Spin 4

The second move is “exchange”: dancers who currently occupy given indexes switch places.

Exchange 2/5

Third (and last) is “partner”: dancers with given names switch places.

Partner E/P

How can you solve it in the simplest way possible?

I started by defining a representation for dancers, and their moves:

array

F# has a couple of types that can be used to represent a circle of dancers. I decided that sequential representation with random access fits best

type

type in F# introduces type alias — a different name for the same type.

The starting position is a simple constant value:

let

let binds an identifier to a value. Similar to variables in other languages, but forbid redefinition — once you bind a value, you cannot bind another later. : explicitly states a type of expression — here, it signifies that value bound to “startingPattern” is of type Circle (which is an alias of char array). It’s worth noting that this is optional — F# uses type inference to automagically find out types of most expressions.

“Move” is simply a change (function) from one state to another.

Spin takes n elements from one end of the circle and moves them to the beginning.

fun

fun creates a lambda function (as Move should be a function). let can be also used inside expressions (in the form of let … in) to create temporary bindings.

I recommend using REPL integrated with an editor, like Emacs mode or Visual Studio Code extension. Using it, you can run the code while writing it, to easily debug small pieces of functionality.

“Exchange” has to first transform our sequential structure into a key-value map (which makes it easy to find elements by key and change values), and then key-value back to sequential structure (which involves sorting, to ensure proper order).

Partner is similar to exchange, albeit keys and values are now swapped (in “exchange”, indexes were keys and characters were values but in “partner” characters are keys and indexes values).

After adding some plumbing, we can check whether the answer we got is right:

The approach taken here is called “Shallow embedding”. It’s most often used to provide Domain Specific Languages inside host language. It can be applied to make a code readable for domain experts, and hide all the “plumbing”, like database access or transport medium. A more elaborate explanation can be found in short paper by Jeremy Gibbons.

So what is the hard part?

With the 1st part being that easy, surely the 2nd can also be done without much thought, right?

The second part is a simple modification of the first one: run it a billion times and provide a result. If running the whole dance routing took your program 1 millisecond, running the whole program will take around 300 hours. In my case, running 1000 examples took 40 seconds, which means the whole thing would take around a year to compute.

Of course, the code above is very inefficient. Because we create new circle after each move, we end up copying lots of objects, which is slow. F# is not pure, so we can instead modify objects to avoid this cost:

Now it takes 0.84s to run 1000 examples, meaning I could see the final result after 10 days. I’d have to find at least two more 10x optimisations to get results in reasonable time.

How did you solve it?

10x optimisations are quite rare and hard to find. So, instead of trying to optimise each move separately, a better approach is to look at the whole sequence, similar to compiler optimisations. In the next article, I’ll describe how that can be done in a systematic way so that finding the final answer is blazing fast, and how it all applies to real-life programming.