Introduction

For the last month or, I have been working as a contractor for Luminal. I am helping them implement Fugue, and more specifically Ludwig – a compiler a for statically typed declarative configuration language. This is one of the most interesting projects I have worked on so far – writing a compiler is really fun. While implementing some parts of this compiler, I came across an interesting problem.

In particular, a typeclass instance seemed to adhere to both the Monad and Applicative laws, but with differing behaviour – which felt a bit fishy. I started a discussion on Twitter understand it better, and these are my thoughts on the matter.

The problem

Suppose we’re writing a typechecker. We have to do a number of things:

Parse the program to get a list of user-defined types.

Typecheck each expression.

A bunch of other things, but for the purpose of this post we’re going to leave it at that.

Now, any of these steps could fail, and we’d like to log the reason for failure. Clearly this is a case for something like Either! Let’s define ourselves an appropriate datatype.

Which is correct, but using a compiler entirely written in this fashion would be annoying. Check, like Either, short-circuits on the first error it encounters. This means we would compile our program, fix one error, compile, fix the next error, compile, and so on.

It would be much nicer if users were to see multiple error messages at once.

Of course, this is not always possible. On one hand, if findDefinedTypes1 throws an error, we cannot possibly call typeCheck1, since we do not have a TypeScope.

On the other hand, if findDefinedTypes1 succeeds, shouldn’t it be possible to collect error messages from both typeCheck1 scope expr1andtypeCheck1 scope expr2?

It turns out this is possible, precisely because the second call to typeCheck1 does not depend on the result of the first call – so we can execute them in parallel, if you will. And that is precisely the difference in expressive power between Monad and Applicative: Monadic >>= provides access to previously computed results, where Applicative <*> does not. Let’s (ab?)use this to our advantage.

Using this instance we can effectively collect error messages. We need to change our code a bit to support a collection of error messages, so let’s use [String] instead of String since a list is a Monoid.

The problem with the solution

The problem is that we have created a situation where <*> is not equal to ap1. After researching this for a while, it seems that <*> = ap is not a verbatim rule. However, most arguments suggest it should be the case – even the name.

This is important for refactoring, for example. Quite a few Haskell programmers (including myself) would refactor:

Without putting too much thought in it, just assuming it does the same thing.

In our case, they are clearly similar, but not equal – we would get only one error instead of collecting error messages. One could argue that this is close enough, but when one uses that argument too frequently, you might just end up with something like PHP.

The latter will get stuck in some sort of infinite recursion, while the former will not. This is not a subtle difference anymore. While the problem is easy to spot here (>> vs. *>), this is not always the case:

Ever since AMP, it is impossible to tell whether this will do a forM_ or a for_-like traversal without looking at the implementation – this makes making mistakes easy.

The solution to the problem with the solution

As we discussed in the previous section, it should be possible for a programmer to tell exactly how a Monad or Applicative will behave, without having to dig into implementations. Having a structure where <*> and ap behave slightly differently makes this hard.

When a Haskell programmer wants to make a clear distinction between two similar types, the first thing that comes to mind is probably newtypes. This problem is no different.

Let’s introduce a newtype for error-collecting Applicative. Since the Functor instance is exactly the same, we might as well generate it using GeneralizedNewtypeDeriving.

At this point, it shouldn’t surprise you that Validation intentionally does not provide a Monad instance.

Conclusion

This, of course, is all my opinion – there doesn’t seem to be any definite consensus on whether or not ap should be the same as <*>, since differing behaviour occurs in prominent libraries. While the Monad and Applicative laws are relatively well known, there is no canonical law saying that ap = <*>.

Update: there actually is a canonical law that ap should be <*>, and it was right under my nose in the Monad documentation since AMP. Before that, it was mentioned in the Applicative documentation. Thanks to quchen for pointing that out to me!

A key point here is that the AMPactually related the two typeclasses. Before that, arguing that the two classes were in a way “unrelated” was still a (dubious) option, but that is no longer the case.

Furthermore, considering this as a law might reveal opportunities for optimisation 2.

Lastly, I am definitely a fan of implementing these differing behaviours using different types and then converting between them: the fact that types explicitly tell me about the behaviour of code is one of the reasons I like Haskell.