Any function gives rise to a contravariant functor. An article for object-oriented programmers.

This article is an instalment in an article series about contravariant functors. It assumes that you've read the introduction. In the first example article, you saw how the Command Handler pattern gives rise to a contravariant functor. The next article gave another example based on predicates.

In the overview article I also mentioned that equivalence and comparison form contravariant functors. Each can be described with an interface, or just function syntax. Let's put them in a table to compare them:

Name C# method signature C# delegate(s) Haskell type(s)
Command Handler void Execute(TCommand command); Action<TCommand> a -> ()
a -> IO ()
Specification bool IsSatisfiedBy(T candidate); Predicate<T>
Func<T, bool>
a -> Bool
Equivalence bool Equals(T x, T y); Func<T, T, bool> a -> a -> Bool
Comparison int Compare(T x, T y); Func<T, T, int> a -> a -> Ordering

In some cases, there's more than one possible representation. For example, in C# Predicate is isomorphic to Func<T, bool>. When it comes to the Haskell representation of a Command Handler, the 'direct' translation of Action<T> is a -> (). In (Safe) Haskell, however, a function with that type is always a no-op. More realistically, a 'handler' function would have the type a -> IO () in order to allow side effects to happen.

Do you notice a pattern?

Input variance #

There's a pattern emerging from the above table. Notice that in all the examples, the function types are generic (AKA parametrically polymorphic) in their input types.

This turns out to be part of a general rule. The actual rule is a little more complicated than that. I'll recommend Sandy Maguire's excellent book Thinking with Types if you're interested in the details.

For first-order functions, you can pick and fix any type as the return type and let the input type(s) vary: that function will give rise to a contravariant functor.

