# A tale on Semirings

Ever wondered why sum types are called sum types? Or maybe you’ve always wondered why the `<*>` operator uses exactly these symbols? And what do these things have to do with Semirings? Read this article and find out!

We all know and use `Monoid`s and `Semigroup`s. They’re super useful and come with properties that we can directly utilize to gain a higher level of abstractions at very little cost. Sometimes, however, certain types can have multiple `Monoid` or `Semigroup` instances. An easy example are the various numeric types where both multiplication and addition form two completely lawful monoid instances.

In abstract algebra there is a an algebraic class for types with two `Monoid` instances that interact in a certain way. These are called `Semiring`s (sometimes also `Rig`) and they are defined as two `Monoid`s with some special laws that define the interactions between them. Because they are often used to describe numeric data types we usually classify them as Additive and Multiplicative. Just like with numeric types the laws of `Semiring` state that multiplication has to distribute over addition and multiplying a value with the additive identity (i.e. zero) absorbs the value and becomes zero.

There are different ways to encode this as type classes and different libraries handle this differently, but let’s look at how the Scala library algebra handles this. Specifically, it defines a separate `AdditiveSemigroup` and `MultiplicativeSemigroup` and goes from there.

``````
(+) :: a -> a -> a

zero :: a

class MultiplicativeSemigroup a where
(*) :: a -> a -> a

class MultiplicativeMonoid a where
one :: a
``````

A `Semiring` is then just an `AdditiveMonoid` coupled with a `MultiplicativeMonoid` with the following extra laws:

1. Additive commutativity, i.e. `x + y === y + x`
2. Right distributivity, i.e. `(x + y) * z === (x * z) + (y * z)`
3. Left distributivity, i.e. `x * (y + z) === (x * y) + (x * z)`
4. Right absorption, i.e. `x * zero === zero`
5. Left absorption, i.e. `zero * x === zero`

To define it as a type class, we simply extend from both additive and multiplicative monoid:

``````class (MultiplicativeMonoid a, AdditiveMonoid a) => Semiring a
``````

Now we have a `Semiring` class, that we can use with the various numeric types like `Int`, `Number`, `BigInt` etc, but what else is a `Semiring` and why dedicate a whole blog post to it?

It turns out a lot of interesting things can be `Semiring`s, including `Boolean`s, `Set`s and animations.

One very interesting thing I’d like to point out is that we can form a `Semiring` homomorphism from types to their number of possible inhabitants. What the hell is that? Well, bear with me for a while and I’ll try to explain step by step.

### Cardinality

Okay, so let’s start with what I mean by cardinality. Every type has a specific number of values it can possibly have, e.g. a `Boolean` has cardinality of 2, because it has two possible values: `true` and `false`.

So `Boolean` has two, how many do other primitive types have? `Int` has 2^32 and `Number` has 2^64. So far so good, that makes sense, what about something like `String`? `String` is an unbounded type and therefore theoretically has infinite number of different inhabitants (practically of course, we don’t have infinite memory, so the actual number may vary depending on your system).

For what other types can we determine their cardinality? Well a couple of easy ones are `Unit`, which has exactly one value it can take and also `Void`, which is the “bottom” type in Haskell, which means it has 0 possible values. I.e you can never instantiate a value of `Void`, which gives it a cardinality of 0.

That’s neat, maybe we can encode this in actual code. We could create a type class that should be able to give us the number of inhabitants for any type we give it. Since we lack dependent types we can’t give a type as an input to a function, so instead we just pass a value of `a` to the function:

``````class Cardinality a where
cardinality :: a -> BigInt
``````

Awesome! Now let’s try to define some instances for this type class. We don’t actually need the value passed to `cardinality` so we’ll just ignore it:

``````instance booleanCardinality :: Cardinality Boolean where
cardinality _ = BigInt.fromInt 2

instance intCardinality :: Cardinality Int where
cardinality _ = pow (BigInt.fromInt 2) (BigInt.fromInt 32)

instance numberCardinality :: Cardinality Number where
cardinality _ = pow (BigInt.fromInt 2) (BigInt.fromInt 64)

instance unitCardinality :: Cardinality Unit where
cardinality _ = BigInt.fromInt 1

instance voidCardinality :: Cardinality Void where
cardinality _ = BigInt.fromInt 0
``````

Alright, this is cool, let’s try it out in the REPL! To do so, we’ll use `undefined`, which can be any type at all and annotate it using the type we want.

``````> cardinality (undefined :: Int)
4294967296

> cardinality (undefined :: Unit)
1

> cardinality (undefined :: Number)
18446744073709551616
``````

Cool, but this is all very simple, what about things like ADTs? Can we encode them in this way as well? Turns out, we can, we just have to figure out how to handle the basic product and sum types. To do so, let’s look at an example of both types. First, we’ll look at a simple product type: `(Boolean, Int8)`.

How many inhabitants does this type have? Well, we know `Boolean` has 2 and `Int8` has 256. So we have the numbers from `-127` to `128` once with `true` and once again with `false`. That gives us `512` unique instances. Hmmm….

`512` seems to be double `256`, so maybe the simple solution is to just multiply the number of inhabitants of the first type with the number of inhabitants of the second type. If you try this with other examples, you’ll see that it’s exactly true, awesome! Let’s encode that fact in a type class instance:

``````instance tupleCardinality :: (Cardinality a, Cardinality b) => Cardinality (a, b) where
cardinality _ = cardinality (undefined :: a) * cardinality (undefined :: b)
``````

Great, now let’s look at an example of a simple sum type: `Either[Boolean, Int8]`. Here the answer seems even more straight forward, since a value of this type can either be one or the other, we should just be able to add the number of inhabitants of one side with the number of inhabitants of the other side. So `Either[Boolean, Int8]` should have `2 + 256 = 258` number of inhabitants. Cool!

Let’s also code that up and try and confirm what we learned in the REPL:

``````instance eitherCardinality :: (Cardinality a, Cardinality b) => Cardinality (Either a b) where
cardinality _ = cardinality (undefined :: a) + cardinality (undefined :: b)
``````
``````> cardinality (undefined :: (Boolean, Int8))
512

> cardinality (undefined :: (Either Boolean Int8))
258

> cardinality (undefined :: (Either Int (Boolean, Unit)))
4294967298
``````

So using sum types seem to add the number of inhabitants whereas product types seem to multiply the number of inhabitants. That makes a lot of sense given their names!

So what about that homomorphism we talked about earlier? Well, a homomorphism is a structure-preserving mapping function between two algebraic structures of the same sort (in this case a semiring).

This means that for any two values `x` and `y` and the homomorphism `f`, we get

1. `f(x * y) === f(x) * f(y)`
2. `f(x + y) === f(x) + f(y)`

Now this might seem fairly abstract, but it applies exactly to what we just did. If we “add” two types of `Int8` and `Boolean`, we get an `Either Int8 Boolean` and if we apply the homomorphism function, `cardinality` to it, we get the value `258`. This is the same as first calling `cardinality` on `Int8` and then adding that to the result of calling `cardinality` on `Boolean`.

And of course the same applies to multiplication and product types. However, we’re still missing something from a valid semiring, we only talked about multiplication and addition, but not about their respective identities.

What we did see, though is that `Unit` has exactly one inhabitant and `Void` has exactly zero. So maybe we can use these two types to get a fully formed Semiring?

Let’s try it out! If `Unit` is `one` then a product type of any type with `Unit` should be equivalent to just the first type.

Turns out, it is, we can easily go from something like `(Int, Unit)` to `Int` and back without losing anything and the number of inhabitants also stay exactly the same.

