Normal functions form monads. An article for object-oriented programmers.

This article is an instalment in an article series about monads. A previous article described the Reader functor. As is the case with many (but not all) functors, Readers also form monads.

This article continues where the Reader functor article stopped. It uses the same code base.

Flatten #

A monad must define either a bind or join function, although you can use other names for both of these functions. Flatten is in my opinion a more intuitive name than join, since a monad is really just a functor that you can flatten. Flattening is relevant if you have a nested functor; in this case a Reader within a Reader. You can flatten such a nested Reader with a Flatten function:

public static IReader<R, A> Flatten<RA>(
    this IReader<R, IReader<R, A>> source)
{
    return new FlattenReader<R, A>(source);
}
 
private class FlattenReader<RA> : IReader<R, A>
{
    private readonly IReader<R, IReader<R, A>> source;
 
    public FlattenReader(IReader<R, IReader<R, A>> source)
    {
        this.source = source;
    }
 
    public A Run(R environment)
    {
        IReader<R, A> newReader = source.Run(environment);
        return newReader.Run(environment);
    }
}

Since the source Reader is nested, calling its Run method once returns a newReader. You can Run that newReader one more time to get an A value to return.

You could easily chain the two calls to Run together, one after the other. That would make the code terser, but here I chose to do it in two explicit steps in order to show what's going on.

Like the previous article about the State monad, a lot of ceremony is required because this variation of the Reader monad is defined with an interface. You could also define the Reader monad on a 'raw' function of the type Func<R, A>, in which case Flatten would be simpler:

public static Func<R, A> Flatten<RA>(this Func<R, Func<R, A>> source)
{
    return environment => source(environment)(environment);
}

In this variation source is a function, so you can call it with environment, which returns another function that you can again call with environment. This produces an A value for the function to return.

SelectMany #

When you have Flatten you can always define SelectMany (monadic bind) like this:

public static IReader<R, B> SelectMany<RAB>(
    this IReader<R, A> source,
    Func<A, IReader<R, B>> selector)
{
    return source.Select(selector).Flatten();
}

First use functor-based mapping. Since the selector returns a Reader, this mapping produces a Reader within a Reader. That's exactly the situation that Flatten addresses.

The above SelectMany example works with the IReader<R, A> interface, but the 'raw' function version has the exact same implementation:

public static Func<R, B> SelectMany<RAB>(
    this Func<R, A> source,
    Func<A, Func<R, B>> selector)
{
    return source.Select(selector).Flatten();
}

Only the method declaration differs.

Query syntax #

Monads also enable query syntax in C# (just like they enable other kinds of syntactic sugar in languages like F# and Haskell). As outlined in the monad introduction, however, you must add a special SelectMany overload:

public static IReader<R, T1> SelectMany<RTUT1>(
    this IReader<R, T> source,
    Func<T, IReader<R, U>> k,
    Func<T, U, T1> s)
{
    return source.SelectMany(x => k(x).Select(y => s(x, y)));
}

As already predicted in the monad introduction, this boilerplate overload is always implemented in the same way. Only the signature changes. With it, you could write an expression like this nonsense:

IReader<intboolr =
    from dur in new MinutesReader()
    from b in new Thingy(dur)
    select b;

Where MinutesReader was already shown in the article Reader as a contravariant functor. I couldn't come up with a good name for another reader, so I went with Dan North's naming convention that if you don't yet know what to call a class, method, or function, don't pretend that you know. Be explicit that you don't know.

Here it is, for the sake of completion:

public sealed class Thingy : IReader<intbool>
{
    private readonly TimeSpan timeSpan;
 
    public Thingy(TimeSpan timeSpan)
    {
        this.timeSpan = timeSpan;
    }
 
    public bool Run(int environment)
    {
        return new TimeSpan(timeSpan.Ticks * environment).TotalDays < 1;
    }
}

I'm not claiming that this class makes sense. These articles are deliberate kept abstract in order to focus on structure and behaviour, rather than on practical application.

Return #

