Monomorphic functors

Non-generic mappable containers, with a realistic example.

This article is an instalment in an article series about functors. Previous articles have covered Maybe, Lazy, and other functors. This article looks at what happens when you weaken one of the conditions that the article series so far has implied.

In the introductory article, I wrote:

As a rule of thumb, if you have a type with a generic type argument, it's a candidate to be a functor.

That still holds, but then Tyson Williams asks if that's a required condition. It turns out that it isn't. In this article, you'll learn about the implications of weakening this condition.

As is my habit with many of the articles in this article series, I'll start by uncovering the structure of the concept, and only later show a more realistic example.

Mapping strings #

So far in this article series, you've seen examples of containers with a generic type argument: Tree<T>, Task<T>, and so on. Furthermore, you've seen how a functor is a container with a structure-preserving map. This function has various names in different languages: Select, fmap, map, etcetera.

Until now, you've only seen examples where this mapping enables you to translate from one type argument to another. You can, for example, translate the characters in a string to Boolean values, like this:

> "Safe From Harm".Select(c => c.IsVowel())
Enumerable.WhereSelectEnumerableIterator<char, bool>
  { false, true, false, true, false, false, false, true, false, false, false, true, false, false }

This works because in C#, the String class implements various interfaces, among these IEnumerable<char>. By treating a string as an IEnumerable<char>, you can map each element. That's the standard IEnumerable functor (AKA the list functor).

What if you'd like to map the characters in a string to other characters? Perhaps you'd like to map vowels to upper case, and all other characters to lower case. You could try this:

> "Safe From Harm".Select(c => c.IsVowel() ? char.ToUpper(c) : char.ToLower(c))
Enumerable.WhereSelectEnumerableIterator<char, char>
  { 's', 'A', 'f', 'E', ' ', 'f', 'r', 'O', 'm', ' ', 'h', 'A', 'r', 'm' }

That sort of works, but as you can tell, the result isn't a string, it's an IEnumerable<char>.

This isn't a big problem, because one of the string constructor overloads take a char array as input, so you can do this:

> new string ("Safe From Harm".Select(c => c.IsVowel() ? char.ToUpper(c) : char.ToLower(c)).ToArray())
"sAfE frOm hArm"

It isn't the prettiest, but it gets the job done.

Monomorphic functor in C# #

If you contemplate the last example, you may arrive at the conclusion that you could package some of that boilerplate code in a reusable function. Since we're already talking about functors, why not call it Select?

public static string Select(this string source, Func<char, char> selector)
{
    return new string(source.AsEnumerable().Select(selector).ToArray());
}

It somewhat simplifies things:

> "Safe From Harm".Select(c => c.IsVowel() ? char.ToUpper(c) : char.ToLower(c))
"sAfE frOm hArm"

Since I deliberately wrote the Select method in the style of other Select methods (apart from the generics), you may wonder if C# query syntax also works?

> from c in "Army of Me"
. select c.IsVowel() ? char.ToUpper(c) : char.ToLower(c)
"ArmY Of mE"

It compiles and works! The C# compiler understands monomorphic containers!

I admit that I was quite surprised when I first tried this out.

Monomorphic functor in Haskell #

Surprisingly, in this particular instance, C# comes out looking more flexible than Haskell. This is mainly because in C#, functors are implemented as a special compiler feature, whereas in Haskell, Functor is defined using the general-purpose type class language feature.

There's a package that defines a MonoFunctor type class, as well as some instances. With it, you can write code like this:

ftg :: Text
ftg = omap (\c -> if isVowel c then toUpper c else toLower c) "Fade to Grey"

Even though Text isn't a Functor instance, it is a MonoFunctor instance. The value of ftg is "fAdE tO grEY".

All the normal functors ([], Maybe, etc.) are also MonoFunctor instances, since the normal Functor instance is more capable than a MonoFunctor.

Restaurant example #

While I've introduced the concept of a monomorphic functor with a trivial string example, I actually discovered the C# feature when I was working on some more realistic code. As I often do, I was working on a variation of an online restaurant reservation system. The code shown in the following is part of the sample code base that accompanies my book Code That Fits in Your Head.

The code base contained a rather complex variation of an implementation of the Maître d' kata. The MaitreD constructor looked like this:

public MaitreD(
    TimeOfDay opensAt,
    TimeOfDay lastSeating,
    TimeSpan seatingDuration,
    IEnumerable<Table> tables)

This had worked well when the system only dealt with a single restaurant, but I was now expanding it to a multi-tenant system and I needed to keep track of some more information about each restaurant, such as its name and ID. While I could have added such information to the MaitreD class, I didn't want to pollute that class with data it didn't need. While the restaurant's opening time and seating duration are necessary for the decision algorithm, the name isn't.

So I introduced a wrapper class:

public sealed class Restaurant
{
    public Restaurant(int id, string name, MaitreD maitreD)
    {
        Id = id;
        Name = name;
        MaitreD = maitreD;
    }
 
    public int Id { get; }
    public string Name { get; }
    public MaitreD MaitreD { get; }
 
