# Functional Programming - The Simple Version

#### Muhammad Tabaza

CTO of PragmaI think functional programming (FP) has become a necessary skill to have for any software developer or programmer in general. Considering the tools used in industry today, like React.js, Elm, and all the popular functional languages, you donâ€™t want to miss out on all the awesomeness. Despite the fact that you need a certain level of understanding of functional programming in order to be proficient in use of these tools, understanding of the general concepts of FP can make you a much better software developer in general. Plus, a lot of frameworks and programming languages that arenâ€™t considered functional actually have functional features. Python, JavaScript, Java, C#, Dart, and many other languages have quality of life functional features that can save you a lot of time and headache if you know how to use them properly.

If you look carefully at these tools, you notice a lot of underlying concepts that are common to all of them. Having a solid understanding of the fundamentals on which these tools were built can carry you much of the way towards mastering them, and certainly makes your life easier when learning to use new tools (and judging them.)

In this article, I attempt to explain the basics of FP using Haskell. Donâ€™t worry if that sounds scary, itâ€™s really simple stuff.

## Functions!

If you squint hard at any computer program, you notice that itâ€™s essentially the following:

Itâ€™s a process that you feed data, and outputs something. The input can be anything from user clicks, to command line arguments, and the output can be a file, or search results.

Thereâ€™s a really simple way to express this notion of transforming input to output: mathematical functions. If you already have a good understanding of functions, I can understand why you might be skeptical of the idea that any program can be modeled as a mathematical function. Youâ€™re right, a function canâ€™t be used to model writing a file to disk. However, functions are the simplest way to model data transformations, which make up most of our programs..

You may have learned about functions in programming. When Iâ€™m talking about functions, I do not mean â€ścustomizable and reusable pieces of code.â€ť What I mean is way simpler than to print something to the screen, or to change the value of some variable outside of it. If youâ€™re not familiar with mathematical functions, let me explain.

A function in mathematics is a relation between two sets A and B, such that every element in A is associated with one and only one element of B. Sounds complicated? This might help:

In essence, a set is a collection of unique elements. In this example, we have two sets: Names (with a capital N,) and Lengths (with a capital L.) These two sets are related in the sense that every name has a length (the number of characters in it.) Since every name is associated with only one length, we can call this relation a mathematical function. Letâ€™s call this function `length`

.

Functions can be thought of as mappings between elements of sets. In length, the element â€śJohnâ€ť is mapped to 4. We note this mapping as *length(â€śJohnâ€ť)=4*, which in plain English translates to: length of â€śJohnâ€ť equals 4. We can also say that *applying* `length`

to â€śJohnâ€ť yields 4.

A value passed to a function as input is called an *argument* of the function. When a function is applied to an argument, the result is called the *image* of that argument, and the argument itself is called the *preimage*. In `length`

, the image of â€śJaneâ€ť is 4.

Notice how the mapping has a direction: it goes from Names to Lengths. More generally, we call the â€śoriginalâ€ť set the *domain* of the function, and the set to which the elements of the domain are mapped the co-domain. For `length`

, the domain is the set Names, and the *co-domain* is the set Lengths.

You can type the expression `length("John")`

into a Haskell REPL (GHCI) and hit Enter to get the result. A REPL is just a program that reads, evaluates, and prints the result of expressions you give it. Feel free to try running any code you see in this article after installing Haskell.

Any function can be expressed as a set of pairs. Each pair in this set consists of a value from the domain, and its corresponding image in the co-domain. Our little `length`

function can be expressed as:

where all the elements between the brackets (`[]`

) form a set. In programming (inconveniently,) it is not necessarily the case that all the pairs that form a function are known before executing it. Imagine a function from the infinite set of integers (â„¤) to the infinite set of real numbers (â„ť.) How can we possibly fit all the pairs that form this function in the finite memory of a computer? Stay tuned.

I guess itâ€™s appropriate now that I define functional programming. FP is using mathematical functions as the primary building block of programs. In other programming paradigms, the primary building block would be instructions, or objects. Using functions instead gives you some superpowers that are beyond the scope of this article, but theyâ€™re very simple, which is a huge plus.