Apart from flattening or monadic bind, a monad must also define a way to put a normal value into the monad. Conceptually, I call this function return (because that's the name that Haskell uses):

public static IReader<R, A> Return<RA>(A a)
{
    return new ReturnReader<R, A>(a);
}
 
private class ReturnReader<RA> : IReader<R, A>
{
    private readonly A a;
 
    public ReturnReader(A a)
    {
        this.a = a;
    }
 
    public A Run(R environment)
    {
        return a;
    }
}

This implementation returns the a value and completely ignores the environment. You can do the same with a 'naked' function.

Left identity #

We need to identify the return function in order to examine the monad laws. Now that this is accomplished, let's see what the laws look like for the Reader monad, starting with the left identity law.

[Theory]
[InlineData(UriPartial.Authority, "https://example.com/f?o=o")]
[InlineData(UriPartial.Path, "https://example.net/b?a=r")]
[InlineData(UriPartial.Query, "https://example.org/b?a=z")]
[InlineData(UriPartial.Scheme, "https://example.gov/q?u=x")]
public void LeftIdentity(UriPartial astring u)
{
    Func<UriPartial, IReader<Uri, UriPartial>> @return =
        up => Reader.Return<Uri, UriPartial>(up);
    Func<UriPartial, IReader<Uri, string>> h =
        up => new UriPartReader(up);
 
    Assert.Equal(
        @return(a).SelectMany(h).Run(new Uri(u)),
        h(a).Run(new Uri(u)));
}

In order to compare the two Reader values, the test has to Run them and then compare the return values.

This test and the next uses a Reader implementation called UriPartReader, which almost makes sense:

public sealed class UriPartReader : IReader<Uri, string>
{
    private readonly UriPartial part;
 
    public UriPartReader(UriPartial part)
    {
        this.part = part;
    }
 
    public string Run(Uri environment)
    {
        return environment.GetLeftPart(part);
    }
}

Almost.

Right identity #

In a similar manner, we can showcase the right identity law as a test.

[Theory]
[InlineData(UriPartial.Authority, "https://example.com/q?u=ux")]
[InlineData(UriPartial.Path, "https://example.net/q?u=uuz")]
[InlineData(UriPartial.Query, "https://example.org/c?o=rge")]
[InlineData(UriPartial.Scheme, "https://example.gov/g?a=rply")]
public void RightIdentity(UriPartial astring u)
{
    Func<UriPartial, IReader<Uri, string>> f =
        up => new UriPartReader(up);
    Func<string, IReader<Uri, string>> @return =
        s => Reader.Return<Uri, string>(s);
 
    IReader<Uri, stringm = f(a);
 
    Assert.Equal(
        m.SelectMany(@return).Run(new Uri(u)),
        m.Run(new Uri(u)));
}

As always, even a parametrised test constitutes no proof that the law holds. I show the tests to illustrate what the laws look like in 'real' code.

Associativity #

The last monad law is the associativity law that describes how (at least) three functions compose. We're going to need three functions. For the purpose of demonstrating the law, any three pure functions will do. While the following functions are silly and not at all 'realistic', they have the virtue of being as simple as they can be (while still providing a bit of variety). They don't 'mean' anything, so don't worry too much about their behaviour. It is, as far as I can tell, nonsensical.

public sealed class F : IReader<intstring>
{
    private readonly char c;
 
    public F(char c)
    {
        this.c = c;
    }
 
    public string Run(int environment)
    {
        return new string(c, environment);
    }
}
 
public sealed class G : IReader<intbool>
{
    private readonly string s;
 
    public G(string s)
    {
        this.s = s;
    }
 
    public bool Run(int environment)
    {
        return environment < 42 || s.Contains("a");
    }
}
 
public sealed class H : IReader<int, TimeSpan>
{
    private readonly bool b;
 
    public H(bool b)
    {
        this.b = b;
    }
 
    public TimeSpan Run(int environment)
    {
        return b ?
            TimeSpan.FromMinutes(environment) :
            TimeSpan.FromSeconds(environment);
    }
}

Armed with these three classes, we can now demonstrate the Associativity law:

[Theory]
[InlineData('a', 0)]
[InlineData('b', 1)]
[InlineData('c', 42)]
[InlineData('d', 2112)]
public void Associativity(char aint i)
{
    Func<char, IReader<intstring>> f = c => new F(c);
    Func<string, IReader<intbool>> g = s => new G(s);
    Func<bool, IReader<int, TimeSpan>> h = b => new H(b);
 
    IReader<intstringm = f(a);
 
    Assert.Equal(
        m.SelectMany(g).SelectMany(h).Run(i),
        m.SelectMany(x => g(x).SelectMany(h)).Run(i));
}

In case you're wondering, the four test cases produce the outputs 00:00:00, 00:01:00, 00:00:42, and 00:35:12. You can see that reproduced below:

Haskell #

In Haskell, normal functions a -> b are already Monad instances, which means that you can easily replicate the functions from the Associativity test:

> f c = \env -> replicate env c
> g s = \env -> env < 42 || 'a' `elem` s
> h b = \env -> if b then secondsToDiffTime (toEnum env * 60) else secondsToDiffTime (toEnum env)

I've chosen to write the f, g, and h as functions that return lambda expressions in order to emphasise that each of these functions return Readers. Since Haskell functions are already curried, I could also have written them in the more normal function style with two normal parameters, but that might have obscured the Reader aspect of each.

Here's the composition in action:

> f 'a' >>= g >>= h $ 0
0s
> f 'b' >>= g >>= h $ 1
60s
> f 'c' >>= g >>= h $ 42
42s
> f 'd' >>= g >>= h $ 2112
2112s

In case you are wondering, 2,112 seconds is 35 minutes and 12 seconds, so all outputs fit with the results reported for the C# example.

What the above Haskell GHCi (REPL) session demonstrates is that it's possible to compose functions with Haskell's monadic bind operator >>= operator exactly because all functions are (Reader) monads.

Conclusion #

In Haskell, it can occasionally be useful that a function can be used when a Monad is required. Some Haskell libraries are defined in very general terms. Their APIs may enable you to call functions with any monadic input value. You can, say, pass a Maybe, a List, an Either, a State, but you can also pass a function.

C# and most other languages (F# included) doesn't come with that level of abstraction, so the fact that a function forms a monad is less useful there. In fact, I can't recall having made explicit use of this knowledge in C#, but one never knows if that day arrives.

In a similar vein, knowing that endomorphisms form monoids (and thereby also semigroups) enabled me to quickly identify the correct design for a validation problem.

Who knows? One day the knowledge that functions are monads may come in handy.

Next: The IO monad.



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, 14 November 2022 06:50:00 UTC

Tags



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