``````> cardinality (undefined :: Int)
4294967296

> cardinality (undefined :: (Unit, Int))
4294967296

> cardinality (undefined :: (Unit, (Unit, Int)))
4294967296
``````

Okay, not bad, but how about `Void`? Given that it is the identity for addition, any type summed with `Void` should be equivalent to that type. Is `Either Void a` equivalent to `a`? It is! Since `Void` doesn’t have any values an `Either Void a` can only be a `Right` and therefore only an `a`, so these are in fact equivalent types.

We also have to check for the absorption law that says that any value mutliplied with the additive identity `zero` should be equivalent to `zero`. Since `Void` is our `zero` a product type like `(Int, Void)` should be equivalent to `Void`. This also holds, given the fact that we can’t construct a `Void` so we can never construct a tuple that expects a value of type `Void` either.

Let’s see if this translates to the number of possible inhabitants as well:

``````> cardinality (undefined :: (Either Void Boolean))
2

> cardinality (undefined :: (Either Void (Int8, Boolean)))
258
``````

Absorption:

``````> cardinality (undefined :: (Void, Boolean))
0

> cardinality (undefined :: (Void, Number))
0
``````

Nice! The only thing left now is distributivity. In type form this means that `(a, (Either b c))` should be equal to `Either (a, b), (a, c)`. If we think about it, these two types should also be exactly equivalent, woohoo!

``````> cardinality (undefined :: (Boolean, (Either Int8 Int16))
131584

> cardinality (undefined :: (Either (Boolean, Int8), (Boolean, Int16)))
131584
``````

## Higher kinded algebraic structures

Some of you might have heard of the `Semigroupal` or `Apply` type class. But why is it called that, and what is its relation to a `Semigroup`? Let’s find out!

First, let’s have a look at `Semigroupal`:

``````class Semigroupal f where
product :: forall a b. f a -> f b -> f (a, b)

``````

It seems to bear some similarity to `Semigroup`, we have two values which we somehow combine, and it also shares `Semigroup`s associativity requirement.

So far so good, but the name `product` seems a bit weird. It makes sense given we combine the `A` and the `B` in a tuple, which is a product type, but if we’re using products, maybe this isn’t a generic `Semigroupal` but actually a multiplicative one? Let’s fix this and rename it!

``````class MultiplicativeSemigroupal f where
product :: forall a b. f a -> f b -> f (a, b)
``````

Next, let us have a look at what an additive `Semigroupal` might look like. Surely, the only thing we’d have to change is going from a product type to a sum type:

``````class AdditiveSemigroupal f where
sum :: forall a b. f a -> f b -> f (Either a b)
``````

Pretty interesting so far, can we top this and add identities to make `Monoidal`s? Surely we can! For addition this should again be `Void` and `Unit` for multiplication:

``````class (AdditiveSemigroupal f) => AdditiveMonoidal f where
void :: f Void

class (MultiplicativeSemigroupal f) => MultiplicativeMonoidal f where
unit :: f Unit
``````

So now we have these fancy type classes, but how are they actually useful? Well, I’m going to make the claim that these type classes already exist in most preludes today, just under different names.

Let’s first look at the `AdditiveMonoidal`. It is defined by two methods, `void` which returns an `f Void` and `sum` which takes an `f a` and an `f b` to create an `f (Either a b)`.

What type class in the Prelude could be similar? First, we’ll look at the `sum` function and try to find a counterpart for `AdditiveSemigroupal`. Since we gave the lower kinded versions of these type classes symbolic operators, why don’t we do the same thing for `AdditiveSemigroupal`?

Since it is additive it should probably contain a `+` somewhere and it should also show that it’s inside some type constructor.

``````(<+>) :: forall f a b. f a -> f b -> f (Either a b)
``````

Oh! The `<+>` function already exists in some libraries as an alias for `alt` which can be found on `Alt`, but it’s sort of different, it takes two `f a`s and returns an `f a`, not quite what we have here.

Or is it? These two functions are actually the same, and we can define them in terms of one another as long as we have a functor:

``````sum :: forall f a b. f a -> f b -> f (Either a b)

alt :: forall f a. (Functor f) => f a -> f a -> f a
alt x y =
let feitheraa = sum x y
in map merge feitheraa
``````

So our `AdditiveSemigroupal` is equivalent to `Alt`, so probably `AdditiveMonoidal` is equivalent to `Plus`, right?

Indeed, and we can show that quite easily.

`Plus` adds an `empty` function with the following definition:

``````empty :: forall a. f a
``````

This function uses a universal quantifier for `a`, which means that it works for any `a`, which then means that it cannot actually include any particular `a` and is therefore equivalent to `f Void` which is what we have for `AdditiveMonoidal`.

Excellent, so we found counterparts for the additive type classes, and we’ve already talked about `MultiplicativeSemigroupal`. So the only thing left to find out is the counterpart of `MultiplicativeMonoidal`.

I’m going to spoil the fun and make the claim that `Applicative` is that counterpart. `Applicative` adds `pure`, which takes an `a` and returns an `f a`. `MultiplicativeMonoidal` adds `unit`, which takes no parameters and returns an `f Unit`. So how can we go from one to another? Well the answer is again using a functor:

``````unit :: f Unit

pure :: forall a. a => f a
pure a = imap (const a) (const ()) unit
``````

`Applicative` uses a covariant functor, but in general we could use invariant and contravariant structures as well. `Applicative` also uses `<*>` as an alias for using `product` together with `map`, which seems like further evidence that our intuition that its a multiplicative type class is correct.

So in the larger ecosystem right now we have `<+>` and `<*>`, is there also a type class that combines both similar to how `Semiring` combines `+` and `*`?

There is, it is called `Alternative`, it extends `Applicative` and `Plus` and if we were super consistent we’d call it a `Semiringal`:

``````class (MultiplicativeMonoidal f, AdditiveMonoidal f) => Semiringal f
``````

Excellent, now we’ve got both `Semiring` and a higher kinded version of it.

If it were available, we could derive a `Semiring` for any `Alternative` the same we can derive a `Monoid` for any `Plus` or `Applicative`. We could also lift any `Semiring` back into `Alternative`, by using `Const`, just like we can lift `Monoid`s into `Applicative` using `Const`.

To end this blog post, we’ll have a very quick look on how to do that.

``````
instance constSemiringal :: Semiring a => Semiringal (Const a) where
sum fb fc =
Const ((unwrap fb) + (unwrap fc))

product fb fc =
Const ((unwrap fb) * (unwrap fc))

unit = Const one

void = Const zero
``````

## Conclusion

Rings and Semirings are very interesting algebraic structures and even if we didn’t know about them we’ve probably been using them for quite some time. This blog post aimed to show how `Applicative` and `Plus` relate to `Monoid` and how algebraic data types form a semiring and how these algebraic structures are pervasive throughout Haskell and other functional programming languages. For me personally, realizing how all of this ties together and form some really satisfying symmetry was really mind blowing and I hope this blog post can give some good insight on recognizing these interesting similarities throughout the prelude and other libraries based on different mathematical abstractions. For further material on this topic, you can check out this talk.

This article glossed over commutativity in the type class encodings. Commutativity is very important law for semrings and the code should show that. However, since this post already contained a lot of different type class definitions, adding extra commutative type class definitions that do nothing but add laws felt like it would distract from what is trying to be taught.

Moreover I focused on the cardinality of only the types we need, but for completions sake, we could also add instances of `Cardinality` for things like `A -> B` , `Maybe a` or `These a b`. These are:

``````  cardinality (undefined :: (a -> b)) ===
pow (cardinality (undefined :: B)) (cardinality (undefined :: a))

cardinality (undefined :: (Maybe a)) ===
cardinality (undefined :: a) + 1

cardinality (undefined :: (These a b)) ===
(cardinality (undefined :: a)) + (cardinality (undefined :: b)) + (cardinality (undefined :: a)) * (cardinality (undefined :: b))
``````

`MonadError` is a very old type class, hackage shows me it was originally added in 2001, long before I had ever begun doing functional programming, just check the hackage page. In this blog post I’d like to rethink the way we use `MonadError` today. It’s usually used to signal that a type might be capable of error handling and is basically like a type class encoding of `Either`s ability to short circuit. That makes it pretty useful for building computations from sequences of values that may fail and then halt the computation or to catch those errors in order to resume the computation. It’s also parametrized by its error type, making it one of the most common example of multi-parameter type classes. Some very common instances include `Either` and `IO`, but there are a ton more.

We can divide instances into 3 loosely defined groups:

First we have simple data types like `Either`, `Maybe` or `These` (with `Validat` not having a `Monad` instance).

Secondly we’ve got `IO` or `Aff` in PureScript and similar types. These are used to suspend side effects which might have errors and therefore need to be able to handle these.

Thirdly and least importantly, we have monad transformers, which get their instances from their respective underlying monads. Since they basically just propagate their underlying instances we’re only going to talk about the first two groups for now.

The simple data types all define `MonadError` instances, but I wager they’re not actually used as much. This is because `MonadError` doesn’t actually allow us to deconstruct e.g. an `Either` to actually handle the errors. We’ll see more on that later, next let’s look at the `IO`-like types and their instances.

`IO` currently defines a `MonadError IOException IO`, in PureScript we have `MonadError Error (Aff eff)`. This means that they’re fully able to raise and catch errors that might be thrown during evaluation of encapsulated side effects. Using `MonadError` with these effect types seems a lot more sensical at first, as you can’t escape `IO` even when you handle errors, so it looks like it makes sense to stay within `IO` due to the side effect capture.

The problem I see with `MonadError` is that it does not address the fundamental difference between these two types of instances. I can pattern match an `Maybe a` with a default value to get back an `a`. With `IO` that is just not possible. So these two groups of types are pretty different, when does it actually make sense to abstract over both of them? Well, it turns out there a few instances where it might be useful, but as we’ll see later, I’m proposing something that will be equally useful to both groups.

Now before we continue, let’s look at the `MonadError` type class in a bit more detail. `MonadError` currently comprises two parts, throwing and catching errors. To begin let’s have a look at the `throw` part, sometimes also called `MonadThrow`:

``````class (Monad m) => MonadError e m | m -> e where
throwError :: e -> m a
``````

This looks fine for now, but one thing that strikes me is that the `m` type seems to “swallow” errors. If we look at `m a` we have no clue that it might actually yield an error of type `e`, that fact is not required to be represented at all. However, that’s not a really big issue, so now let’s look at the `catch` part:

``````class (Monad m) => MonadError e m | m -> e where
...
catchError :: m a -> (e -> m a) -> m a
``````

Immediately I have a few questions, if the errors are handled, why does it return the exact same type? Furthermore if this is really supposed to handle errors, what happens if I have errors in the `e -> m a` function? This is even more blatant in the `try` function:

``````try :: forall m e a. MonadError e m => m a -> m (Either e a)
``````

Here there is no way the outer `m` still has any errors, so why does it have the same type? Shouldn’t we represent the fact that we handled all the errors in the type system? This means you can’t actually observe that the errors are now inside `Either`. That leads to this being fully legal code:

``````try (try (try (try (Just 42))))
``````

Another example that demonstrates this is the fact that calling `handleError`, which looks like this:

``````handleError :: forall m e a. MonadError e m => m a -> (e -> a) -> m a
``````

also returns an `m a`. This method takes a pure function `e -> a` and thus can not fail during recovery like `catchError`, yet it still doesn’t give us any sign that it doesn’t throw errors. For `IO`-like types this is somewhat excusable as something like an unexceptional `IO` is still very uncommon, but for simple data types like `Either` or `Maybe` that function should just return an `A`, since that’s the only thing it can be. Just like with `attempt`, we can infinitely chain calls to `handleError`, as it will never change the type.

Ideally our type system should stop us from being able to write this nonsensical code and give us a way to show anyone reading the code that we’ve already handled errors. Now I’m not saying that the functions on `MonadError` aren’t useful, but only that they could be more constrained and thus more accurate in their representation.

For this purpose let’s try to write a different `MonadError` type class, one that’s designed to leverage the type system to show when values are error-free, we’ll call it `MonadBlunder` for now.

To mitigate the problems with `MonadError` we have a few options, the first one I’d like to present is using two different type constructors to represent types that might fail and types that are guaranteed not to. So instead of only a single type constructor our `MonadBlunder` class will have two:

``````class MonadBlunder f g e where
``````

Our type class now has the shape `(* -> *) -> (* -> *) -> * -> *`, which is quite a handful, but I believe we can justify its usefulness. The first type parameter `f` will represent our error-handling type, which will be able to yield values of type `e`. The second type parameter `g` will represent a corresponding type that does not allow any errors and can therefore guarantee that computations of the form `g a` will always yield a value of type `a`.

Now that we figured out the shape, let’s see what we can actually do with it. For throwing errors, we’ll create a `throwError` function that should return a value inside `f`, as it will obviously be able to yield an error.

``````class MonadBlunder f g e where
throwError :: forall a. e -> f a
``````

This definition looks identical to the one defined one `MonadError` so let’s move on to error-handling. For handled errors, we want to return a value inside `g`, so our `catchError` function should indeed return a `g a`:

``````class MonadBlunder f g e where
...

catchError :: forall a. f a -> (e -> f a) -> g a
}
``````

