What is functional programming?
Tags: functional, programming, paradigms
Published: 2022-08-02 17:26:20

I'm planning on doing a couple of posts on the language Elm and why it may be better than JS, but to fully understand what happens in Elm you need to know some things about the **functional paradigm** - a clean view on what programming is, designed with mathematical perfection.

### Functions
###### Functions everywhere.

As the name implies functional programming is all about functions. Everything is done using them, and applying the function to a parameter is the fundamental operation. In imperative languages like Python, C++ or JS, to apply a function `foo` to `x` you use parenthesis: `foo(x)`, but in functional languages it's sufficient to write the function next to the value: `foo x`. Parenthesis come up when applying a function to another function's result. For a bigger example:
```python
# Imperative:
foo(x, bar(y), baz)
```
vs.
```
-- Functional:
foo x (bar y) baz
```
This syntax is cleaner and more readable when most of the program is function application: not even commas are required to separate arguments.

Everything in the functional paradigm is a function. Even normal operators like `+` or `*` are considered functions. In most functional languages you can put parenthesis around them and apply them like any other function:
```
(x + y) = (+) x y
(x * y) = (*) x y
```
Functions can be passed as arguments and assigned to variables. This allows for some powerful operators that I will discuss in later posts.

### Purity
###### No side effects allowed

Functional languages deal with **pure functions**, which are not allowed to alter any internal or external state. This means a pure function's output can only depend on its inputs, not on time of execution or randomness. It can also not affect outcomes of other operations in any way other than through returning values.

This may seem as overly restrictive: after all the screen is an external state, and how are we supposed to write an application that doesn't depend on time? Most functional languages have their mechanisms for dealing with those problems, usually behind the scenes, without introducing impurity to the programmer's code.

Purity has its benefits: a pure function for a given input will always return the same output, so there may not be a need to recalculate it later. The execution of a part of the program never depends on anything outside of it. This opens opportunities for optimizing compilation and makes thinking about code way easier.

### Strong Types
###### Like in C or Java, but good.

Another property of most functional languages is that they are **strongly typed**. What this means is that all data flowing through the program has to be assigned a type, like `String` or `Int` or `Float`. Every value traveling along some path in the program has to always have the same type.

In languages like C++ or Java this leads to a ton of unnecessary type annotations that are annoying and obscure the meaning of the code. In functional programs types can almost always be inferred from their surroundings, lifting the burden of attaching labels to everything from the programmer.

**Type inference** means that from knowing what type the basic literals are (like `21` or `"Hello"`), and what types the basic operators take and return the compiler can reason about types of other values and functions, in theory requiring almost no type annotations. It's still a good practice to annotate your function definitions so that the compiler can warn you when the type you want doesn't match what is inferred.

### Algebraic types
###### We need to go deeper...

In imperative languages data types reflect how a value is stored in computer memory: `int` is a four byte number, `string` is an array of bytes and `float` is a floating point number as described by [The Standard](https://en.wikipedia.org/wiki/IEEE_754). In functional languages data types reflect what the value represents. You have basic types that all have some implementation-defined representation in memory, but you can also define your own types, usually on top of existing ones.

Types are defined with constructor functions. For example `Boolean` may be defined as:
```
type Boolean = True | False
```
This means the `Boolean` type can be constructed by either `True` or `False` constructors. Neither of them take any arguments, so they always return the same values which can later be interpreted as "true" and "false". A more complex example that uses arguments is:
```
type Webpage
  = Loading
  | Loaded Html
  | LoadingError String
```
This represents the fact that a `Webpage` may be one of three:

* `Loading`, in which case no additional info about it is available,
* `Loaded`, in which case it has a value of type `Html` to display,
* `LoadingError`, in which case there's an error message available describing what went wrong. This allows for precise modelling of what your data means and can possibly be.

### Pattern matching
###### Elegant conditionality

Algebraic types naturally represent options available to a given value, so the most used conditional construction in functional programming is one that branches based on the constructor. The usual syntax looks like this:
```
case value of
  Some pattern -> result
  Other pattern -> different result
```
Going with the `Webpage` example we could construct a function that takes a `Webpage` value and returns a rendered view like this:
```
renderPage : Webpage -> Rendered
renderPage page =
  case page of
    Loading -> renderText "Loading..."
    Loaded html -> renderHtml html
    LoadingError message -> renderText message
```
This may be a bit to take in, so let's go through it line by line:

- `renderPage : Webpage -> Rendered`
  This is how type annotations look like for functions. `renderPage` is a function that takes a `Webpage` and returns `Rendered`.

- `renderPage page =`
  Start of the function definition. `page` is the function argument.

- `case page of`
  Start of a `case` expression.

- `Loading -> renderText "Loading..."`
  If `page` was made with the `Loading` constructor display the loading text.

- `Loaded html -> renderHtml html`
  If `page` was made with the `Loaded` constructor render it's parameter as HTML.

- `LoadingError message -> renderText message`
  Finally if `page` was made with the `LoadingError` then display the error message.

You can see how a `case` expression can be used to *deconstruct* the value and assign its contents to variables (`html` and `message` in the example). This way of branching can also make sure that the program *never breaks*, because every possibility has to be accounted for. Any errors have to be explicit (like `LoadingError` in the example) and passed around openly as values.

### Sidenote: Type theory
###### Very rough explanation.

Algebraic data types are such a powerful concept that you don't need any builtin types to make programs. You can define numbers and lists and operate on them without referencing any existing types. I have already shown the easiest example, the `Boolean` type, but let me explore this further.

The second simplest example is natural numbers. If you think about it, any natural numbers can be defined as either zero, or a *successor* of some other number. This translates to:
```
type Nat = Zero | Succ Nat
```
This type is defined recursively, which lets us define an infinite amount of numbers with a finite set of symbols. With this whenever you encounter a number you can split the logic into two `case`s: a simple one when the number is zero, and a recursive one when it isn't. For example addition would work like:
```
add : Nat -> Nat
add x y =
  case x of
    Zero -> y
    Succ x' -> add x' (Succ y)
```
When adding zero to `y` the answer is just `y`, and when adding a successor of something the `Succ` can be "moved" to `y`, decreasing `x` which guarantees that it finally reaches the base case.

As a closing remark I will add an example of a `List` type with a `map` function that transforms each element of the list. This example has some more advanced notation, so don't worry if you don't get it.
```
type List a = Empty | Cat a List

map : (a -> b) -> List a -> List b
map func list =
  case list of
    Empty -> Empty
    Cat head tail -> Cat (func head) (map func tail)
```

### Conclusion
###### I'm back to writing!

I hope this gave you a vague idea of what you could stumble upon when dealing with functional languages. If you want some more concrete and in-depth examples look forward to my series on the programming language Elm. I barely have any formal education in functional programming and category or type theory, so if you spot any mistakes please notify me in the comments. See you soon!