Composing with side-effects⌗

Now. If you have thought that the FP guys are crazy, hopefully you’re going to end up with a ton of evidence on your hands to finally lock us away into the depths of the abyss, where we truly belong. Or you might have discovered something new, interesting and useful, which, you know, is also good.

There are three things that make functional programming as functional as it gets (or not):

  • Immutability
  • Composition
  • Purity

Different languages tend to pull on those different things in different proportions. For example Lisp allows you to do side-effects and mutate variables. Clojure on the other hand is all about immutability. Haskell is about managing those side-effects and maintaining purity. And OCaml is like, let me just code the way I want: it can be highly functional and pure, but can also code loose and dirty, with mutation and in imperative style.

But then again, there are things that are really important across the languages: composability.

Hopefully from the previous experiences you’ve realized that the composability is a good thing and actually helps us to write simpler code: if you can actually write your code in terms of simpler functions that are composable, this is what you would do instead of writing a wall of code and keeping that state in your head all the time.

However, hopefully that you’ve also realized that composition works nicely if the functions are pure. To maintain some sense of purity, you need immutability: you can’t have values changing suddenly underneath you.

That’s why those things are important and why references are dangerous. If you don’t manage those things, then the simple act of composing will make the debugging difficult. You won’t be able to know what to trust, not much better than the imperative or OOP style.

So okay, you’ll try to keep your functions pure to keep them composable. But what if you have to compose functions that do have side-effects?

Well, luckily for you, there are people much smarter than you and I, who are paid to solve those kinds of problems, and their solutions are then integrated into languages or thrown to the side with many people not understanding why the hell do they need a PhD to write a "Hello World" to the console.

So we will start simple, and hopefully you’ll see the beauty.

Let’s take the simple act of getting an Nth element in the list:

def get_nth(l, n):
  return l[n]

Well, the code is simple, right? Time to go home?

There are obvious problems that you may also see: what if the Nth element doesn’t exist? Well, let’s strengthen our code:

def get_nth(l, n):
  if len(l) > n:
    return l[n]

Okay, now the function doesn’t raise an exception if the Nth element doesn’t exist. But what happens instead? If we try to use that element, we will get another type of exception: something to do with NoneType. How do you handle that?

At this point most people (including naive and young me) would just say “Fuck it” and code around this limitation, while keeping it in mind.

In the end, we have some specific goal in mind, not just a function that needs to access some Nth element. And so we would write around that limitation and we would achieve our goal.

And all would be nice if that was a throwaway script. However more often than not, the code would become a part of a critical infrastructure. A ton more code would be written on top of that code, making it more difficult and more dangerous to change the code.

My single F in the whole undergraduate degree came from the course where I had to choose an open-source project and contribute to it. I made a grave mistake to take my favorite Python project: Deluge. Needless to say, I couldn’t make head nor tail of the project, and so I didn’t do anything.

So, if the code is bad, it can get really bad. What would happen first is that you would write a solution for a specific situation. And then you would need to change it a little. And then a little more. Then you would encounter more and more problems, because you’re now breaking your invariants that existed only in your head (and not in your type system). And now simple code that resembled a “happy path” looks like an amalgamation of ifs, try/catch and many more. And still it is a highly brittle code, a.k.a. legacy code.

Now, the million-dollar question: why is that the case?

Well, we know that it wasn’t the case with pure functions. Pure functions can be substituted by a single value. We opened a pandora’s box when we tried to work with impure functions, or those that have side-effects that are unaccounted for.

On a side-note, the funny thing that would happen at this stage is that people would:

  • hear that the functional programming is well-equipped with solving those kinds of problems,
  • try out the FP concepts without understanding then
  • half-assing them
  • would make even more mess
  • and then say that it is bad

Unfortunately, there is some required background in CS. But more importantly, there’s a specific mindset that is required when doing functional programming. FP has tendency to push you towards the right direction, but without the understanding, it would be for naught.

But what would functional programmer would think when writing a code like that?

Well. The first thing is that the question would be: “Why are we writing a function that would need to access the Nth element?”.

And the answer is: “We don’t know”. In fact, this function is really generic. It can be used for any reason. It is the same question as to why you would use the word “long”? Of course, you would use it to say that something is long. But you could also say that something is longing for something.

You can’t just take the word and shoehorn it into a specific domain. In that way, you can’t just take a generic function and assign it implicit assumptions and hope that they won’t get broken, because they most certainly will.