Looks good so far, right? Well, we still have the problem that the function `e -> f a` might return an erronous value, so if we want to guarantee that the result won’t have any errors, we’ll have to change that to `g a` as well:

``````class MonadBlunder f g e where
...

catchError :: forall a. f a -> (e -> g a) -> g a
}
``````

And now we’re off to a pretty good start, we fixed one short coming of `MonadError` with this approach.

Another approach, maybe more obvious to some, might be to require the type constructor to take two arguments, one for the value and one for the error type. Let’s see if we can define `throwError` on top of it:

``````class MonadBlunder b where
throwError :: forall e a. e -> b e a
...
}
``````

This looks pretty similar to what we already have, though now we have the guarantee that our type doesn’t actually “hide” the error-type somewhere. Next up is `catchError`. Ideally after we handled the error we should again get back a type that signals that it doesn’t have any errors. We can do exactly that by choosing an unhabited type like `Void` as our error-type:

``````class MonadBlunder b where
...

catchError :: forall e a. b e a -> (e -> b Void a) -> b Void a
}
``````

And this approach works as well, however now we’ve forced the two type parameter shape onto implementors. This `MonadBlunder` has the following kind `(* -> * -> *) -> *`. This means we can very easily define instances for types with two type parameters like `Either`. However, one issue might be that it’s much easier to fit a type with two type parameters onto a type class that expects a single type constructor `(* -> *)` than to do it the other way around.

For example try to implement the above `MonadBlunder ` for the standard `IO`. It’s not going to be simple, whereas with the first encoding we can easily encode both `Either` and `IO`. For this reason, I will continue this article with the first encoding using the two different type constructors.

Next we’re going to look at laws we can define to make sense of the behaviour we want. The first two laws should be fairly obvious. If we `bind` over a value created by `throwError` it shouldn’t propogate:

