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

This article is an instalment in an article series about functors. In a previous article you saw, for example, how to implement the Maybe functor in C#. In this article, you'll see another functor example: Reader.

The Reader functor is similar to the Identity functor in the sense that it seems practically useless. If that's the case, then why care about it?

As I wrote about the Identity functor:

"The inutility of Identity doesn't mean that it doesn't exist. The Identity functor exists, whether it's useful or not. You can ignore it, but it still exists. In C# or F# I've never had any use for it (although I've described it before), while it turns out to be occasionally useful in Haskell, where it's built-in. The value of Identity is language-dependent."

The same holds for Reader. It exists. Furthermore, it teaches us something important about ordinary functions.

Reader interface #

Imagine the following interface:

public interface IReader<RA>
    A Run(R environment);

An IReader object can produce a value of the type A when given a value of the type R. The input is typically called the environment. A Reader reads the environment and produces a value. A possible (although not particularly useful) implementation might be:

public class GuidToStringReader : IReader<Guid, string>
    private readonly string format;
    public GuidToStringReader(string format)
        this.format = format;
    public string Run(Guid environment)
        return environment.ToString(format);

This may be a silly example, but it illustrates that a a simple class can implement a constructed version of the interface: IReader<Guid, string>. It also demonstrates that a class can take further arguments via its constructor.

While the IReader interface only takes a single input argument, we know that an argument list is isomorphic to a parameter object or tuple. Thus, IReader is equivalent to every possible function type - up to isomorphism, assuming that unit is also a value.

While the practical utility of the Reader functor may not be immediately apparent, it's hard to argue that it isn't ubiquitous. Every method is (with a bit of hand-waving) a Reader.

Functor #

You can turn the IReader interface into a functor by adding an appropriate Select method:

public static IReader<R, B> Select<ABR>(this IReader<R, A> reader, Func<A, B> selector)
    return new FuncReader<R, B>(r => selector(reader.Run(r)));
private sealed class FuncReader<RA> : IReader<R, A>
    private readonly Func<R, A> func;
    public FuncReader(Func<R, A> func)
        this.func = func;
    public A Run(R environment)
        return func(environment);

The implementation of Select requires a private class to capture the projected function. FuncReader is, however, an implementation detail.

When you Run a Reader, the output is a value of the type A, and since selector is a function that takes an A value as input, you can use the output of Run as input to selector. Thus, the return type of the lambda expression r => selector(reader.Run(r)) is B. Therefore, Select returns an IReader<R, B>.

Here's an example of using the Select method to project an IReader<Guid, string> to IReader<Guid, int>:

public void WrappedFunctorExample()
    IReader<Guid, stringr = new GuidToStringReader("N");
    IReader<Guid, intprojected = r.Select(s => s.Count(c => c.IsDigit()));
    var input = new Guid("{CAB5397D-3CF9-40BB-8CBD-B3243B7FDC23}");
    Assert.Equal(16, projected.Run(input));

The expected result is 16 because the input Guid contains 16 digits (the numbers from 0 to 9). Count them if you don't believe me.

As usual, you can also use query syntax:

public void QuerySyntaxFunctorExample()
    var projected =
        from s in new GuidToStringReader("N")
        select TimeSpan.FromMinutes(s.Length);
    var input = new Guid("{FE2AB9C6-DDB1-466C-8AAA-C70E02F964B9}");
    Assert.Equal(32, projected.Run(input).TotalMinutes);

The actual computation shown here makes little sense, since the result will always be 32, but it illustrates that arbitrary projections are possible.

Raw functions #

The IReader<R, A> interface isn't really necessary. It was just meant as an introduction to make things a bit easier for object-oriented programmers. You can write a similar Select extension method for any Func<R, A>:

public static Func<R, B> Select<ABR>(this Func<R, A> func, Func<A, B> selector)
    return r => selector(func(r));

Compare this implementation to the one above. It's essentially the same lambda expression, but now Select returns the raw function instead of wrapping it in a class.

In the following, I'll use raw functions instead of the IReader interface.

First functor law #

The Select method obeys the first functor law. As usual, it's proper computer-science work to actually prove this, but you can write some tests to demonstrate the first functor law for the IReader<R, A> interface. In this article, you'll see parametrised tests written with First, the first functor law:

public void FirstFunctorLaw(string input)
    T id<T>(T x) => x;
    Func<stringintf = s => s.Length;
    Func<stringintactual = f.Select(id);
    Assert.Equal(f(input), actual(input));

The 'original' Reader f (for function) takes a string as input and returns its length. The id function (which isn't built-in in C#) is implemented as a local function. It returns whichever input it's given.

Since id returns any input without modifying it, it'll also return any number produced by f without modification.

To evaluate whether f is equal to f.Select(id), the assertion calls both functions with the same input. If the functions have equal behaviour, they ought to return the same output.

The above test cases all pass.

Second functor law #

Like the above example, you can also write a parametrised test that demonstrates that a function (Reader) obeys the second functor law:

public void SecondFunctorLaw(string input)
    Func<stringinth = s => s.Length;
    Func<intboolg = i => i % 2 == 0;
    Func<boolcharf = b => b ? 't' : 'f';
        h.Select(i => f(g(i)))(input));

You can't easily compare two different functions for equality, so, like above, this test defines equality as the functions producing the same result when you invoke them.

Again, while the test doesn't prove anything, it demonstrates that for the five test cases, it doesn't matter if you project the 'original' Reader h in one or two steps.

Haskell #

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

> h = length
> g i = i `mod` 2 == 0
> f b = if b then 't' else 'f'
> (fmap f $ fmap g $ h) "ploeh"

Here f, g, and h are equivalent to their above C# namesakes, while the last line composes the functions stepwise and calls the composition with the input string "ploeh". In Haskell you generally read code from right to left, so this composition corresponds to h.Select(g).Select(f).

Conclusion #

Functions give rise to functors, usually known collectively as the Reader functor. Even in Haskell where this fact is ingrained into the fabric of the language, I rarely make use of it. It just is. In C#, it's likely to be even less useful for practical programming purposes.

That a function a -> b forms a functor, however, is an important insight into just what a function actually is. It describes an essential property of functions. In itself this may still seem underwhelming, but mixed with some other properties (that I'll describe in a future article) it can produce some profound insights. So stay tuned.

Next: The IO functor.

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.


Monday, 30 August 2021 05:42:00 UTC


"Our team wholeheartedly endorses Mark. His expert service provides tremendous value."
Hire me!
Published: Monday, 30 August 2021 05:42:00 UTC