    // More code follows...

I also added copy-and-update methods (AKA 'withers'):

public Restaurant WithId(int newId)
{
    return new Restaurant(newId, Name, MaitreD);
}
 
public Restaurant WithName(string newName)
{
    return new Restaurant(Id, newName, MaitreD);
}
 
public Restaurant WithMaitreD(MaitreD newMaitreD)
{
    return new Restaurant(Id, Name, newMaitreD);
}

Still, if you need to modify the MaitreD within a given Restaurant object, you first have to have a reference to the Restaurant so that you can read its MaitreD property, then you can edit the MaitreD, and finally call WithMaitreD. Doable, but awkward:

restaurant.WithMaitreD(restaurant.MaitreD.WithSeatingDuration(TimeSpan.FromHours(.5)))

So I got the idea that I might try to add a structure-preserving map to Restaurant, which I did:

public Restaurant Select(Func<MaitreD, MaitreD> selector)
{
    if (selector is null)
        throw new ArgumentNullException(nameof(selector));
 
    return WithMaitreD(selector(MaitreD));
}

The first time around, it enabled me to rewrite the above expression as:

restaurant.Select(m => m.WithSeatingDuration(TimeSpan.FromHours(.5)))

That's already a little nicer. It also handles the situation where you may not have a named Restaurant variable you can query; e.g. if you have a method that returns a Restaurant object, and you just want to continue calling into a Fluent API.

Then I thought, I wonder if query syntax works, too...

from m in restaurant
select m.WithSeatingDuration(TimeSpan.FromHours(.5))

And it does work!

I know that a lot of people don't like query syntax, but I think it has certain advantages. In this case, it actually isn't shorter, but it's a nice alternative. I particularly find that if I try to fit my code into a tight box, query syntax sometimes gives me an opportunity to format code over multiple lines in a way that's more natural than with method-call syntax.

Conclusion #

A monomorphic functor is still a functor, only it constrains the type of mapping you can perform. It can be useful to map monomorphic containers like strings, or immutable nested data structures like the above Restaurant class.

Next: Set is not a functor.

Comments

Tyson Williams #

Excellent article! I was planning to eventually write a blog post on this topic, but now there is no need.

I know that a lot of people don't like query syntax, but I think it has certain advantages. In this case, it actually isn't shorter, but it's a nice alternative. I particularly find that if I try to fit my code into a tight box, query syntax sometimes gives me an opportunity to format code over multiple lines in a way that's more natural than with method-call syntax.

Said another way, one objective measure that is better in this case when using query syntax is that the maximum line width is smaller. It is objective primarily in the sense that maximum line width is objective and secondarily in the sense that we generally agree that code with a lower maximum line width is typically easier to understand.

Another such objective measure of quality that I value is the maximum number of matching pairs of parentheses that are nested. This measure improves to two in your query syntax code from three in your previous code. The reason it was three before is because there are four levels of detail and your code decreases the level of detail three times: Restaurant to MaitreD, MaitreD to TimeSpan, and TimeSpan to double. Query syntax is one way to decrease the level of detail without having to introduce a pair of matching parentheses.

I find more success minimizing this measure of quality when taking a bottom-up approach. Using the Apply extension method from language-ext, which is like the forward pipe operator in F#, we can rewrite this code without any nested pairs of matching parentheses as

.5.Apply(TimeSpan.FromHours).Apply(m => m.WithSeatingDuration).Apply(restaurant.Select)

(I did not check if this code compiles. If it does not, it would be because the C# compiler is unsure how to implicitly convert some method group to its intended Func<,> delegate.) This code also has natural line-breaking points before each dot operator, which leads to a comfortable value for the maximum line width.

Another advantage of this code that I value is that the execution happens in the same order in which I (as an English speaker) read it: left to right. Your code before using the query syntax executed from right to left as dictated by the matching parentheses. In fact, since the dot operator is left associative, the degree to which execution occurs from left to right is inversely correlated to the number of nested pairs of parentheses. (One confusing thing here is the myriad of different semantic meanings in C# to the syntactic use of a pair of parentheses.)

2020-10-19 14:05 UTC

Mark Seemann #

Tyson, thank you for writing. I've never thought about measuring complexity by nested parentheses, but I like it! It makes intuitive sense.

I'm not sure it applies to LISP-like languages, but perhaps some reader comes by some day who can enlighten us.

2020-10-21 13:55 UTC

Tyson Williams #

While reading your articles about contravairant functors, a better name occured to me for what you called a monomorphic functor in this article.

For a covariant functor, its mapping function accepts a function with types that vary (i.e. differ). The order in which they vary matches the order that the types vary in the corresponding elevated function. For a contravariant functor, its mapping function also accepts a function with types that vary. However, the order in which they vary is reversed compared to the order that the types vary in the corresponding elevated function. For the functor in this article that you called a monomorphic functor, its mapping function accepts a function with types that do not vary. As such, we should call such a functor an invariant functor.

2021-09-14 01:01 UTC

Mark Seemann #

Tyson, thank you for writing. That's a great suggestion that makes a lot of sense.

The term invariant functor seems, however, to be taken by a wider definition.

"an invariant type T allows you to map from a to b if and only if a and b are isomorphic. In a very real sense, this isn't an interesting property - an isomorphism between a and b means that they're already the same thing to begin with."

Sandy Maguire, Thinking with Types

This seems, at first glance, to fit your description quite well, but when we try to encode this in a programming language, something surprising happens. We'd typically say that the types a and b are isomorphic if and only if there exists two functions a -> b and b -> a. Thus, we can encode this in a Haskell type class like this one:

class Invariant f where
  invmap :: (a -> b) -> (b -> a) -> f a -> f b

I've taken the name of both type class and method from Thinking with Types, but we find the same naming in Data.Functor.Invariant. The first version of the invariant package is from 2012, so assume that Sandy Maguire has taken the name from there (and not the other way around).

There's a similar-looking definition in Cats (although I generally don't read Scala), and in C# we might define a method like this:

public sealed class Invariant<A>
{
    public Invariant<B> InvMap<B>(Func<A, B> selector1, Func<B, A> selector2)
}

This seems, at first glance, to describe monomorphic functors quite well, but it turns out that it's not quite the same. Consider mapping of String, as discussed in this article. The MonoFunctor instance of String (or, generally, [a]) lifts a Char -> Char function to String -> String.

In Haskell, String is really a type alias for [Char], but what happens if we attempt to describe String as an Invariant instance? We can't, because String has no type argument.

We can, however, see what happens if we try to make [a] an Invariant instance. If we can do that, we can try to experiment with Char's underlying implementation as a number:

"To convert a Char to or from the corresponding Int value defined by Unicode, use toEnum and fromEnum from the Enum class respectively (or equivalently ord and chr)."

Char documentation

ord and chr enable us to treat Char and Int as isomorphic:

> ord 'h'
104
> chr 104
'h'

Since we have both Char -> Int and Int -> Char, we should be able to use invmap ord chr, and indeed, it works:

> invmap ord chr "foo"
[102,111,111]

When, however, we look at the Invariant [] instance, we may be in for a surprise:

instance Invariant [] where
  invmap f _ = fmap f

The instance uses only the a -> b function, while it completely ignores the b -> a function! Since the instance uses fmap, rather than map, it also strongly suggests that all (covariant) Functor instances are also Invariant instances. That's also the conclusion reached by the invariant package. Not only that, but every Contravariant functor is also an Invariant functor.

That seems to completely counter the idea that a and b should be isomorphic. I can't say that I've entirely grokked this disconnect yet, but it seems to me to be an artefact of instances' ability to ignore either of the functions passed to invmap. At least we can say that client code can't call invmap unless it supplies both functions (here I pretend that undefined doesn't exist).

If we go with the Haskell definition of things, an invariant functor is a much wider concept than a monomorphic functor. Invariant describes a superset that contains both (covariant) Functor and Contravariant functor. This superset is more than just the union of those two sets, since it also includes containers that are neither Functor nor Contravariant, for example Endo:

instance Invariant Endo where
  invmap f g (Endo h) = Endo (f . h . g)

For example, toUpper is an endomorphism, so we can apply it to invmap and evaluate it like this:

> (appEndo $ invmap ord chr $ Endo toUpper) 102
70

This example takes the Int 102 and converts it to a String with chr:

> chr 102
'f'

It then applies 'f' to toUpper:

> toUpper 'f'
'F'

Finally, it converts 'F' with ord:

> ord 'F'
70

Endomorphisms are neither covariant nor contravariant functors - they are invariant functors. They may also be monomorphic functors. The mono-traversable package doesn't define a MonoFunctor instance for Endo, but that may just be an omission. It'd be an interesting exercise to see if such an instance is possible. I don't know yet, but I think that it is...

For now, though, I'm going to leave that as an exercise. Readers who manage to implement a lawful instance of MonoFunctor for Endo should send a pull request to the mono-traversable package.

Finally, a note on words. I agree that invariant functor would also have been a good description of monomorphic functors. It seems to me that in both mathematics and programming, there's sometimes a 'land-grab' of terms. The first person to think of a concept gets to pick the word. If the concept is compelling, the word may stick.

This strikes me as an unavoidable consequence of how knowledge progresses. Ideas rarely spring forth fully formed. Often, someone gets a half-baked idea and names it before fully understanding it. When later, more complete understanding emerges, it may be too late to change the terminology.

This has happened to me in this very article series, which I titled From design patterns to category theory before fully understanding where it'd lead me. I've later come to realise that we need only abstract algebra to describe monoids, semigroups, et cetera. Thus, the article series turned out to have little to do with category theory, but I couldn't (wouldn't) change the title and the URL of the original article, since it was already published.

The same may be the case with the terms invariant functors and monomorphic functors. Perhaps invariant functors should instead have been called isomorphic functors...

2021-09-14 8:22 UTC

Mark Seemann #

I've started a small article series on invariant functors.

2022-08-01 5:58 UTC

Published: Monday, 19 October 2020 07:36:00 UTC

Monomorphic functors by Mark Seemann

Mapping strings #

Monomorphic functor in C# #

Monomorphic functor in Haskell #

Restaurant example #

Conclusion #

Comments

Wish to comment?

Published

Tags