``````throwError e >>= f === throwError e
``````

Next we’re going to formulate a law that states, that raising an error and then immediatly handling it with a given function should be equivalent to just calling that function on the error value:

``````throwError e `catchError` f === f e
``````

Another law could state that handling errors for a pure value lifted into the `F` context does nothing and is equal to the pure value in the `G` context:

``````pure a `catchError` f === pure a
``````

Those should be good for now, but we’ll be able to find more when we add more derived functions to our type class. Also note that none of the laws are set in stone, these are just the ones I came up with for now, it’s completely possible that we’ll need to revise these in the future.

Now let’s focus on adding extra functions to our type class. `MonadError` offer us a bunch of derived methods that can be really useful. For most of those however we need access to methods like `bind` for both `f` and `g`, so before we figure out derived combinators, let’s revisit how exactly we define the type class.

The easiest would be to give both `f` and `g` a `Monad` constraint and move on. But then we’d have two type classes that both define a `throwError` function extends `Monad`, and we wouldn’t be able to use them together, since that would cause ambiguities and as I’ve said before, the functions on `MonadError` are useful in some cases.

Instead, since I don’t really like duplication and the fact that we’re not going to deprecate `MonadError` overnight, I decided to extend `MonadBlunder` from `MonadError` for the `F` type, to get access to the `throwError` function. If `throwError` and `catchError` were instead separated into separate type classes (as is currently the case in the PureScript prelude), we could extend only the `throwError` part. This also allows us to define laws that our counterparts of functions like `try` and `ensure` are consistent with the ones defined on `MonadError`. So the type signature now looks like this:

``````class (MonadError f e, Monad g) => MonadBlunder f g e | f -> e, f -> g where
...
``````

Now since this means that any instance of `MonadBlunder` will also have an instance of `MonadError` on `f`, we might want to rename the functions we’ve got so far. Here’s a complete definition of what we’ve come up with with `throwError` removed and `catchError` renamed to `catchBlunder`:

``````class (MonadError f e, Monad g) => MonadBlunder f g e | f -> e, f -> g where
catchBlunder :: forall a. f a -> (e -> g a) -> g a
``````

Now let us go back to defining more derived functions for `MonadBlunder`. The easiest probably being `handleError`, so let’s see if we can come up with a good alternative:

``````handleBlunder :: forall f g e a. MonadBlunder f g e => f a -> (e -> a) -> g a
handleBlunder fa f = catchBlunder fa (pure . f)
``````

This one is almost exactly like `catchBlunder`, but takes a function from `e` to `a` instead of to `g a`. We can easily reuse `catchBlunder` by using `pure` to go back to `e -> g a`.

Next another function that’s really useful is `try`. Our alternative, let’s call it `endeavor` for now, should return a value in `g` instead, which doesn’t have a `MonadError` instance and therefore can not make any additional calls to `endeavor`:

``````endeavor :: forall f g e a. MonadBlunder f g e => f a -> g (Either e a)
endeavor fa =
handleBlunder (map Right fa) Left
}
``````

The implementation is fairly straightforward as well, we just handle all the errors my lifting them into the left side of an `Either` and map successful values to the right side of `Either`.

Next, let’s look at the dual to `try`, sometimes called `absolve` or `rethrow`. For `MonadError` it turns an `f (Either e a)` back into an `f`, but we’re going to use our unexceptional type again:

``````absolve :: forall f g e a. MonadBlunder f g e => g (Either e a) -> f a
``````

But looking at this signature, we quickly realize that we need a way to get back to `f a` from `g a`. So we’re going to add another function to our minimal definition:

``````class (MonadError f e, Monad g) => MonadBlunder f g e | f -> e, f -> g, g -> f where
catchBlunder :: forall a. f a -> (e -> g a) -> g a
accept :: g ~> f
``````

This function `accept`, allows us to lift any value without errors into a context where errors might be present.

We can now formulate a law that values in `g` never stop propagating, so `bind` should always work, we do this by specifying that calling `handleBlunder` after calling `accept` on any `g a`, is never going to actually change the value:

``````(accept ga) `handleBlunder` f === ga
``````

Now we can go back to implementing the `absolve` function:

``````absolve :: forall f g e a. MonadBlunder f g e => g (Either e a) -> f a
absolve gea = accept gea >>= (either throwError pure)
``````

Now that we’ve got the equivalent of both `try` and `rethrow`, let’s add a law that states that the two should cancel each other out:

``````absolve (endeavor fa) === fa
``````

We can also add laws so that `handleBlunder` and `endeavor` are consistent with their counterparts now that we have `accept`:

``````accept (fa `handleBlunder` f) === fa `handleError` f

accept (endeavor fa) === try fa
``````

One nice thing about `try`, is that it’s really easy to add a derivative combinator that doesn’t go to `f e a`, but to the isomorphic monad transformer `ExceptT f e a`. We can do the exact same thing with `endeavor`:

``````endeavorT :: forall f g e a. MonadBlunder f g e => f a -> ExceptT g e a
endeavorT fa = ExceptT (endeavor fa)
``````

One last combinator I’d like to “port” from `MonadError` is the `ensure` function. `ensure` turns a successful value into an error if it does not satisfy a given predicate. We’re going to name the counterpart `assure`:

``````assure :: forall f g e a. MonadBlunder f g e => g a -> (a -> e) -> (a -> Bool) -> f a
assure ga error predicate =
accept ga >>= (\a ->
if predicate a then pure a else throwError (error a))
``````

This plays nicely with the rest of our combinators and we can again add a law that dictates it must be consistent with `ensure`:

``````ensure (accept ga) error predicate === assure ga error predicate
``````

Now we have a great base to work with with laws that should guarantee principled and sensible behaviour. Next we’ll actually start defining some instances for our type class.

The easiest definitions are for `Either` and `Maybe`, though I’m not going to cover both, as the instances for `Option` can simply be derived by `Either Unit a`and I’m going to link to the code at the end. For `Either e a`, when we handle all errors of type `e`, all we end up with is `a`, so the corresponding `g` type for our instance should be `Identity`. That leaves us with the following definition:

``````instance MonadBlunder (Either e) Identity e where
catchBlunder :: forall a. Either e a -> (e -> Identity a) -> Identity a
catchBlunder fa f = case fa of
Left e -> f e
Right a -> Identity a

accept :: Identity ~> Either e
accept = Right . runIdentity
``````

Fairly straightforward, as `Identity a` is just `a`, but with this instance we can already see a small part of the power we gain over `MonadError`. When we handle errors with `handleBlunder`, we’re no longer “stuck” inside the `Either` Monad, but instead have a guarantee that our value is free of errors. Sometimes it’ll make sense to stay inside `Either`, but we can easily get back into `Either`, so we have full control over what we want to do.

Next up, we’ll look at `IO` and the type that inspired this whole blog post `UIO`. `UIO` is equivalent to an `IO` type where all errors are handled and is short for “unexceptional IO”. This would also work for `IO` types who use two type parameters `IO e a` where the first represents the error type and the second the actual value. There you’d choose `IO e a` as the `f` type and `IO Void a` as the `g` type. `IO Void a` there is equivalent to `UIO a`.

As one might expect, you can not simply go from `IO a` to `UIO a`, but we’ll need to go from `IO a` to `UIO (Either e a)` instead, which if you look at it, is exactly the definition of `endeavor`. Now let’s have a look at how the `MonadBlunder` instance for `IO` and `UIO` looks:

``````instance MonadBlunder IO UIO IOException where
catchBlunder :: forall a. IO a -> (e -> a) -> UIO a
catchBlunder fa f =
unsafeFromIO (fa `catchError` (accept . f))

accept :: UIO ~> IO
accept = runUIO
``````

And voila! We’ve got a fully working implementation that will allow us to switch between these two types whenever we have a guarantee that all errors are handled. This makes a lot of things much simpler. For example, if one wants to use `bracket` with `UIO`, you just need to `bind` to the finalizer, as `bind` is always guaranteed to not short-circuit.

We can also define instances for `ExceptT` and `MaybeT` (being isomorphic to `ExceptT f Unit a`), where the corresponding unexceptional type is just the outer `f`, so `endeavor` is just a call to `run`:

``````instance MonadBlunder (ExceptT e f) f e where
catchBlunder :: forall a. ExceptT e f a -> (e -> f a) -> f a
catchBlunder efa f =
runExceptT efa >>= (\eea -> case eea of
Left e -> f e
Right a -> pure a
)

accept :: f ~> ExceptT f e
accept = lift
``````

Finally, it’s also possible to create instances for other standard monad transformers like `WriterT`, `ReaderT` or `StateT` as long as their underlying monads themselves have instances for `MonadBlunder`, as is typical in mtl. As their implementations are very similar we’ll only show the `StateT` transformer instance:

``````instance (MonadBlunder f g e) => MonadBlunder (StateT s f) (StateT s g) e where
catchBlunder :: forall a. StateT s f a -> (e -> StateT s g a) -> StateT s g a
catchBlunder sfa f =
StateT (\s -> runStateT sfa s `catchBlunder` ((runStateT s) . f))

accept :: StateT s g ~> StateT s f
accept = mapStateT accept
``````

In practice this means we can call `catchBlunder` on things like `StateT s IO a` and get back a `StateT s UIO a`. Pretty neat!

## Conclusion

In this article, I’ve tried to present the argument that `MonadError` is insufficient for principled error handling. We also tried to build a solution that deals with the shortcomings described earlier. Thereby it seeks not to replace, but to expand on `MonadError` to get a great variety of error handling capabilities. I believe the `MonadBlunder` type class, or whatever it will be renamed to, has the potential to be a great addition to the functional community at large.

You can find the full code here.

Note again, that none of this is final or set in stone and before it arrives anywhere might still change a lot, especially in regards to naming (which I’m not really happy with at the moment), so if you have any feedback of any sorts, please do chime in! Would love to hear your thoughts and thank you for reading this far!

# Optimizing Tagless Final

The following is a blog post written for PureScript, but should be able to work with Haskell with only very few modifications.

The Tagless Final encoding has gained some steam recently, with some people hailing 2017 as the year of Tagless Final. Being conceptually similar to the Free Monad, different comparisons have been brought up and the one trade-off that always comes up is the lack or the difficulty of inspection of tagless final programs and in fact, I couldn’t find a single example on the web. This seems to make sense, as programs in the tagless final encoding aren’t values, like programs expressed in terms of free structures. However, in this blog post, I’d like to dispell the myth that inspecting and optimizing tagless final programs is more difficult than using `Free`.

To start with, this blog post is gonna use a different tagless final encoding not based on type classes, but records instead. This allows us to treat interpreters as values. This technique is described here.

Without further ado, let’s get into it, starting with our example algebra, a very simple key-value store:

``````newtype KVStore f = KVStore
{ put :: String -> String -> f Unit
, get :: String -> f (Maybe String)
}
``````

To get the easiest example out of the way, here’s how to achieve parallelism in a tagless final program:

``````program :: forall f m. Parallel m f => KVStore f -> f (Maybe String)
program (KVStore k) = do
k.put "A" a
x <- (<>) <\$> k.get "B" `parApply` k.get "C"
k.put "X" (fromMaybe "-" x)
pure x
``````

This programs makes use of the `Parallel` type class, that allows us to make use of the `parApply` combinator to use independent computations with a related `Applicative` type. This is already much simpler than doing the same thing with `Free` and `FreeApplicative`. For more info on `Parallel` check out the docs here.

However this is kind of like cheating, we’re not really inspecting the structure of our program at all, so let’s look at an example where we actually have access to the structure to do optimizations with.

Let’s say we have the following program:

``````program :: forall f. Apply f => KVStore f -> f (List String)
program mouse (KVStore k) = (\f s _ t -> catMaybes (f : s : t : Nil)) <\$>
k.get "Cats" <*> k.get "Dogs" <*> k.put "Mice" "42" <*> k.get "Cats"
``````

Not a very exciting program, but it has some definite optimization potential. Right now, if our KVStore implementation is an asynchronous one with a network boundary, our program will make 4 network requests sequentially if interpreted with the standard `Apply` instance of something like `Aff`. We also have a duplicate request with the `"Cats"`-key.

So let’s look at what we could potentially do about this. The first thing we should do, is extract the static information. The easiest way to do so, is to interpret it into something we can use using a `Monoid`. This is essentially equivalent to the `analyze` function commonly found on `FreeApplicative`.

Getting this done, is actually quite simple, as we can use `Const` as our `Applicative` data type, whenever the lefthand side of `Const` is a `Monoid`. I.e. if `m` has a `Monoid` instance, `Const m a` has an `Applicative` instance. You can read more about `Const` here.

``````import Prelude
import Data.StrMap as M
import Data.Set as S
import Data.Const

analysisInterpreter :: KVStore (Const (Tuple (S.Set String) (M.StrMap String)))
analysisInterpreter = KVStore
{ put : \key value -> Const \$ tuple2 S.empty (M.singleton key value)
, get : \key -> Const \$ tuple2 (S.singleton key) M.empty
}

(Const (program analysisInterpreter))

``````

By using a Tuple of `Set` and `Map` as our `Monoid`, we now get all the unique keys for our `get` and `put` operations. Next, we can use this information to recreate our program in an optimized way.

``````optimizedProgram :: forall f. Apply f => KVStore f -> f (List String)
optimizedProgram (KVStore k) =
let (Const (Tuple gets puts)) = program analysisInterpreter
in traverse (\(Tuple k v) -> k.put k v) (fromFoldable puts) *> traverse k.get (fromFoldable gets)
``````

And we got our first very simple optimization. It’s not much, but we can imagine the power of this technique. For example, if we were using something like `GraphQL`, we could sum all of our `get` requests into one large request, so only one network roundtrip is made. We could imagine similar things for other use cases, e.g. if we’re querying a bunch of team members that all belong to the same team, it might make sense to just make one request to all the team’s members instead of requesting them all individually.

Other more complex optimizations could involve writing a new interpreter with the information we gained from our static analysis. One could also precompute some of the computations and then create a new interpreter with those computations in mind.

Embedding our Applicative program inside a larger monadic program is also trivial:

``````program :: forall f. Apply f => String -> KVStore f -> f (List String)
program mouse (KVStore k) = (\f s _ t -> catMaybes (f : s : t)) <\$>
k.get "Cats" <*> k.get "Dogs" <*> k.put "Mice" mouse <*> k.get "Cats"

optimizedProgram :: forall f. Apply f => String -> KVStore f -> f (List String)
optimizedProgram mouse (KVStore k) =
let (Const (Tuple gets puts)) = program mouse analysisInterpreter
in traverse (\(Tuple k v) -> k.put k v) (fromFoldable puts) *> traverse k.get (fromFoldable gets)

monadicProgram :: forall f. Bind f => KVStore f -> f Unit
mouse <- k.get "Mice"
list <- optimizedProgram (fromMaybe "64" mouse) k
k.put "Birds" (fromMaybe "128" (head list))

