Learning to think Functionally

I’m learning Haskell.

Although I know other programming languages, I don’t understand the functional paradigm yet.

Learning Haskell is not just about learning the syntax. It’s about learning a new way of thinking about programming. To quote learnyouahaskell.com: “Learning Haskell is much like learning to program for the first time”.

I realised this when I tried to solve an informatics olympiad problem in Haskell. I found myself thinking in terms of what steps to take: first parse this list, then check for that, followed by adding up these numbers and finally comparing this to that.

That manner of thinking is better suited to imperative programming — where the code is a set of instructions that a computer must follow. This is the sort of programming people are usually more familiar with. The order in which the statements are performed and the state of the program matter in imperative programming.

In contrast to imperative programming, we have declarative programming, of which functional programming is a subset. Here the focus is on the logic of computation and not the control flow. In declarative programming the computer is simply told what it must do. How it actually does that, is not the programmer’s problem.

In functional programming for instance, most of the code might just be pure functions. These are functions that depend solely on the inputs and not any program state. So if you call say f(x) twice, it will give the same value both times because the value depends on only two things — f and x.

How exactly do you think functionally?

When we think imperatively, we are thinking about a series of steps to be performed. This was a trap I was stuck in while struggling with Haskell.

In order to gain some intuitions, I watched this lecture.

Some interesting takeaways:

• Learning a functional language without understanding the paradigm of functional programming will feel really clunky to use, as you will just be retrofitting your imperative ideas into functional code.
• Functional programming was initially more of a hype in academia than in the industry, but it seems that functional programming is really picking up in the industry and it might be very important for you to learn it.
• Object Oriented makes code understandable by encapsulating moving parts. Functional Programming makes code understandable by minimizing moving parts. The fewer things you deal with, the less you screw up.
• Functional: perspective of minimizing shared state. If the functions rely on nothing but the inputs, then they don’t need to be scoped. It also means the functions are reusable.
• In functional we can pass around functions and use higher-order functions.
• As time passes, programming languages handle more and more things for us. Even though this might mean less efficiency, fortunately computers are getting faster.
• Think about results, not steps. Think on a higher level about what you want to achieve. Find the appropriate higher order functions that provide the framework to achieve that.
• Think more about transformations, less about unique data structures or data types
• fold, filter and map are your best friends.
• Benefits of functional: code that is easier to reason about and easier to parallelize.

Results, not steps

My understanding of functional is that functional is about explaining what result you want in terms of things that the computer already knows how to do (the basic features that the language comes with).

What about complexity?

I still need a way to think about how to be functional that gives consideration to complexity (otherwise I’ll have no luck with informatics olympiad questions).

There seems to be a conflict here. We don’t want to think about what steps to perform. That’s imperative (skillful pun, reread until you get it). At the same time, in order to reason about complexity, we do need to think about which steps are being performed and how many times. It seems that in order to write performant code, we will need to think about the steps even though we don’t want to.

I realised that this conflict stems from my misconception that functional programming is a genie. It’s not. You don’t just make a wish and get it. It is still programming, and there are still tricks here and there that come from mastery. It’s just that you are operating on the level of what the computer should do, instead of the level of how the computer should do it.

Note that we’re not just telling the computer what we want. We cannot simply say “Build a general purpose AI”. The language will not have the required symbols to express that idea. We still have to break down what we want into sub-problems that can be expressed in the language. Note that those sub-problems are not steps, rather they will be an explanation of what it is that you wanted in simpler terms (eventually terms that are part of the language).

This choice of sub-problems is the task of a functional programmer. Different choices maximize for different goals (eg. performance, readability, maintainability, etc.). An imperative programmer also makes similar decisions and breaks code into sub-problems but with the additional task of specifying the steps to take and the order in which to take them, which functional languages take care of under the hood.

Also it’s not as if sub-problems are much higher level than steps. In both types of programming you still have to go down to pretty low-level generic tools like list manipulations, comparing elements, etc. This is another misconception that I had. So it’s not that declarative is drastically higher level than imperative. The benefits of declarative are elsewhere.

The next question is: how should one choose their sub-problems if their goal is performance? Just as in any programming, by exploiting mathematical truths.

A lot of optimisation in computer science looks like this: 1) Begin with a baseline solution, 2) realise a mathematical fact or pattern, 3) exploit that fact or pattern in order to improve performance.

So choose sub-problems in accordance to stricter mathematical conditions.

Example: Say you’re looking for primes.

You can explain this in the language as:

1. A prime is a number that is not divisible by any number less than itself, except 1.
2. A prime is a number that is not divisible by any number less than or equal to its square root, except 1.

Both are true. The first method of spelling out what a prime is, is closer to the definition of primes. The second is more efficient (if written into a functional language) perhaps because it uses an additional fact and is a stricter mathematical fact.

I think that gives me a few things to think about as I continue to learn Haskell and attempt to solve problems with it. This post does not intend to teach you functional programming on its own, but hopefully it has provided some thinking tools and raised your consciousness to some concepts central to functional thinking.

I am by no means an authority on this topic, but I think there is great value in documenting misconceptions and the struggles of learning.