### Equations

Earlier I implied that in programming, we normally donâ€™t know all the pairs of preimages and images that form a function. Most of the time, we canâ€™t even write these pairs down because there are so many (possibly *infinitely* many.) Consider a function that maps an integer to its increment (the number + 1.) This function is impossible to write out as a set of pairs because the integers never end.

In such cases, we can express the function as an *equation*. A formula that the *computer* can use to *compute* the image of a given argument. In the case of our increment function, writing the equation isnâ€™t very difficult:

This equation is read: â€śthe increment of *x* is equal to *x* + 1.â€ť Isnâ€™t it wonderful! Instead of writing out the mapping with *concrete* arguments in this form:

We can *generalize* the formula to work with any given integer by making the argumentâ€™s value unknown in the equation, making it a *parameter*. The image of a particular value can be computed by applying the function:

This expression will yield `61`

(the image of `60`

.)

In Haskell, you actually donâ€™t need parentheses in function definitions and applications. You can use spaces instead:

We can call function definitions *equations* in Haskell because the two sides are literally equal. You can take out any application of a function and put the evaluated right-hand side of the function equation in its place, and you would get exactly the same result. The same can be said for any Haskell expression. Think of it as being able to take out `250 * 2`

and placing `500`

instead of it. This property is known as *referential transparency*, and it just makes programs much easier to think about.

## Function Types

Remember what I said about mapping having a direction? Letâ€™s take a closer look at our increment function. It is a function that maps the elements of the set of integers (â„¤) to the set of integers + 1 (also â„¤.) In mathematics, this direction is noted as â„¤ â†¦ â„¤. In Haskell, we think a lot about the *types* (basically sets)of data that we operate on. There are many predefined sets already built into the language, such as `Int`

for integers, `Float`

for floating-point numbers, `Bool`

for `True`

and `False`

, and `String`

for text. But functions have types of their own. A function going from integers to integers has the type `Int -> Int`

.

When defining a function, it is almost never necessary to explicitly specify its type. The Haskell compiler can figure the type of the function on its own by looking at how the functionâ€™s parameters are being used. Adding type annotations makes it easier for you to just look at the functionâ€™s name and type (its *signature*) and immediately have a good idea of what it does.

The definition of `increment`

with explicit type annotations is as follows:

Now you can read this definition as: â€ś`increment`

is a function from `Int`

to `Int`

; the increment of an integer x equals x + 1.â€ť

When writing Haskell code in a file (not in the REPL,) you can write the type annotation on one line, and the actual function definition on the next line. This makes it possible to omit the semicolon (`;`

.)

Looking at our definition of `increment`

with the eyes of a lazy programmer, I can see a small problem: it can only be used to increment integers. Wouldnâ€™t it be great if the function could be applied to arguments of any numeric type? It would make sense for us to use the same function to increment floating-point numbers too, right? Coming soon.

### Functions of Multiple Parameters

Letâ€™s say we want to define a function *f* that takes two integer parameters: *x* and *y*. The function squares *x* and adds it to *y*. This is how it would look in Haskell:

Simple enough. Now you can apply f to two space-separated arguments:

which yields `7`

. Great! Now on to the weird part.

If we were to redefine `f`

with type annotations, it would look like this:

Thatâ€™s strangeâ€¦ Look at the type of `fâ€¦`

Itâ€™s `Int -> Int -> Int`

! Why is that? Shouldnâ€™t it be `(Int, Int) -> Int`

since it takes a pair of integers and maps them to a single integer? And what does it mean to have two arrows in a functionâ€™s type anyway?

This weirdness is a consequence of a concept called *currying*, which Iâ€™ll explain when it becomes useful.

Letâ€™s take a break from types for now. In order for the rest of the concepts Iâ€™d like to explain to make sense and feel useful, I feel it is appropriate to take a look at a very important data structure first: the list.

## Lists