``````

Here we refactor our `optimizedProgram` to take an extra parameter `mouse`. Then in our larger `monadicProgram`, we perform a `get` operation and then apply its result to `optimizedProgram`.

So now we have a way to optimize our one specific program, next we should see if we can introduce some abstraction.

First we’ll have to look at the shape of a generic program, they usually are functions from an interpreter `algebra f` to an expression inside the type constructor `f`, such as `f a`.

``````type Program alg a = forall f. Applicative f => alg f -> f a
``````

The program is only defined by the algebra and the resulting `a`, so it should work for all type constructors `f`.

``````optimize :: forall alg f a m. Applicative f
=> Monoid m
=> Program alg a
-> alg (Const m)
-> m -> f a
-> alg f
-> f a
optimize program extract restructure =
let (Const m) = program extract
in restructure m
``````

Now we should be able to express our original optimization with this new generic approach:

``````optimizedProgram :: forall f. Apply f => String -> KVStore f -> f (List String)
optimizedProgram mouse (KVStore k) =
optimize program analysisInterpreter (\(Tuple gets puts) ->
traverse (\(Tuple k v) -> k.put k v) (fromFoldable puts) *> traverse k.get (fromFoldable gets))
``````

So far so good, we’ve managed to write a function to generically optimize tagless final programs. However, one of the main advantages of tagless final is that implementation and logic should be separate concerns. With what we have right now, we’re violating the separation, by mixing the optimization part with the program logic part. Our optimization should be handled by the interpreter, just as the sequencing of individual steps of a monadic program is the job of the target `Monad` instance.

One way to go forward, is to create a typeclass that requires certain algebras to be optimizable. This typeclass could be written using the generic function we wrote before, so let’s see what we can come up with:

``````type OptimizerReqs alg f m =
{ extract :: alg (Const m)
, rebuild :: m -> alg f -> f (alg f)
}

class (Monad f, Monoid m) <= Optimizer alg f m | alg -> f , f -> m where
reqs :: OptimizerReqs alg f m

optimize :: forall alg f m a. Optimizer alg f m
=> Program alg a
-> alg f
-> f a
optimize prog interpreter =
let (Const m2) = prog (reqs :: OptimizerReqs alg f m).extract
in (reqs.rebuild m2 interpreter) >>= prog
``````

This might look a bit daunting at first, but we’ll go through it bit by bit. First we define our type class `Optimizer` parameterized by an algebra `alg :: (* -> *) -> *` and a type constructor `f :: * -> *`. This means we can define different optimizations for different algebras and different target types. For example, we might want a different optimization for a production `Optimizer KVStore (EitherT Task e) m` and a testing `Optimizer KVStore Identity m`. Next, for our interpreter we need a `Monoid m` for our static analysis, so we parametrize the `Optimizer` with an extra parameter `m`.

The next two functions should seem familiar, the `extract` function defines an interpreter to get an `m` out of our program. The `rebuild` function takes that value of `m` and the interpreter and produces an `f alg f`, which can be understood as an `f` of an interpreter. This means that we can statically analyze a program and then use the result of that to create a new optimized interpreter and this is exactly what the `optimize` function does. This is also why we needed the `Monad` constraint on `f`, we could also get away with returning just a new interpreter `alg f` from the `rebuild` method and get away with an `Applicative` constraint, but we can do more different things this way.

Let’s see what our program would look like with this new functionality:

``````monadicProgram :: forall f m. Optimizer KVStore f m => KVStore f -> f Unit
mouse <- k.get "Mice"
list <- optimize (program \$ fromMaybe "64" mouse) (KVStore k)
k.put "Birds" (fromMaybe "128" (head list))
``````

Looking good so far, now all we need to run this is an actual instance of `Optimizer`. We’ll use the standard `Aff` for this and for simplicity our new optimization will only look at the `get` operations:

``````extract :: KVStore (Const (S.Set String))
extract = KVStore
{ get : \key -> Const \$ S.singleton key
, put : \_ _ -> Const \$ S.empty
}

