An article for object-oriented programmers.

This article is an instalment in an article series about monads.

Just as functors must obey the functor laws, monads must follow the monad laws. When looked at from the right angle, these are intuitive and reasonable rules: identity and associativity.

That sounds almost like a monoid, but the rules are more relaxed. For monoids, we require a binary operation. That's not the case for functors and monads. Instead of binary operations, for monads we're going to use Kleisli composition.

This article draws heavily on the Haskell wiki on monad laws.

In short, the monad laws comprise three rules:

  • Left identity
  • Right identity
  • Associativity

The article describes each in turn, starting with left identity.

Left identity #

A left identity is an element that, when applied to the left of an operator, doesn't change the other element. When used with the fish operator it looks like this:

id >=> h ≡ h

For monads, id turns out to be return, so more specifically:

return >=> h ≡ h

In C# we can illustrate the law as a parametrised test:

[Theory]
[InlineData(-1)]
[InlineData(42)]
[InlineData(87)]
public void LeftIdentityKleisli(int a)
{
    Func<int, Monad<int>> @return = Monad.Return;
    Func<int, Monad<string>> h = i => Monad.Return(i.ToString());
 
    Func<int, Monad<string>> composed = @return.Compose(h);
 
    Assert.Equal(composed(a), h(a));
}

Recall that we can implement the fish operators as Compose overloads. The above test demonstrates the notion that @return composed with h should be indistinguishable from h. Such a test should pass.

Keep in mind, however, that Kleisli composition is derived from the definition of a monad. The direct definition of monads is that they come with a return and bind functions (or, alternatively return and join). If we inline the implementation of Compose, the test instead looks like this:

[Theory]
[InlineData(-1)]
[InlineData(42)]
[InlineData(87)]
public void LeftIdentityInlined(int a)
{
    Func<int, Monad<int>> @return = Monad.Return;
    Func<int, Monad<string>> h = i => Monad.Return(i.ToString());
 
    Func<int, Monad<string>> composed = x => @return(x).SelectMany(h);
 
    Assert.Equal(composed(a), h(a));
}

or, more succinctly:

Assert.Equal(@return(a).SelectMany(h), h(a));

This is also the way the left identity law is usually presented in Haskell:

return a >>= h = h a

In Haskell, monadic bind is represented by the >>= operator, while in C# it's the SelectMany method. Thus, the Haskell and the C# representations are equivalent.

Right identity #

Right identity starts out similar to left identity. Using the fish operator, the Haskell wiki describes it as:

f >=> return ≡ f

Translated to a C# test, an example of that law might look like this:

[Theory]
[InlineData("foo")]
[InlineData("ploeh")]
[InlineData("lawful")]
public void RightIdentityKleisli(string a)
{
    Func<string, Monad<int>> f = s => Monad.Return(s.Length);
    Func<int, Monad<int>> @return = Monad.Return;
 
    Func<string, Monad<int>> composed = f.Compose(@return);
 
    Assert.Equal(composed(a), f(a));
}

Again, if we inline Compose, the test instead looks like this:

[Theory]
[InlineData("foo")]
[InlineData("ploeh")]
[InlineData("lawful")]
public void RightIdentityInlined(string a)
{
    Func<string, Monad<int>> f = s => Monad.Return(s.Length);
    Func<int, Monad<int>> @return = Monad.Return;
 
    Func<string, Monad<int>> composed = x => f(x).SelectMany(@return);
 
    Assert.Equal(composed(a), f(a));
}

Now explicitly call the f function and assign it to a variable m:

[Theory]
[InlineData("foo")]
[InlineData("ploeh")]
[InlineData("lawful")]
public void RightIdentityInlinedIntoAssertion(string a)
{
    Func<string, Monad<int>> f = s => Monad.Return(s.Length);
    Func<int, Monad<int>> @return = Monad.Return;
 
    Monad<intm = f(a);
 
    Assert.Equal(m.SelectMany(@return), m);
}

The assertion is now the C# version of the normal Haskell definition of the right identity law:

m >>= return = m

In other words, return is the identity element for monadic composition. It doesn't really 'do' anything in itself.

Associativity #

The third monad law is the associativity law. Keep in mind that an operator like + is associative if it's true that

(x + y) + z = x + (y + z)

Instead of +, the operator in question is the fish operator, and since values are functions, we typically call them f, g, and h rather than x, y, and z:

(f >=> g) >=> h ≡ f >=> (g >=> h)

Translated to a C# test as an example, the law looks like this:

[Theory]
[InlineData(0)]
[InlineData(1)]
[InlineData(2)]
public void AssociativityKleisli(double a)
{
    Func<double, Monad<bool>> f = i => Monad.Return(i % 2 == 0);
    Func<bool, Monad<string>> g = b => Monad.Return(b.ToString());
    Func<string, Monad<int>> h = s => Monad.Return(s.Length);
 
    Func<double, Monad<int>> left = (f.Compose(g)).Compose(h);
    Func<double, Monad<int>> right = f.Compose(g.Compose(h));
 
    Assert.Equal(left(a), right(a));
}

The outer brackets around (f.Compose(g)) are actually redundant; we should remove them. Also, inline Compose:

[Theory]
[InlineData(0)]
[InlineData(1)]
[InlineData(2)]
public void AssociativityInlined(double a)
{
    Func<double, Monad<bool>> f = i => Monad.Return(i % 2 == 0);
    Func<bool, Monad<string>> g = b => Monad.Return(b.ToString());
    Func<string, Monad<int>> h = s => Monad.Return(s.Length);
 
    Func<double, Monad<string>> fg = x => f(x).SelectMany(g);
    Func<double, Monad<int>> left = x => fg(x).SelectMany(h);
 
    Func<bool, Monad<int>> gh = x => g(x).SelectMany(h);
    Func<double, Monad<int>> right = x => f(x).SelectMany(gh);
 
    Assert.Equal(left(a), right(a));
}