Side-effects are those implicit assumptions. In our get_nth(l, n), the assumption was that n < len(l). We know that everything is going to work if the assumption is correct. The problem is that we don’t know what would happen if the assumption is incorrect. And usually what happens is the worst.

Usually it is very difficult to debug, because something that was deemed impossible happens.

For that reason when functional programmers write code, they write it with the idea in mind of what is it they are in fact doing. The reality is getting in the way. If the programming language has a strong and expressive type system, then basically programmers can write code as if they are writing a mathematical proof that their code is correct. If not, then, well, you deal with what you have and hope you have good discipline.

So, the question is, how do we deal with side-effects?

The answer is: head-on. Let’s make the side-effects explicit.

Again, there are several ways of doing what I am going to do, but what I’m going to show you is the poor man’s monads (yeah, those dreaded monads), so that in case of anything, you can at least manage to do something.

So, let’s get back to our example of get_nth():

def get_nth(l, n):
  return l[n]

So, in a good case, we have our value. But in a bad case we have to deal with it somehow. But we can’t give anything, because there’s nothing. So let’s give nothing.

def get_nth(l, n):
  if len(l) > n:
    return some(l[n])
  else:
    return none()

This is how the functional programmers would do it.

I’m pretty sure you’re interested in what some() and none() do. Well, they are simple, but it is not so much important as to what they are, but how they must be used.

Here are their definitions:

def some(x):
  return ('some', x)

def none():
  return ('none',)

Those are the simple tuples. We will keep our data structures simple.

What we did here, is (implicitly) defined our own type. This type is sometimes called Option, sometimes Maybe. But the idea is that this type represents two cases:

  • Something exists
  • Nothing exists

So, we can wrap the value into our Option type. To extract it, we can write an extractor:

def value_of(opt):
  return opt[1]

This would work as expected in case of Some:

print(value_of(some("There is some value!")))

However, we would have the same problem in case of None:

print(value_of(none())) # throws exception

So we came back to our problem.

At this point people would give up on FP, saying it is useless. But what can we do?

Well, it is clear that you’re not supposed to work with the underlying representation. First thing you can do is check if the value is Some:

def is_some(opt):
  return opt[0] == 'some'

Then we can try to extract value from Some:

def extract_value(opt, default_value):
  if is_some(opt):
    return value_of(opt)
  else:
    return default_value

This is better, because it forces us to come up with the default value in case the our option value is actually None. But this approach requires a discipline. You must use extract_value() whenever you’re working with Option types and not use the underlying structure. Also, it is not so easy to come up with the default value in each and every case.

There must be a better option. Instead of extracting the value from the Somes, let’s work on Options directly. Of course, we can write functions that are aware that their arguments are Option types, but it would quickly become difficult and unwieldy to manage.

Instead, we can write normal functions, and make them work with Option types.

We do this by the use of functors.

Now, another scary word.

When functional programmers say something is a functor, what they mean is that there’s an associated function map. And what they also mean, is that the function map has a specific type:

map :: (a -> b) -> f a -> f b

Now, you already seen this style of writing type signatures, but it may seem scary, so let me make it less scary.

The first (a -> b) is a function, so the first argument to map is a function. A higher-ordered function.

Now, what those f a and f b refer to? Well, the f in f a refers to functor. Basically a type for which map is defined. So map requires specific types for which that map is defined. Good? Good.

While it is sounds bad, another way to look at it, is that the map generates a specific type of functor, which is dependent on context.

In our case we have Option, so we could have written like this:

map :: (a -> b) -> Option a -> Option b

So now our function map takes some function from a to b and makes it a function that works on Option a and produces an Option b.

For example we can make the function len work on strings that may or may not exist:

map :: (String -> Int) -> Option String -> Option Int

That’s just one way to look at it.

Remember, there’s also a map in Python that maps each element in the list via f()? Well, now it is time to explain that.

The word map actually comes from the functor. map basically means functor. Functor is just some structure that has associated map function.

Python lists, turns out, are also a functor. For them the map function is defined as [f(x) for x in l].

But the reason why map is called map is because not the elements in the functor are being mapped, but because the normal function of type a -> b is being mapped to a function f a -> f b.

What we are transforming are not values but functions. Think about that.

Now, to be a valid map and functor, there is something called functor laws. But they are quite intuitive and not scary at all, so I won’t be covering them I’m already tired writing all this stuff.

So, the questions now is: how do we implement map for our Option?

def map_opt(f):
  def foo(opt):
    if is_some(opt):
      return some(f(value_of(opt)))
    else:
      return none()
  return foo