In the above table, various handlers fix void (which is isomorphic to unit (()) as the output type and let the input type vary. Both Specification and Equivalence fix bool as the output type, and Comparison fix int (or, in Haskell, the more sane type Ordering), and allow the input type to vary.

You can pick any other type. If you fix it as the output type for a function and let the input vary, you have the basis for a contravariant functor.

Reader #

Consider this IReader interface:

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

If you fix the environment type R and let the output type A vary, you have a (covariant) functor. If, on the other hand, you fix the output type A and allow the input type R to vary, you can have yourself a contravariant functor:

public static IReader<R1, A> ContraMap<RR1A>(
    this IReader<R, A> reader,
    Func<R1, R> selector)
    return new FuncReader<R1, A>(r => reader.Run(selector(r)));

As an example, you may have this (rather unwarranted) interface implementation:

public sealed class MinutesReader : IReader<int, TimeSpan>
    public TimeSpan Run(int environment)
        return TimeSpan.FromMinutes(environment);

You can fix the output type to TimeSpan and let the input type vary using the ContraMap functions:

public void WrappedContravariantExample()
    IReader<int, TimeSpan> r = new MinutesReader();
    IReader<string, TimeSpan> projected = r.ContraMap((string s) => int.Parse(s));
    Assert.Equal(new TimeSpan(0, 21, 0), projected.Run("21"));

When you Run the projected reader with the input string "21", the ContraMap function first calls the selector, which (in this case) parses "21" to the integer 21. It then calls Run on the 'original' reader with the value 21. Since the 'original' reader is a MinutesReader, the output is a TimeSpan value that represents 21 minutes.

Raw functions #

As was also the case when I introduced the Reader (covariant) functor, the IReader interface is just a teaching device. You don't need the interface in order to turn first-order functions into contravariant functors. It works on raw functions too:

public static Func<R1, A> ContraMap<RR1A>(this Func<R, A> func, Func<R1, R> selector)
    return r => func(selector(r));

In the following I'm going to dispense with the IReader interface and instead work with raw functions.

Identity law #

A ContraMap method with the right signature isn't enough to be a contravariant functor. It must also obey the contravariant functor laws. As usual, it's proper computer-science work to actually prove this, but you can write some tests to demonstrate the identity law for functions. In this article, you'll see parametrised tests written with First, the identity law:

public void ContravariantIdentityLaw(int input)
    Func<intstringf = i => i.ToString();
    Func<intstringactual = f.ContraMap((int i) => i);
    Assert.Equal(f(input), actual(input));

Here I'm using the (int i) => i lambda expression as the identity function. As usual, you can't easily compare functions for equality, so you'll have to call them to verify that they produce the same output, which they do.

Composition law #

Like the above example, you can also write a parametrised test that demonstrates that ContraMap obeys the composition law for contravariant functors:

public void ContravariantCompositionLaw(double input)
    Func<stringinth = s => s.Length;
    Func<double, TimeSpan> f = i => TimeSpan.FromSeconds(i);
    Func<TimeSpan, stringg = ts => ts.ToString();
        h.ContraMap((double d) => g(f(d)))(input),

This test defines two local functions, f and g. Once more, you can't directly compare methods for equality, so instead you have to invoke both compositions to verify that they return the same int value.

They do.

Isomorphisms #

Now that we understand that any first-order function is contravariant, we can see that the previous examples of predicates, handlers, comparisons, and equivalences are really just special cases of the Reader contravariant functor.

For example, Predicate<T> is trivially isomorphic to Func<T, bool>. Still, it might be worthwhile to flesh out how other translations might work:

public static ISpecification<T> AsSpecification<T>(this Predicate<T> predicate)
    return new DelegateSpecificationAdapter<T>(predicate);
public static ISpecification<T> AsSpecification<T>(this Func<T, boolpredicate)
    return new DelegateSpecificationAdapter<T>(predicate);
private class DelegateSpecificationAdapter<T> : ISpecification<T>
    private readonly Predicate<T> predicate;
    public DelegateSpecificationAdapter(Predicate<T> predicate)
        this.predicate = predicate;
    public DelegateSpecificationAdapter(Func<T, boolpredicate) :
        this((Predicate<T>)(x => predicate(x)))
    public bool IsSatisfiedBy(T candidate)
        return predicate(candidate);
public static Predicate<T> AsPredicate<T>(this ISpecification<T> specification)
    return candidate => specification.IsSatisfiedBy(candidate);
public static Func<T, bool> AsFunc<T>(this ISpecification<T> specification)
    return candidate => specification.IsSatisfiedBy(candidate);

Above are conversions between ISpecification<T> on the one hand, and Predicate<T> and Func<T, bool> on the other. Not shown are the conversions between Predicate<T> and Func<T, bool>, since they are already built into C#.

Most saliently in this context is that it's possible to convert both ISpecification<T> and Predicate<T> to Func<T, bool>, and Func<T, bool> to ISpecification<T> or Predicate<T> without any loss of information. Specifications and predicates are isomorphic to an open constructed Func - that is, a Reader.

I'll leave the other isomorphisms as exercises, with the following hints:

  • You can only convert an ICommandHandler<T> to a Func if you introduce a Unit value, but you could also try to use Action<T>.
  • For Equivalence, you'll need to translate the two input arguments to a single object or value.
  • The same goes for Comparison.

All the contravariant functor examples shown so far in this article series are isomorphic to the Reader contravariant functor.

Particularly, this also explains why it was possible to make IEqualityComparer.GetHashCode contravariant.

Haskell #

The Haskell base package comes with a Contravariant type class and various instances.

In order to replicate the above MinutesReader example, we can start by implementing a function with equivalent behaviour:

Prelude Data.Functor.Contravariant Data.Time> minutes m = secondsToDiffTime (60 * m)
Prelude Data.Functor.Contravariant Data.Time> :t minutes
minutes :: Integer -> DiffTime

As GHCi reports, the minutes function has the type Integer -> DiffTime (DiffTime corresponds to .NET's TimeSpan).

The above C# example contramaps a MinutesReader with a function that parses a string to an int. In Haskell, we can use the built-in read function to equivalent effect.

Here's where Haskell gets a little odd. In order to fit the Contravariant type class, we need to flip the type arguments of a function. A normal function is usually written as having the type a -> b, but we can also write it as the type (->) a b. With this notation, minutes has the type (->) Integer DiffTime.

In order to make minutes a contravariant instance, we need to fix DiffTime and let the input vary. What we'd like to have is something like this: (->) a DiffTime. Alas, that's not how you define a legal type class instance in Haskell. We have to flip the types around so that we can partially apply the type. The built-in newtype Op does that:

Prelude Data.Functor.Contravariant Data.Time> :t Op minutes
Op minutes :: Op DiffTime Integer

Since the general, partially applied type Op a is a Contravariant instance, it follows that the specific type Op DiffTime is. This means that we can contramap Op minutes with read:

Prelude Data.Functor.Contravariant Data.Time> :t contramap read (Op minutes)
contramap read (Op minutes) :: Op DiffTime String

Notice that this maps an Op DiffTime Integer to an Op DiffTime String.

How do you use it?

You can retrieve the function wrapped in Op with the getOp function:

Prelude Data.Functor.Contravariant Data.Time> :t getOp (contramap read (Op minutes))
getOp (contramap read (Op minutes)) :: String -> DiffTime

As you can tell, this expression indicates a String -> DiffTime function. This means that if you call it with a string representation of an integer, you should get a DiffTime value back:

Prelude Data.Functor.Contravariant Data.Time> getOp (contramap read (Op minutes)) "21"

As usual, this is way too complicated to be immediately useful, but it once again demonstrates that contravariant functors are ubiquitous.

Conclusion #

Normal first-order functions give rise to contravariant functors. With sufficiently tinted glasses, most programming constructs look like functions. To me, at least, this indicates that a contravariant functor is a fundamental abstraction in programming.

This result looks quite abstract, but future articles will build on it to arrive at a (to me) fascinating conclusion. Until then, though...

Next: Functor variance compared to C#'s notion of variance.

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, 04 October 2021 05:47:00 UTC


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