There is a lot of confusion about types and monads, especially among people who’ve never used them to their full extent. In this post I wish to explore the motivations for having type systems and monads in a programming language, along with the trade-offs languages make on those matters. I will start with types, since that is the more familiar of the two concepts. I when talking about monads, I will draw a lot of parallels to types.

**Haskell primer**

To make sure that this tutorial is readable for everyone, I will quickly explain a bit of the syntax of Haskell. If you are already familiar with Haskell, skip past this section.

In Haskell, one doesn’t use parentheses when applying functions:

print "Hello"

But one may use it to make the prefix notation work when applying nested functions:

print (addOne 1)

I will sometimes be using whitespace to avoid parentheses:

print addOne 1

One defines functions simply by writing the name, followed by the arguments, followed by an equals sign, followed by the result:

addOne x = x + 1

One usually adds type annotations, but it is very, very rarely needed, as Haskell has global type inference:

addTwo :: Int -> Int addTwo x = x + 2

Parameterized types have a similar syntax. For instance, a map from strings to ints is called

Map String Int

In Haskell, we can use binary functions as infix functions:

plus :: Int -> Int -> Int plus x y = x + y example x = x `plus` x

Haskell also has the let-in concept:

let x = 2 in x*x

This is a nice way of having temporary variables. We can define lambdas using this syntax:

\parameter -> body

Read the backslash as a lambda. I will be changing small parts of Haskell (mainly the libraries) to make it more beginner-friendly.

**Types**

Suppose we are designing a language. Let’s suppose that we choose not to have a type system. In this case, we may end up confusing the types of variables in subtle ways. The damage of this can be reduced with rigorous unit testing and excellent variable naming, but one can still lose lots of time on bugs from this. Another problem is that it makes refactoring harder, since the validation that you did it right is weaker.

Another choice is to fix a set of types from the beginning. Few languages do this, as it isn’t much better than not having a type system. In fact, not having a type system is equivalent to having exactly one type.

A nicer choice would be to let the programmer define data types from building blocks. Older languages (and Go) do not let the programmer parameterize types with types, so we will look at this example first. This lets the programmer create their own data types, but usually not general-purpose ones, such as lists. There are ways to acheive polymorphism without parameterized types (such as inheritance), but I will not write about that now.

The type systems of Haskell and many functional languages, along with some modern less-than-functional languages allow the programmer to define data types parameterized with other data types in a way that looks like this:

data Option a = None | Just a

This translates quite directly to English:

The data type Option of a is either None or Just of a.

One can define a wide variety of data types this way, and using pattern matching, one can use them in safe ways:

logIn userData = do maybeUser <- lookupUser userData case maybeUser of None -> -- display error Just user -> -- log user in

**Effect systems**

You thought I was going to talk about monads now? Well, I’m not. First, I will introduce the concept of an effect system. Just like there can be a lot of bugs when not expecting what stuff is, there can be a lot of bugs when not expecting what stuff does. Just like a type system restricts what stuff can be, an effect system restricts what stuff can do. Some effect systems can also restrict what stuff can’t do, such as not committing/rollbacking database transactions.

Drawing parallels to types, the simplest effect system is not having an effect system. This does not help catching bugs, but it is quite popular. Not every mainstream language lacks an effect system. For instance, Java has a badly designed effect system called “checked exceptions”.

Another way to make an effect system is by fixing a set of effects. Such a set could be `IO`

(in the Haskell-jargon for anything sense), state, exceptions and nontermination. This limits the programmer a lot; we are not, for instance, able to ensure that database transactions are handled appropriately. Borrowing examples from a Koka (which implements this kind of effect system) tutorial:

function sqrTotal(x: Int): total int { return x * x } function sqrIO(x: Int): io int { print("effect") return x * x } function sqrDiv(x: Int): div int { if (x < 5) { while {true} {} } return x*x } function sqrExn(x: Int): exn int { if (x < 5) { error("oops") } return x*x }

A third way is to let the programmer define an effect system in a way a bit like the data type example. An example syntax for this could be:

effect StreamReader = read :: Option Char | hasMore :: Bool

One could then imagine “handlers” that convert one kind of effect (such as `StreamReader`

) to some “greater” kind (such as `IO`

), to be able to use the effect for things (such as reading files).

We can also imagine parameterized versions of effects defined in the same way as above:

effect StreamReader el = read :: Option el | hasMore :: Bool effect State st = set :: st -> Unit | get :: st effect Exn ex = throw :: ex -> Void