When you have a number of related data points that you would like to process together, itâ€™s a good idea to store them in some sort of container that preserves their structure, and gives you some tools to help with your processing task. *Lists* are great data structures that do just that. They can be used to store data in an ordered manner, in the sense that the first element in the list comes before the second element, and the second comes before the third, and so on. Lists also let you easily walk through all the elements within them, transform them, filter them, and aggregate them.

Letâ€™s define a list of the integers from 1 to 5 and name it `oneToFive`

:

Youâ€™ll notice that the type of `oneToFive`

is `[Int]`

(read â€ślist of `Int`

.â€ť) We can construct lists by using square brackets (`[]`

) to surround the comma-separated elements of the list. This is awesome! Letâ€™s see what we can do with this list.

In Haskell, there are lots of predefined functions that operate on lists. One of these functions is `head`

, which maps a list to its first element. For instance:

would yield 1 (the first element of `[1,2,3,4,5]`

.) Another function is `tail`

, which maps a list to its self, but without the head:

will yield `[2,3,4,5]`

(`oneToFive`

without `1`

, the first element.) A list can be pictured as a snake, even though this is not a perfect analogy â€” snakes canâ€™t regrow their heads:

Take the listâ€™s head, and youâ€™re left with its tail. A listâ€™s tail is a list itself, so it has a head and a tail. Take the listâ€™s tailâ€™s head, and you have the second element (2.) Take the listâ€™s tailâ€™s tailâ€™s tailâ€™s tailâ€™s head, and youâ€™ll get 5:

How fun. What about the head of an empty list? Well, it doesnâ€™t exist, so you canâ€™t get it. The same goes for the tail of an empty list. Now, let us think for a moment about the tail of a list with one element. Thatâ€™s tricky, but letâ€™s reason about it this way:

If we have a list of five elements, then its tail should have 4 elements (5 minus the head.) So we can say that the length of the tail is the length of the whole list minus one. But it doesnâ€™t make sense for a list to have a length less than 0 (being empty,) so the base case, or the most basic case for a list, is to be empty. So it makes sense for the smallest possible tail to be the empty list.

If we have a list of five elements, then its tail should have 4 elements (5 minus the head.) So we can say that the length of the tail is the length of the whole list minus one. But it doesnâ€™t make sense for a list to have a length less than 0 (being empty,) so the *base case*, or the most basic case for a list, is to be empty. So it makes sense for the smallest possible tail to be the empty list.

Other than using square brackets to construct lists, you can use the colon operator (`:`

, a.k.a. the construction operator) to stick a head to a tail, therefore constructing a new list. For example, `oneToFive`

can be defined as:

The expression is evaluated from right to left. Weâ€™re sticking `5`

to `[]`

, `4`

to `[5]`

, 3 to `[4,5]`

, `2`

to `[3,4,5]`

, and 1 to `[2,3,4,5]`

, thus getting `[1,2,3,4,5]`

. Using this notation, itâ€™s clear how the smallest possible tail of any list is the empty list (`[]`

.) Without it, you wouldnâ€™t be able to construct any list, because you wouldnâ€™t be able to â€śend the cycle.â€ť This brings us to a very important concept in functional programming: *recursion*.

## Recursion

A list can either be empty (`[]`

,) or it can consist of an element `x`

stuck to the beginning of a list (`x : aList`

.) Do you notice anything weird about this definition of a list? Weâ€™re defining a list in terms of its self. It makes complete sense when you think about it. There are only two possible ways a list can exist: either as the empty list, or as a construction of a head and a tail list. The key here is that in a construction of a head and tail, the tail can be any list, either empty, or a construction of its own.

Letâ€™s try to define a function that maps a list to the count of its elements. Letâ€™s call it `count`

.

This function should have one parameter: the list of elements we want to count. A list can either be empty, or a construction of at least one element (a head,) and a tail. These are the only two cases we have to deal with since the function only has one parameter, which is a list.

The first case is that of an empty list. Easy, an empty list has zero elements:

The second case is that of a construction. Hmmâ€¦ A construction consists of a head (1 element,) and a tail (a list of unknown number of elements.) Ok, so the count of the elements in a construction is 1 + the count of the elements of the tail. Waitâ€¦ Letâ€™s write that down:

where `h`

is the head, and `t`

is the tail. Together with the empty list case, the whole definition would be:

Now thatâ€™s just magical. If whatâ€™s going on is not obvious, maybe this will help:

Earlier I explained how functions are equations. We can use this fact to understand how `count`

works by applying it to some list (e.g. `oneToFive`

,) and walking through the evaluation of the result one step at a time.

Again, notice how the evaluation would never have ended successfully without a base case (count `[]`

.)

In general, recursion is defining something in terms of its self. Data structures can be recursive; functions can be recursive; relations in general can be recursive. Youâ€™ll find that thinking recursively can make things a lot simpler sometimes.

You may have learned about loops in programming (e.g. `for`

and `while`

loops,) and you may be wondering why you would ever use recursion. Well, one reason is that Haskell and some other functional languages donâ€™t have any looping constructs built into them. Another reason is that using recursion lets you use the equational reasoning we applied earlier when evaluating `count(oneToFive)`

in all sorts of situations, saving you some brain power. Most importantly, though, I think recursion makes it easy to describe things clearly and concisely, which results in more understandable code.

### Higher-Order Functions

Yet another scary term.

Letâ€™s imagine a scenario where you have a list of integers, and you want to increment each of them. You define a function `incrementAll`

that does just that:

Easy. To increment all the elements of an empty list, you do nothing with it. To increment all the elements of a construction, you increment its head, and stick it to all the incremented elements of the tail. Great. You later require a function to decrement all the integers in a list, so you define `decrementAll`

:

Later, you require another function to multiply the integers by two, so you define `doubleAll`

:

â€¦ Thereâ€™s a problem here. Weâ€™re duplicating a lot of code, which quickly becomes boring. If you look at these three functions, you notice theyâ€™re essentially the same function, but they map the elements of the list differently. All three walk through the list recursively, and transform its elements using some function (e.g. `increment`

.) How do we solve this problem?

Remember what I said about functions having types of their own? Functions can be divided into sets. Thereâ€™s the set of functions from integers to integers (`Int -> Int`

,) the set of functions from lists of integers to integers (`[Int] -> Int`

,) and so on. We can think about a function as we would an integer; we can pass an integer as an argument to a function, right? Why not do the same with functions?

Letâ€™s define a function `transform`

that walks through a list, and transforms each element using a function `f`

that we pass as an argument:

Looks awfully similar to the previous functions, but with the extra parameter `f`

. What weâ€™re doing here is that weâ€™re leaving the function used to transform the elements up to the user of `transform`

. All we do in `transform`

is traverse a list, and apply a given function `f`

to its elements. Letâ€™s try using it with `increment`

and `oneToFive`

:

yields `[2,3,4,5,6]`

. Awesome! Note that `increment`

and `oneToFive`

are both arguments of `transform`

. We are not applying `increment`

to `oneToFive`

. Now letâ€™s try `transform`

with `decrement`

:

yields `[0,1,2,3,4]`

. It works! We can do the same with `doouble`

, but you get the point. `transform`

can be used with any function as long as its type is compatible with the type of the elements of the list.

A higher-order function is simply a function that takes a function as an argument. So `transform`

is a *higher-order function*. Many of these functions are available in Haskell by default. For example, filter can be used to filter a list:

This will filter the even numbers in `oneToFive`

and yield `[2,4]`

. `even`

is a simple function that takes an integer, and yields `True`

if itâ€™s even, and `False`

if it isnâ€™t. The `filter`

function uses the function you pass it to test the elements of the list, and keeps the elements that pass the test.

Another popular function is `foldl`

(short for â€śfold left,â€ť) which â€śfoldsâ€ť a list as if folding a long piece of cardboard starting from the left and reducing it to a small piece. For example, we can use `foldl`

to find the sum of all the elements of a list of integers:

yields 15. `foldl`

takes three arguments: the function used to calculate the result of every fold, the initial value to start folding with, and the list to fold. This is a bit abstract. If you know about `for`

