Skip to content

How to make your types obey the law

Jump to bottom
Paul Louth edited this page Oct 17, 2024 · 1 revision

Laws testing

Functors, applicatives, and monads all have laws that make them what they are. Some think that Map just means the same as Map in mathematics, when in fact functors are more constrained and are structure-preserving.

The full set of laws are:

Functors

  • Identity law
  • Composition law
  • Structure preservation law

Applicatives

  • Identity law
  • Composition law
  • Homomorphism law
  • Interchange law
  • Applicative-functor law

Monads

  • Left-identity law
  • Right-identity law
  • Associativity law

When you write your own functors/applicatives/monads you are expected to honour these laws. In reality it's pretty hard to go wrong if you just follow the type-signatures and implement the traits in the most obvious way, but still, it is possible to make mistakes and some of the guarantees of the traits will start to fail.

assert

The type-system isn't able to enforce many of the laws above, so we need to do it ourselves. Often the best way to do that is via unit-tests. If you implement a monadic type (using the new traits system) then can simply call:

MonadLaw<M>.assert();

Where M is your monad trait implementation type.

For example, this tests that Option complies with all of the laws listed above. If any law does not hold then an exception will be thrown. All failing rules will be aggregated into a single exception.

MonadLaw<Option>.assert();

If your type isn't a monad, but is an applicative, then you can call:

ApplicativeLaw<M>.assert();

And if your type isn't an applicative, but is a functor, then you can call:

var mx = M.Pure(123);
FunctorLaw<M>.assert(mx);

Functors don't know how to instantiate new functors (unlike applicatives and monads), so you must provide an instance to the assert function. For example:

var mx = Option.Some(123);
FunctorLaw<Option>.assert(mx);

A couple of notes:

  • All tests work with lifted integers, M<int>, the reason is to keep equality tests simple, but also an int can be plucked out of thin air and manipulated easily.
  • If your type is a monad and you call MonadLaw<M>.assert, you do not need to call ApplicativeLaw<M>.assert or FunctorLaw<M>.assert. Those will be tested automatically.

validate

The assert functions listed above are perfect for unit-tests, but you can also call validate. It will return a Validation<Error, Unit> which will collect a set of failures for any failing laws. This can be used for non-exceptional tests (perhaps in some tooling).

var result = MonadLaw<Option>.validate();  // Validation<Error, Unit>

Equality

The functions that test that the laws hold need to be able to test equality of the functor/monad/applicative values. Unfortunately, not all functors/applicatives/monads support equality. Types like Reader, for example, are computations (not values), and so must be evaluated to extract a concrete value.

The functors/applicatives/monads traits don't know how to evaluate the underlying lifted-values to extract the concrete values. And so, for types that have no valid Equals implementation, you must provide an equality function to assert and validate.

Here's an example for Eff<int>:

  bool eq(K<Eff, int> vx, K<Eff, int> vy) => 
      vx.Run().Equals(vy.Run());
  
  MonadLaw<Eff>.assert(eq);

It's pretty simple, we just need to run the computations to get at the concrete results. We can then compare those results.

Examples

You can look at the unit-tests for all of the functor/applicative/monad types in language-ext:

Future

  • More laws tested for more traits!
  • Potentially add these assertions to a Roslyn analyzer (if anyone wants to try, please do!)
Clone this wiki locally