To make the language simpler, one may want to unify the effect system and the type system. In that case, one can define combinators that make effects a lot nicer to work with. One way to combine effects and types is by making effects a kind of “type constructors”, which take the parameters of the effect along with the result of the computation. That is, a piece of code that can read from a character stream and returns an int would be of type `StreamReader Char Int`

.

catchAndReturn :: Exn ex a -> a -> a catchAndReturn code default = case code of throw _ -> default return x -> x

We may ask ourselves the question: do we really need to have a separate syntax for defining effects, now that effects are just certain kinds of types? The answer is no, and it turns out that by not having a special syntax for effects, we get some much more powerful effects. In fact, they become so powerful that I would dare to say that functional languages (at least tomorrows functional languages) will be much better at imperative programming than imperative languages.

First, let us define a simple effect as if it were a type, just to have an example. We will choose state, because that is a simple effect. First, observe that state is basically the same as carefully threading a value to every function:

while :: a -> (a -> Bool) -> (a -> a) -> a while state cond action = if cond then while (action state) cond action else state test :: Int -> (Int, String) test state = while state (\st -> st > 10) -- while (state > 10) (\st -> st - 1) -- state = state - 1

This is not very readable, but it tells us something about state: a stateful calculation with a state of type st returning something of type a is a normal calculation of the type `st -> (st, a)`

. We can try encoding that in types:

data State st a = Stateful (st -> (st, a)) runState :: State st a -> st -> (st, a) -- utility function runState state = -- this can be done in a better way, case state of -- but for simplicity, it is done this way Stateful f -> f

We can then try to write `while`

using this:

while :: (st -> Bool) -> State st Unit -> State st Unit while cond action = Stateful (\state -> if cond state then runState while cond action first (runState action state)) else (state, Unit)

This doesn’t seem much cleaner. That turns out to be a result of missing combinators. For instance, we have no combinator for combining stateful effects in a sequence. A good combinator for that is this:

andThen :: State st a -> (a -> State st b) -> State st b andThen stA stB = State (\st0 -> let (st1, a) = runState st st0 in runState (f a))

It turns out that some combinators for interacting with the state are also nice. These combinators may be easier to understand after reading the next implementation of `while`

.

get :: State st st get = State (\st -> (st, st)) result :: a -> State st a result a = State (\st -> (st, a))

The implementation of `while`

is…

while :: (st -> Bool) -> State st Unit -> State st Unit while cond action = get `andThen` (\x -> if cond x then action `andThen` (\Unit -> while cond action) else result Unit)

This implementation does not look nearly as bad as the original implementation. It can be improved, but I will get to that later. In a sense, result takes a value and makes some stateful code that has no effect, but has the result that the function result was given as a parameter.

You may be thinking “Congratulations! You’ve just implemented an ugly version of something I use every day!”. I will admit that this thought is not completely unjustified, but hang in there. It turns out that `andThen`

and `result`

are combinators that make sense for every kind of effect. You may ask “What can these combinators even be used for?”. Again, this is not completely unjustified. It turns out that with only these combinators, one can implement a slightly different version of while, but before we do that, I need to introduce you to typeclasses.

**Typeclasses**

One way to make code more reusable is to use typeclasses. A good example of a typeclass is monoid, which basically lets you concatenate things, regardless of what they are:

double :: Monoid a => a -> a double x = x <> x

This function lets us double arbitrary things. For instance, the result of `double "Haskell is awesome!"`

is `"Haskell is awesome!Haskell is awesome!"`

The type of double should be read “If `a`

is a monoid, given an `a`

, we can give you an `a`

.”. We can also define other utility functions for monoids, such as concatenating every element in a list, but that is not important right now. The important thing is that we can turn a type that isn’t a monoid into a monoid, simply by writing an implementation of a few things. This way, we get all of the utility functions for monoids for free.

The way we do this is by creating a typeclass instance. For instance, suppose we want to make `Int`

a monoid such that `<>`

adds numbers. One would do it like this:

instance Monoid Int where x <> y = x + y empty = 0

Many typeclasses have rules associated with them. For instance, one rule of monoids is that no matter what `x`

is, `x <> empty`

must be `x`

.

After implementing monoid for ints, we can use our previously defined utility function:

double 2

As one would expect, the result of evaluating the above code is `4`

.

Another thing we can do is declare typeclasses that can be implemented by others. For instance, suppose we decide that `andThen`

and `result`

are sufficient for effects. In that case, we can define a typeclass for effects like this:

class Effect ef where andThen :: ef a -> (a -> ef b) -> ef b result :: a -> ef a

We should also decide on some laws. First, let’s formalize our intuition that `result`

does not have any effect, and instead is used to have the right type in combination with `andThen`

. First, if we have some effectful code called `effectful`

, and we take that code `andThen`

give its result to `result`

, we would expect it to be the same as the original code:

effectful `andThen` (\res -> result res) = effectful

Next, if we have some effectful function called `effectfulFunc`

, we would expect that if we take a value, give that value to `result`

`andThen`

execute `effectfulFunc`

, it is the same as executing `effectfulFunc`

with the original value:

result x `andThen` effectfulFunc = effectfulFunc x

Another laws that we would expect is hard to formulate in English, but here the algebraic formulation is:

(effectful `andThen` firstEffectfulFunc) `andThen` secondEffectfulFunc = effectful `andThen` (\x -> firstEffectfulFunc x `andThen` secondEffectfulFunc)

You may not understand the equation above yet, but hopefully you’ve learned why Haskellers often use single-character-names. To understand the example above, we may need to change it to a language more familiar to you. It basically says that these two pseudo-code snippets are the same:

secondEffectfulFunc(firstEffectfulFunc(effectful())) x = effectful() secondEffectfulFunc(firstEffectfulFunc(x))

In other words, it lets you extract the result of a computation to a local variable.

**Examples**

We can implement multiple examples of the effect typeclass above. Obviously, we can use the functions I already defined for `State`

to make `State`

an `Effect`

:

instance Effect (State st) where andThen stA stB = State (\st0 -> let (st1, a) = runState st st0 in runState (f a)) result a = State (\st -> (st, a))

Another effect we can imagine is dynamic scoping:

data DynScope env a = DynScoped (env -> a) runDynScope :: DynScope env a -> env -> a runDynScope dynScope env = case dynScope of DynScoped f -> f env instance Effect (DynScope env) where andThen dynSA dynSB = DynScope (\env -> runDynScope dynSB runDynScope dynSA env env) result x = DynScope (\env -> x)

Another one is `IO`

, but we cannot really implement that, since what makes `IO`

special is that it is native code. We can make Prolog-style nondeterminism an effect by using lists, but that’ll have to wait for another blog post.

Exceptions, software transactional memory, context-sensitive parsing and continuation passing are also examples of effects that fit the `Effect`

typeclass.

**Utility functions**

There is not a big advantage to having defined all of this if we don’t have any utility functions. Luckily, we can define lots of utility functions.

A common pattern is that we have a list of things to execute, and we want to execute them sequentially, and collect all the results in a list. This can be done like this:

sequence :: Effect ef => [ef a] -> ef [a] -- [something] is a list of somethings sequence list = case list of first : rest -> first `andThen` (\x -> sequence rest `andThen` (\xs -> result (x : xs))) Empty -> result Empty

I also talked about a generalized `while`

. This does not make sense for every kind of effect, only those in which the result of an action can change depending on preceding actions. That does not matter for the implementation, but there’s no point in using it with effects like `DynScope`

.

while :: Effect ef => ef Bool -> ef Unit -> ef Unit while cond action = cond `andThen` (\bool -> if bool then action `andThen` (\Unit -> while cond action) else result Unit)

**Monads**

So where do monads come into all this? Depending on your knowledge, you may already know this, but the `Effect`

typeclass… is the exact same as the `Monad`

typeclass. Now, there are arguably some monads that don’t fit the effect intuition, but I think this intuition is what makes monads so important for programming.

In the future, I want people to at least separate effect systems, monads and Haskell when they write rants, but that is unlikely to happen.

It may seem impractical to write a type for each mishmash of effects you use, and luckily, there is a good solution for that, called monad transformers, but that will have to wait for another post.

Remember that the entire point originally was to catch bugs, but I would like to see you implement Prolog-style nondeterminism in a language that does not have monads or something equivalent in power (continuations), or something more powerful (macros).

You may still think that the above examples looks ugly, and I agree, so let me introduce… do notation. Basically, do notation replaces

do x <- m stuff using x

with

m `andThen` (\x -> do stuff using x)

and it replaces

do expression

with

expression

It may not seem like such a simple a transformation is able to make the code prettier, but I’ll let you decide:

sequence list = case list of first : rest -> do x <- first xs <- sequence rest result (x : xs) Empty -> result Empty while cond action = do bool <- cond if cond then do Unit <- action while cond action else result Unit