loops, you can think of `folds`

as loop iterations, where in each iteration, you change the value of some accumulator. In the case of folding a list of integers to find their sum, the accumulator would be the sum, which starts at zero, and then increases with every number you pass in the list to finally be returned as the sum of all the numbers in the list.

Notice thereâ€™s something peculiar about the function we passed to `foldl`

. As the function used to calculate the accumulator in each fold, we used `(+)`

. This is possible because operators in Haskell are really just functions of two parameters. To multiply two integers, you pass them as arguments to the `(*)`

function:

both yield `8`

.

Higher-order functions arenâ€™t limited to lists. They can be used in all sorts of situations (e.g. asynchronous programming,) and they are a good tool for abstraction. We can generalize a formula by making some part of it unknown, and allowing it to be passed as an argument.

Weâ€™ve gone through many concepts so far. Weâ€™ve built a pretty good intuition about functions, and weâ€™ve seen how powerful they are. Weâ€™ve also discussed types briefly, but now Iâ€™d like you to run these lines in the REPL:

Take a quick look at the result of each of these. `:t`

is a command you can use in the REPL to get the type of an expression. But whatâ€™s with these types? There are lots of `a`

â€™s and fat arrows (`=>`

.) What do they mean? And the question about multiple arrows in the types of functions of multiple parameters remains unanswered! What have we been doing all this time!

## Currying

The result of `:t f`

is `Int -> Int -> Int`

, which is strange. The result of `:t (f 2)`

is `Int -> Int`

, which is even stranger. Doesnâ€™t `f`

take two arguments? Well, thatâ€™s the key: `f`

takes two arguments, but `(f 2)`

is another function that takes only one:

both yield `7`

. You can even assign a name to `(f 2)`

:

Now `g`

is a function just like `(f 2)`

. It takes one integer argument, and yields an integer, so `g 3`

will yield `7`

. Since weâ€™re applying `f`

to only one argument, the value we provide will be used in place of the first parameter (`x`

.) The resulting function takes the one remaining argument (`y`

,) and finally yields an integer.

Currying (named after Haskell Curry) is making a function yield another function when itâ€™s not applied to enough arguments. If a curried function takes 5 arguments, applying it to 3 arguments will yield a function that takes 2 arguments. In Haskell, all functions are curried, which allows us to write more concise code. For example, instead of writing a function that sums the elements of a list as:

we can just write:

Since `foldl`

takes 3 arguments, and weâ€™re applying it to 2 arguments, it will yield a function that takes one argument (the last parameter, a list,) and finally yields the sum.

Another example would be to use curried functions as arguments to higher-order functions. Remember `transform`

? Thereâ€™s actually a function just like it already defined called `map`

that transforms every element of a list using some function you pass:

will yield `[2,3,4,5,6]`

. The addition operator is a function, though, and all functions are curried. So we can apply `(+)`

to one argument, and get a function that takes one argument. So `increment`

can be rewritten as:

which is cool. But now we donâ€™t really need `increment`

since we have a clear simple way to get a function that increments a number. So a function `incrementAll`

that increments all the elements in a list can be written as:

This works because `map`

has two parameters (a function and a list,) and weâ€™re only applying it to one argument. This is just beautiful.

Alright, weâ€™ve discovered the secret of functions of multiple parameters. Now, letâ€™s answer the question about all the aâ€™s and bâ€™s in types like `:t map`

:

## Parametric Polymorphism

What a tongue twister.

In previous sections, we looked at cases where you can generalize a definition by making some part of it unknown. Types are no different; if you take a look at the list type `[]`

you might notice that itâ€™s missing something: the type of elements within it. In order to create a list, you must make it a list of something, so you can think of the list type as a function on the type level that has a type parameter. So to construct a list type that has elements in it, you must pass some type to `[]`

. The type `[Int]`

is `Int`

passed to `[]`

as an argument. Because `[]`

itself isnâ€™t a complete type and it has a type parameter, it is called a type constructor.