rebuild :: forall e. S.Set String -> KVStore (Aff e) -> Aff e (KVStore (Aff e))
rebuild gs (KVStore interp) =
precomputed <#> (\m -> KVStore \$ interp
{ get = \key -> case (M.lookup key m) of
Just a -> pure \$ Just a
Nothing -> interp.get key
})
where
tupleList :: Aff e (List (Maybe (Tuple String String)))
tupleList =
parTraverse (\key -> interp.get key <#> (\m -> m <#> \s -> key /\ s)) (fromFoldable gs)
precomputed :: Aff e (M.Map String String)
precomputed = tupleList <#> (M.fromFoldable <<< catMaybes)

instance kvStoreAffOptimizer :: Optimizer KVStore (Aff e) (S.Set String) where
reqs = { extract , rebuild }
``````

Our `Monoid` type is just a simple `Set String` here, as the `extract` function will only extract the `get` operations inside the `Set`. Then with the `rebuild` we build up our new interpreter. First we want to precompute all the values of the program. To do so, we just run all the operations in parallel and put them into a `Map`, while discarding values where the `get` operation returned `Nothing`. Now when we have that precomputed `Map`, we’ll create a new interpreter with it, that will check if the key given to `get` operation is in the precomputed `Map` instead of performing an actual request. We can then lift the value into a `Aff e (Maybe String)`. For all the `put` operations, we’ll simply run the interpreter.

Now we should have a great optimizer for `KVStore` programs interpreted into an `Aff`. Let’s see how we did by interpreting into a silly implementation that only prints whenever you use one of the operations:

``````testInterpreter :: forall e. KVStore (Aff e)
testInterpreter = KVStore
{ put : \_ value -> do
liftEff \$ unsafeCoerceEff \$ log \$ "Put something " <> value
pure unit
, get : \key -> do
liftEff \$ unsafeCoerceEff \$ log \$ "Hit network for " <> key
pure \$ Just \$ key <> "!"
}
``````

Now let’s run our program with this interpreter and the optimizations!

``````launchAff \$ monadicProgram testInterpreter
// Hit network for Mice
// Hit network for Cats
// Hit network for Dogs
// Put something: Mice!
// Put something: Cats!
``````

And it works, we’ve now got a principled way to write programs that can then be potentially optimized.

## Conclusion

Designing a way to completely separate the problem description from the actual problem solution is fairly difficult. The tagless final encoding allows us one such fairly simple way. Using the technique described in this blog post, we should be able to have even more control over the problem solution by inspecting the structure of our program statically.

Another thing we haven’t covered here, are programs with multiple algebras, which is quite a bit more complex as you can surely imagine, maybe that will be the topic of a follow up blog post.

The code for this blog post can be found here, if people find it useful enough, I’ll publish and document it!

What kind of problems and techniques would you like to see with regards to tagless final? Would love to hear from you in the comments!

Today I’d like us to build our own Reactive Mobile Framework. A Reactive UI Framework should allow us to build apps declaratively by manipulating User Event Streams.

Now we’re not going to write such a Framework from scratch, but we’d like to use an existing Framework and create some Bindings, so that we can use it reactively. Examples for these types of wrappers are RxCocoa for the `Cocoa` and `Cocoa Touch` Frameworks, RxBinding for Android or RxSwing for the Java Swing toolkit.

First we have to choose the UI Framework we’re going to work with. I’ve spent a lot of time working with mobile Reactive Frameworks, so for today, I’d like to create some Bindings for the Xamarin.Forms toolkit. Xamarin.Forms is a cross-platform UI Framework that lets you create native UIs for both Android and iOS, by leveraging the .NET Framework. We’re going to write our code in F#, since it just supports the functional paradigm a lot better.

Now without further ado let’s identify what exactly it takes to create such a Wrapper.

Firstly, we’ll need to have a way to create an event stream from user interactions, for example, we should be able to create an event stream from a toggle or checkbox, that emits boolean values. We’ll call these interactions event sources, some frameworks like `RxBinding` will only support bindings for event sources.

Next, we will need a way to take event streams and bind them to a View. An easy example is a function that takes a stream of Strings and binds them to a Label. We’ll call these event sinks, since that’s where our streams will go into.

So one of the easiest programs we can imagine with this kind of setup is a Switch that emits boolean values that then get mapped to some kind of text which finally gets bound to a Label. I made a small diagram to illustrate what’s happening:

Alright, now let’s get codin’! The first thing we’re gonna do is create the source function for the Switch. The function will accept a `Switch` and return an `Observable<bool>`. Creating new Observables is fairly straight forward. Let’s look at a small example:

We use the `Observable.Create` function and call the `OnNext`, `OnError` and `OnCompleted` functions to emit values and errors.

Now that we know how to create Observables, let’s finally create one for the Switch:

Here we again create an Observable that emits the value of the Switch everytime it’s toggled. We don’t need to call `OnError` or `OnCompleted`, since the Switch won’t error out or stop emitting. Yay! We created our first source binding! We placed in a module called `RxForms`, where we’ll place all of our binding functions from now on.

Okay, so let’s continue by defining a sink. We’ll call our function `bindLabel` and it’ll take an `Observable<string>` and a `Label` and it’ll return a `Subscription`.

Now that we’ve created functions to extract sources and bind to sinks, we have a basis on which we could expand and wrap around all of the Xamarin.Forms widgets. So go! No time to lose, the Api has dozens of Views to wrap, but first let’s see if our cute little program actually works. Here’s the code:

We’re using the simplest layout With a `StackLayout` and then create both a `Switch` and a `Label` and then use our functions to wire everything up. Here’s how this would look on iOS:

Notice, though, that we currently have to handle the subscription manually. If we fleshed out our Framework, we could create a mechanism, that unsubscribes automatically, whenever the bound view get’s destroyed (This is what RxCocoa’s `DisposeBag` does, maybe we’ll implement this in another article).

I could probably end this article here, but let’s look at a few more examples. First, some easy stuff:

With these, we can easily use `Button`s, `ListView`s and `Entry`s (Entrys are simple Textfields). So let’s use these new widgets to create the most over used example app: The Todo app! Yaaaay! The Todo app is great though, because it usually demonstrates how to handle state.

One option for implementing such an app would be to add both a Button and an Entry and combine them, but Entry also offers a Event that emits once the user ends input. Let’s add a function to extract such a source:

We’ll start by adding both an `Entry` and a `ListView` and extracting an `Observable<string>` from the `Entry`:

Now what we’d like to accumulate these todos into a list of todos, a `List<string>`. To do that, we’ll use the `scan` operator, which is like a reducer, but emits all the intermediary values. Once again, I made a diagram to explain this (a picture speak a thousand words).

So every time our `Entry` completes, we add a new item to our list. This is how that looks in code:

And with that, we’re done right? Well not quite, since now every time we submit a Todo, our Entry doesn’t clear, which kinda sucks. So we need to write another binding for `Entry`s. However, I’m going to leave that as an exercise for you, dear reader! Instead, here’s a gif on how it should look in the end (I’ll upload the final code, just in case you get stuck).

### Conclusion

So that’s it for now, I hope, that with your help, we can bring Reactive Programming to more and more UI Frameworks. Me, personally, I’d really like to see a full fledged Library made out of what we started in this article. In case you have any questions, I’d love to hear them, so just post them in the comments down below. The full code of this article can be found here. Happy Coding everyone!

# What makes a programming language functional

What makes a language functional? Well, that’s a good question! Some people say that lambdas make a language a functional language. Others say it’s the ability to bind functions to variables. But that in itself isn’t really all it takes right? After all, we could do this with function pointers in C! And I don’t think many would claim C is a functional language, right?

In this article I’ll try to go over some specific features that I personally think make or break a functional programming language. Now pay in mind, that a lot of this is going to be fairly subjective, but I’d love to hear your thoughts in the comments!

So without further ado here’s what we will take a look at throughout this article (in order of most to last important to functional programming):

• First Class Functions
• Immutability
• Recursion
• Expression-Oriented Programming
• Currying
• Lazy Evaluation
• Algebraic Data Types
• Other topics (Higher Kinded Types, Existential Types)

## First class functions

Most languages support this nowadays, Java 8 brought First Class functions to the language and C++ also included them in C++11. Having functions be first class basically only really means that you can use them the same way you would use any other value, like being able to bind functions to variables and pass them around your application.

Now there have been a lot of different names for what is basically just a couple of concepts, so we’ll try and go through them shortly.

### Anonymous Functions AKA Lambda Expressions

Lambdas and anonymous functions are essentially the same thing, it’s just a function that doesn’t have a binding to an identifier. So they’re just easy ways for creating functions, in the same sense that some languages allow literals for Arrays or dictionaries. Anonymous functions originate in Alonzo Church’s Lambda Calculus, hence the name. Here’s an example in python: With that we’ve defined a variable holding a function that will square a given number when applied. Pretty straight forward!

### Lexical Closures

Now closures are often confused with lambdas and it’s not difficult to understand why. All closures are anonymous functions, but it doesn’t work vice versa. Closures are special functions, that close over the environment where it was created, meaning it can gain access to values not in its parameter list. Very similar to how methods can access instance variables. You’ve probably already heard of the saying “Closures are the poor man’s objects”. Let’s take a look at an example in Kotlin: In this snippet we can see that the function passed to `forEach` gets access to the `sum` variable and can even modify it. So closures and lambdas go hand in hand, then what’s the deal with Higher order functions?

### Higher Order Functions

Most of you have probably already used Higher Order Functions. HOFs are just functions that take another function as a parameter. So any function that takes a callback function could be considered a HOF. Other very notable example include functions like `map`, `filter` `reduce`. Here’s an example for a `filter`-function in Swift: Here predicate is a function that takes a parameter of type `T` and returns a `Bool` depending on if the element matches the predicate or not. You’ll find many of these HOFs in most functional languages and it’s almost an absolut must for doing any kind of functional programming.

## Immutability

Immutability plays a big part in FP, a small subset of functional languages are so called “pure” functional languages. Purity means, that absolutely everything is immutable. Examples for this are Haskell, Elm and (as the name suggests) PureScript.

So on the one side we’ve got languages where everything is immutable, but on the other side we also have languages where immutability is unavailable. JavaScript has often been touted as a functional language, butit didn’t have any way to make variables immutable until ES6 and even then it’s only limited to local variables and there’s still no way to declare instance variables to be immutable (unless you’re using Object.freeze). Other languages where immutability is also lacking are Python and Ruby.

Now this is not the only metric for how much a given language supports immutability. Another is of course, how much the language encourages you to write immutable code. In Java and C# for example you need to add an extra keyword to make a value immutable (C# also doesn’t allow Type Inference on immutable values).

Put this in contrast to Rust:

It’s quite clear which programming language wants to encourage you to use immutable values. Some compilers (like Rust and Swift) also emit a warning if you use a mutable variable, but don’t mutate it.

Lots of functional languages also offer a way to copy an Object or Record, but with one or multiple values modified. This makes creating a new value almost exactly as easy as modifying the original. Here’s an example of what that might look like in Elm:

Another thing to consider is something traditionally called “const correctness”, which means that you can’t mutate parts of a value if it’s declared immutable. For example this is legal in Java: Where as the equivalent would throw a compiler error in C++.

Now the last thing to consider is whether or not your language supports performant immutable data structures. Languages like Kotlin and Swift support simple readonly data structures, that are the same as their mutual counterpart, but not being able to modify it.

Other more functional languages offer us special collections that are optimized for immutability. These immutable data structures have operators that can modify and return a copy of the original. Most of the time, however we don’t even need to copy most of the collection and can instead reuse it, because we don’t need to worry about subsequent code making changes to our data. So there’s no need to defensively copy the whole structure, saving both memory and time! This is called data sharing and is a huge benefit of immutable data structures.

The coolest collections come from the late Scala community leader Phil Bagwell (R.I.P.), essentially they offer amortized O(1) lookups, insertions and deletions on Vectors and HashMaps. You can find these data structures in Clojures and Scalas standard library as well as in libraries such as Immutable.js. There’s a lot of super interesting stuff to talk about, so if you’re interested check out this great series on how these data structures actually work.

## Recursion

Most if not all of modern programming languages support the notion of recursion However it plays a much bigger part in functional programming than in imperative programming. That is because when programming in a functional way, iterating over data structure recursively is not just much more elegant, but also the only way to iterate without invoking side-effects.

In order for this to be efficient, most functional languages offer an optimization technique called “Tail Call Optimization”. With this technique it’s possible for recursive functions to not increase the size of the call stack. In other words: the compiler more or less replaces the original function with the equivalent of an imperative loop.

Going into too much detail here would break the scope of the article, so here’s the gist of it: if the last thing you do (i.e. the “tail” position) in a function is a recursive call to itself, the compiler can optimize this to act like iteration instead of recursion.

So if you want to do functional programming in your language without having to worry about stack overflows, your language should probably provide some form of TCO.

Some languages make writing tail recursive functions a lot easier by giving you a way to mark them as such. For example Scala supports a way explicitly annotate a function as tail recursive and let the compiler throw an error when it isn’t.

This guarantees that an error is issued whenever tail call optimization cannot be performed by the compiler.

## Expression-Oriented Programming

To understand Expression-Oriented programming we first need to define the difference between expressions and statements. This is best explained by contrasting return types of different functions. For example a `void` type means the method is probably a statement, since it doesn’t a result. Everything else is an expression and yields a value when computed. Typically the former looks something like `list.sort()` while expressions look like `sorted = sort(list)`.

To put it simply, in Expression-Oriented programming languages everything is an expression! Which means that everything has a return value. This is something we aspire to because statements always have side effects and should be avoided as much as possible in functional programming.

Rust, Ruby, Kotlin and more functional languages like Scala, Elm, Haskell or F# all use this paradigm. This means that for example the `if`-construct always returns a result:

Another neat example are Scala’s “for-expressions” which involve some syntactical sugar that looks very similar to for-loops found in imperative languages.

## Currying

Currying is when you break down a function that takes multiple parameters into a series of functions each taking a parameter and returning a new function. A simple example would be this:

I’ve written in depth about the workings and advantages of Currying and the most often confused technique of partial application in an earlier article. Both Currying and partial application are very useful tools in the functional programming world and most functional languages make it very easy to do so. For example in Haskell or one of the different ML-derived languages, it’s mostly impossible to even write an uncurried version of functions. Functions are just curried by default! Here’s some Haskell code: The type signature of the `add` function is `Integer -> Integer -> Integer`, meaning it takes an Int and returns a function that takes an Int and returns an Int. This allows us to just pass one argument to the `add` function and get another generic function that adds the passed argument. Different languages handle this differently, but it’s a pretty important tool in the functional programmers toolkit!

Scala for example lets you partially apply functions easily by passing an underscore `_` as a function parameter. Swift is a rather curious example, because it supported a very way of writing curried functions, but has since deprecated them without any real replacement.

## Lazy evaluation

Lazy evaluation is a technique to defer the computation of expressions to when they are really needed. This is in contrast to eager evaluation, where every expression is evaluated immediately. Lazy evaluation can be very beneficial when programming in a functional way. Let’s look at an example of eager evaluation in JavaScript:

In this example each operation returns a new copy immediately once called. What we’d like to do is use higher-order functions like `map` and `filter` instead of manually fusing passes, but without having to create intermediate data structures and having to iterate the structure multiple times. This can be solved quite handily using lazy evaluation.

So now let’s have a look at equivalent code using lazy evaluation: Wait a minute… it’s the same basic code! Well yeah it is, the truly interesting stuff is happening behind the scenes, but this code can demonstrate a few things.

Firstly, we no longer create intermediate copys of the list, in fact nothing even gets computed untill we access the first element by calling the `head` method. Secondly, since we’re only accessing the first element of the list, all the operations are only applied once and we can save a lot of execution time. We do not need to evaluate the whole list, when all we want to do is print out the first element.

In Haskell lazy evaluation is the default, but in most other functional languages it’s opt in. Examples for these are the various Lisps, Scala and F#.

## Algebraic Data Types

Algebraic data types? Aw man, what’s this fancy maths stuff? I just want to program cool stuff! Alright! I won’t go into too much detail here, so bear with me for a moment! Okay, so most functional languages allow you to define simple data types. These ADTs are simple data cointainers that can be defined recursively. They can be easily constructed and deconstructed and usually come with built in structural equality checking.

All of this allows us to utilize a technique called “Pattern matching”. Pattern matching is a kind of `switch-case` on steroids, it can do type-testing, it can check exhaustiveness and it can destructure it’s arguments. Let’s have a look at an example written in Scala:

This is just a rather simple example, but I’m sure you can imagine how powerful the `match` expression can be. An ADT can be anything by the way, from Tuples to Lists, to Records. So Pattern matching is extremely useful because we can decompose any kind of data structure by its shape instead of its contents.

With pattern matching navigating and decomposing data structures becomes very convenient, with a compact syntax.

There’s two other things I’d like to atleast give a mention, they’re both fairly complex and probably warrant a whole article just to get a good understanding. Furthermore they’re both features of a type system, which might be interesting in staticly typed languages, but no so much for dynamic ones.

### Higher kinded Types

The first feature is the ability to create “Higher Kinded Types”, which can be seen as providing a way to is the ability to generically abstract over things that take type parameters Here’s an example with a Functor in Scala: Here `F[_]` could be anything that takes a generic parameter, so `Option[T]` or `List[T]` would both be fine.

### Existential Types

The other feature is called “Existential Types” can be used for several different purposes, but what they do is to ‘hide’ a type parameter for outside use. Sometimes you don’t care about the actual type but only that it exists. Existential types can make this a reality without making the type parameter covariant.

## Conclusion

Now I’d like to conclude without telling you which language is a functional language or which one isn’t. The line is probably more blurred than not and it’s impossible to find some objective criteria for a functional language. We could argue for ages about what or what doesn’t constitute one and how we should weigh these features on a scale from 1 to 100, instead I think we’ve got a fair overview of features functional programmers use everyday.

My hope is that after reading this article, you understand that lambdas aren’t the only criteria and what else might play a role in programming in a functional way. Yes we can do functional programming in almost any language, but in most that would be more cumbersome than we’d like and we should probably strive to use the right tool for the right job. Once you try out a language that has a lot of these “functional” features, you’ll probably find programming with pure functions a lot more pleasant. And I hope you guys can also enjoy functional programming more once you’ve got a hold on some of these cool features.