Quite a mess.

I mean Python.

But what is happening, is that we take a function f(), and if our value is Some(x), we extract that x, apply it to f() via f(x), and wrap it back into Some() via Some(f(x)). Otherwise, if it is None, we just pass along that None.

In OCaml this would have been written like this:

let map f opt =
  match opt with
  | Some(x) -> Some(f x)
  | None -> None

In Haskell this would have been written as (Some -> Just and None -> Nothing):

map f opt = case opt of
  Just x -> Just (f x)
  Nothing -> Nothing

Or even like this:

map f (Just x) = Just (f x)
map _ Nothing  = Nothing

Quite readable, compared to Python, isn’t it. But those codes are equivalent, I assure you.

Now, with this, we can make a function len that works on Options:

len_opt = map_opt(len)

To check that it works, we need to additionally convert our Option to string:

def string_of(opt):
  if is_some(opt):
    v = value_of(opt)
    return "Some({})".format(v)
  else:
    return "None"

And now:

print(string_of(len_opt(some("Hello World!")))) # prints "Some(12)"
print(string_of(len_opt(none(              )))) # prints "None"

What we did might not seem much, probably because it is simple. But what is important, is that we have defined functions that work despite the presence of side effects.

If we tried to take the len() of None directly, I’m personally not sure what would happen, because I don’t want to learn Python, but I suspect that the exception would happen.

However, with len_opt() we have made a total function: that works in every case. And that is actually very powerful idea. We now don’t need any try/catch. The code just works.

Ain’t that amazing? Eh?

Now, with this out of the way, let’s cover something else: Applicative Functor.

Another scary term, but it is actually quite simple.

Let’s take a look at the map type signature:

map :: (a -> b) -> f a -> f b

And also let’s take a look at add:

add :: Int -> Int -> Int

Now, the question, what would happen if we give add to map?

map add :: Option Int -> Option (Int -> Int)

How did this happen?

Remember that the type of add is Int -> Int -> Int. If we try to match it with a -> b, then a == Int and b == Int -> Int.

What this means is that we accidentially put a function inside a functor, instead of a value. What this means for us is that we can’t simply apply values to those functions.

So Applicative Functor solves that specific problem: applies values to a function inside a functor. Here’s the type signature for apply:

apply :: f (a -> b) -> f a -> f b

That’s basically it.

In case of an option we can easily write one such apply:

def apply_opt(opt_f, opt_a):
  if is_some(opt_f):
    return map_opt(value_of(opt_f))(opt_a)
  else:
    return none()

This works because we first check if the opt_f is actually Some(f), and if it is, then we just convert our a -> b to f a -> f b with map, and then apply f a to it. If it is None, then it is, well, None.

Important note is that this apply function works with curried functions (you still remember what curried functions are, right?).

So if we have our add function, this is how we would make it work with Options:

def add(a):
  def foo(b):
    return a + b
  return foo

add_opt = map_opt(add)

one = some(1)
two = some(2)

print(string_of(
  apply(add_opt(one), two)
))

This doesn’t look so nice, because it is, well, Python (I feel tired of mentioning and apologizing for Python at this point).

In functional languages like Haskell and OCaml you can define your own custom operators, and in those languages they define apply as such:

(<*>) = apply

add x y = x + y

add_opt = map add

one = Just 1
two = Just 2

(add_opt one) <*> two

In fact, they define a custom operator for map as well, so this can be rewritten like this:

(<$>) = map
(<*>) = apply

add x y = x + y

one = Just 1
two = Just 2

add <$> one <*> two

Now, when I first saw this, I thought it was ugly. Why would you need to have separate <$> and <*>?

The answer is: to satisfy type system.

Sometimes type system is an annoying bitch. Because reality is an annoying bitch.

But once you overcome that initial barrier and accept zen, you’ll start to see the good things. For example if you had a function that sums 4 numbers instead of 2, you could have written like this:

add_quad a b c d = a + b + c + d

add_quad <$> (Just 1) <*> (Just 2) <*> (Just 3) <*> (Just 4)

So instead of trying to write complex function that is aware of four Options, we just apply values to our new function.

In Python this… wouldn’t be so nice.

But we can somewhat mitigate it:

def lift_optA2(f):
  def foo(a):
    def bar(b):
      return apply(map_opt(f)(a), b)
    return bar
  return foo

The term lift comes from lifting our values and functions into realm of side-effects (please don’t look at me like that, I didn’t come up with those silly terms).

And now instead of this:

add_opt = map_opt(add)
print(string_of(
  apply(add_opt(one), two)
))

We can write like this:

add_opt = lift_optA2(add)
print(string_of(
  add_opt(one)(two)
)) # prints "Some(3)"

We essentially treat add_opt as if it is a normal add! This is the power of applicative functors. We are coding with side effects as if those functions are pure!

If you don’t get this, well, take your time, because it is a big deal. This is what we were getting to all this time. All the immutability, pure functions and all the higher ordered functions were necessary for us to get to the point were we could write robust code in the face of side-effects.

Now, the last part that is left to understand is the dreaded monads. When people are talking about monads, what they refer to is two things:

  • constructor (in case of Options is some(x))
  • bind (also written as »= or>>=)

What bind essentially does, is sequence functions that do side effects, i.e. functions that are of type a -> f b.

Here how the bind is defined in case of Option:

def bind(opt_a):
  def foo(f):
    if is_some(opt_a):
      v = value_of(opt_a)
      return f(v)
    else:
      return none()
  return foo

The type signature of bind is this:

bind :: f a -> (a -> f b) -> f b

So what is effectively does, is take a value in some context (affected by side-effects) and applies a side-effecting function to it.

The weird order of arguments has to do with the fact, that bind is often declared as a custom operator >>= (also written as »=), this allows to sequence the functions:

foo x =
  x >>= \v1 ->
  f v1 >>= \v2 ->
  g v2 >>= \v3 ->
  if is_even v3 then
    return true
  else
    h v2

This is an imaginary side-effects-aware code in Haskell. v1, v2 and v3 refer to values in case the functions before them worked out nicely. The code follows a “happy path”, but in case there are problems, they are handled by the bind or the >>= operator in the background.

This is another power of functional programming: you think through the concepts and leverage the power of the ideas to make the programming language work for you, instead against of you.

Now, hopefully you see that the power of Option comes not from the fact that it represents Some and None, but from the way we structure our code in such a way to keep working with those values in a consistent manner. Despite the presence of the side-effects.

Also, Option is just one side-effect that exists there. There are many more and they can be as general or as domain-specific as you like. You can even write a monad to reliably work specifically with a MySQL for example.

The main idea is to be aware of the ideas and side-effects at hand.

Bonus: programming as proofs⌗

At this point when you start to take advantage of all the advanced concepts of functional programming and start to read academical papers on CS and Category Theory, you’ll start to feel as if you’re not programming, but actually writing a proof of the idea that you have in mind and computer is just there to verify your ideas.

And in fact this is not exactly far-fetched. If you have heard about coq, it does exactly that. Coq is a proof-assistant.

We have taught computers to verify mathematical proofs for us. Isn’t it marvelous?!

While I’m getting into a territory that I don’t understand, Coq leverages the Curry-Howard correspondance. TL;DR it states that properly written computer program corresponds to some mathematical proof. If you’re writing a function of type a -> b, you’re actually writing a proof that if a, then b. In fact, OCaml was initially developed with idea of writing a Coq in it. So sometimes you can feel the mathematical roots of OCaml and writing in it sometimes feels like writing proofs. It is not accidential.

Of course, there’s no problem if you don’t understand this or if it doesn’t work in your language: you need sufficiently strong type system to model your propositions.

But the idea is that the types are actually a very strong concept that helps you reason about the programs. Types are actually so powerful, they can encode the complex logic in their own fact of existance. This is what classes are supposed to do, but properly using classes at some point becomes just another form of functional programming.

There is a good wealth of materials on type theory. Good thing that math is thousand years old and that we have much better understanding of it than of Computer Science, isn’t it?

Closing thoughts…⌗

Thank you for reaching till this part. It must have been some journey, eh?

But if you reached till here, it means that your journey for you is just beginning. There are still so many things to learn about functional programming.

The thing I like the most is that when I learn more about functional programming, I somehow end up learning more about the world we live in. I somehow become a bit more profecient in philosophy and reasoning. I start to understand other people. I start to understand what the people are trying to do with economies.

It is surprising.

I also start to get appreciation for really good ideas. When you discover them, you start to squeel with delight. Because really good ideas are rare, but when you discover one, it sticks with you till the end of your life.

Nothing of this would have been possible without functional programming in my life.

And for you who are coding in Python, try giving other languages a try. Even if you won’t code in them professionally (or ever), at least your proficiency in Python will become better. What I hate more than Python is bad Python code that makes other people’s lives misereable.

Let’s try to make the world a better place.

Hope to see you soon…