Because a list can come in many forms (e.g. `[Int]`

, `[Float]`

, and `[String]`

,) we say itâ€™s *polymorphic*. Since the type argument is the part that varies among lists, we say itâ€™s *parametrically polymorphic*.

The same idea applies to functions; in `:t map`

, the type of the list doesnâ€™t matter, because the operations we perform on the list require no knowledge of the type. That is why you see `[a]`

and `[b]`

in `:t map`

. Both `a`

and `b`

can vary between different applications of `map`

, which is why theyâ€™re called type variables, and `map`

is called a `polymorphic function`

. For example:

Here, `a`

is `Int`

, and `b`

is `Int`

. So `map`

has the type:

This also shows that `a`

and `b`

are not necessarily different types. Hereâ€™s another example:

Here `a`

is `String`

, and `b`

is `Int`

. So the type of `map`

is:

This polymorphism becomes really useful when you want a function or a type to work with multiple types. If you were defining a list data structure, you shouldnâ€™t care about the type itâ€™ll be used with, because you would want it to be usable with any type. Itâ€™s also great that the Haskell compiler can figure out types on its own, so you donâ€™t need to think about it too much. Simply define a function, and look at the type that the compiler has given to it, itâ€™s usually the most generic type possible.

## Type Classes

Check out the type of `(+)`

:

Ok, we understand from `a -> a -> a`

that itâ€™s a function that takes two `a`

's and yields an `a`

. But whatâ€™s with the `Num a =>`

at the beginning?

Imagine youâ€™re defining the `(+)`

function. Would you want it to be usable with any type? I think not. You would want `(+)`

to be usable with types that have properties of numbers (or I hope so, at least.) Thatâ€™s what the `Num a`

is for. It limits `a`

to types that are number-like. But what is `Num`

?

In order for something to be number-like, it has to support some operations like addition (`+`

,) multiplication (`*`

,) and a few others. If a type can be operated on using these functions, we consider it number-like.

In Haskell, you can define a *type class* containing the specification of functions that a type needs to support in order to be considered a member of some class of types.

The definition of the `Num`

type class looks like this:

Some of the functions every `Num`

has to support arenâ€™t concretely defined inside the type class. Functions like `(*)`

and `abs`

are left up to the author of `a`

to define, so only their types are specified. Other functions like `(-)`

have a default concrete definition, given by `x â€” y = x + negate y`

, so the author of `a`

needs only to define `negate`

for `(-)`

to become available.

Letâ€™s define our own type class called `FillStatus`

. Any member type of `FillStatus`

must support a function `isEmpty`

that tells us whether the argument is empty or not:

So `isEmpty`

takes an `a`

and returns a `Bool`

(`True`

or `False`

.) Now letâ€™s make lists satisfy the requirements of `FillStatus`

by defining an instance of `FillStatus`

for `[a]`

:

The definition of `isEmpty`

for lists is pretty straightforward: a list is empty if itâ€™s the empty list (`[]`

) and itâ€™s not otherwise (thatâ€™s what the underscore means.) Awesome! Now `isEmpty []`

yields `True`

, and `isEmpty [1,2,3]`

yields `False`

!

We can provide an instance of `FillStatus`

for any type we want (as long as it makes sense.) Type classes are similar to interfaces in other programming languages like Java, but thereâ€™s a key difference between the two: you donâ€™t need to specify which type classes a type belongs to while defining it. `Int`

is already defined, and we can still create an instance of `FillStatus Int`

without modifying the definition of `Int`

.

## Conclusion

Weâ€™ve looked at many functional programming concepts in this article. However, this is by no means a comprehensive explanation of FP or Hakell. It is an introduction and a quick overview. After understanding the contents of this article, you should be able to read a lot of Haskell code, and write code in a functional way. I havenâ€™t mentioned things like state, Haskellâ€™s relationship with category theory , or even fundamental things like anonymous functions because this article is long as it is. But Iâ€™ll be writing more in the future.

I really hope you found this helpful. If you did, consider following Pragma and myself here on Medium and on Twitter @Tabz_98 and @pragmalang for future content.