If there's a way in C# to inline the local compositions fg and gh directly into left and right, respectively, I don't know how. In any case, the above is just an intermediate step.

For both left and right, notice that the first step involves invoking f with x. If, instead, we call that value m, we can rewrite the test like this:

[Theory]
[InlineData(0)]
[InlineData(1)]
[InlineData(2)]
public void AssociativityInlinedIntoAssertion(double a)
{
    Func<double, Monad<bool>> f = i => Monad.Return(i % 2 == 0);
    Func<bool, Monad<string>> g = b => Monad.Return(b.ToString());
    Func<string, Monad<int>> h = s => Monad.Return(s.Length);
 
    Monad<boolm = f(a);
 
    Assert.Equal(m.SelectMany(g).SelectMany(h), m.SelectMany(x => g(x).SelectMany(h)));
}

The above assertion corresponds to the way the associativity law is usually represented in Haskell:

(m >>= g) >>= h = m >>= (\x -> g x >>= h)

Once more, keep in mind that >>= in Haskell corresponds to SelectMany in C#.

Conclusion #

A proper monad must satisfy the three monad laws: left identity, right identity, and associativity. Together, left identity and right identity are know as simply identity. What's so special about identity and associativity?

As Bartosz Milewski explains, a category must satisfy associativity and identity. When it comes to monads, the category in question is the Kleisli category. Or, as the Haskell wiki puts it:

Monad axioms:
Kleisli composition forms
a category.

Subsequent articles in this article series will now proceed to give examples of concrete monads, and what the laws look like for each of these.

Next: The List monad.


Comments

That sounds almost like a monoid, but the rules are more relaxed. For monoids, we require a binary operation. That's not the case for functors and monads. Instead of binary operations, for monads we're going to use Kleisli composition.

I am confused by this paragraph. A monoid requries a binary operation (that is also closed), and Kleisli composition is (closed) binary operation.

As you said in the introductory article to this monad series, there are three pieces to a monad: a generic type M<>, a function with type a -> M<a> (typically called "return"), and a function with signature (a -> M<b>) -> M<a> -> M<b> (sometimes called "bind"). Then (M<>, return, bind) is a monad if those three items satisfy the monad laws.

I think the following is true. Let M<> be a generic type, and let S be the set of all functions with signature a -> M<a>. Then (M<>, return, bind) is a monad if only only if (S, >=>, return) is a monoid.

2022-04-18 16:17 UTC

Tyson, thank you for writing. To address the elephant in the room first: A monad is a monoid (in the category of endofunctors), but as far as I can tell, you have to look more abstractly at it than allowed by the static type systems we normally employ.

Bartosz Milewski describes a nested functor as the tensor product of two monadic types: M ⊗ M. The binary operation in question is then M ⊗ M -> M, or join/flatten (from here on just join). In this very abstract view, monads are monoids. It does require an abstract view of functors as objects in a category. At that level of abstraction, so many details are lost that join looks like a binary operation.

So, to be clear, if you want to look at a monad as a monoid, it's not the monadic bind function that's the binary operation; it's join. (That's another reason I prefer explaining monads in terms of join rather than leading with bind.)

When you zoom in on the details, however, join doesn't look like a regular binary operation: m (m a) -> m a. A binary operation, on the other hand, should look like this: m a -> m a -> m a.

The Kleisli composition operator unfortunately doesn't fix this. Let's look at the C# method signature, since it may offer a way out:

public static Func<T, Monad<T2>> Compose<TT1T2>(
    Func<T, Monad<T1>> action1,
    Func<T1, Monad<T2>> action2)

Notice that the types don't match: action1 has a type different from action2, which is again different from the return type. Thus, it's not a binary operation, because the elements don't belong to the same set.

As Bartosz Milewski wrote, though, if we squint a little, we may make it work. C# allows us to 'squint' because of its object hierarchy:

public static Func<object, Monad<object>> Compose(
    Func<object, Monad<object>> action1,
    Func<object, Monad<object>> action2)

I'm not sure how helpful that is, though, so I didn't want to get into these weeds in the above article itself. It's fine here in the comments, because I expect only very dedicated readers to consult them. This, thus, serves more like a footnote or appendix.

2022-04-23 11:29 UTC

Thanks very much for you reply. It helped me to see where I was wrong. (S, >=>, return) is not a monoid because >=> is not total over S, which is another condition the binary operation must satisfy, but I overlooked that. Furthremore, I meant to define S as the set of all functions with signature a -> M<b>. The same problem still exists though. The second code block in your comment has this same problem. There is not a natural choice for the implementation unless the types of the objects satisfy the constraints implied by the use of type parameters in the first code block in your comment. I will keep thinking about this.

In the meantime, keep up the great work. I am loving your monad content.

2022-04-23 19:47 UTC


Wish to comment?

You can add a comment to this post by sending me a pull request. Alternatively, you can discuss this post on Twitter or somewhere else with a permalink. Ping me with the link, and I may respond.

Published

Monday, 11 April 2022 06:57:00 UTC

Tags



"Our team wholeheartedly endorses Mark. His expert service provides tremendous value."
Hire me!
Published: Monday, 11 April 2022 06:57:00 UTC