1098 words
5 minutes
Understanding C# Covariance And Contravariance (5) Higher-order functions
2009-08-31
.NET
.NET
/
C#
/
C# 4.0
/
Covariance And Contravariance

Understanding C# Covariance And Conreavariance:

Higher-order functions are functions which either take one or more functions as input, or output a function. The other functions are called first-order functions.

public static partial class HigherOrder
{
    public static void FirstOrderAndHigherOrder()
    {
        { Action action = () => { }; } // First-order function.
        Action<Action> actionIn = action => action(); // Higher-order function


        Func<object> func = () => new object(); // First-order function.
        Func<Func<object>> funcOut = () => func; // Higher-order function
    }
}

So far, all the covariance/contravariance demonstrations are using first-order functions. For example:

public static partial class HigherOrder
{
    // System.Action<T>.
    public delegate void Action<in TIn>(TIn @in);


    public static void ContravarianceForFirstOrder()
    {
        // First-order functions.
        Action<Derived> derivedIn = (Derived @in) => { };
        Action<Base> baseIn = (Base @in) => { };


        // Contravariance of input: Action<Base> "is a" Action<Derived>.
        // Or: T is contravariant for Action<in T>.
        derivedIn = baseIn;
    }
}

Most LINQ query methods are higher-order functions. In the fore mentioned example:

public static partial class LinqToObjects
{
    public static IEnumerable<int> Positive(IEnumerable<int> source)
    {
        return source.Where(value => value > 0);
    }
}

the lambda expression is a anonymous first-order function, and Where is a higher-order function.

Variance of input#

The following delegate type:

public delegate void ActionIn<T>(Action<T> action);

can represent a higher-order function type, which take a function as parameter.

Regarding T for Action is contravariant, is T still contravariant for ActionIn? The answer is no. The following code cannot be compiled:

public static partial class HigherOrder
{
#if Uncompilable
    public delegate void ActionIn<in T>(Action<T> action);


    public static void ContravarianceOfInput()
    {
        // Higher-order funcitons:
        ActionIn<Derived> derivedInIn = (Action<Derived> derivedIn) => derivedIn(new Derived());
        ActionIn<Base> baseInIn = (Action<Base> baseIn) => baseIn(new Base());


        // Regarding Action<Base> "is a" ActionIn<Derived>,
        // assumes there is still contravariance of input,
        // which is, ActionIn<Base> "is a" ActionIn<Derived>
        derivedInIn = baseInIn;


        // When calling baseInIn, derivedInIn executes.
        // baseInIn should have a Action<Base> input, while derivedInIn requires a Action<Derived> input.
        // The actual Action<Base> "is a" required Action<Derived>. This binding should always works.
        baseInIn(new Action<Base>((Base @in) => { }));
    }
#endif
}

What is the problem here? And how to fix?

Revisit covariance and contravariance#

First, covariance/contravariance can be viewed in another way:

  • Func: Derived “is a” Base => Func “is a” Func. This is named covariance (not out-variance) because the direction of “is a” relationship remains.
  • Action: Derived “is a” Base => Action “is a” Action. This is named contravariance (not in-variance) because the direction of “is a” relationship reverses.
    • In the original “is a” relationship, Derived is on the left side, Base is on the right side
    • In the new “is a” relationship, Derived goes to the right, and Base goes to the left

To examine the variance for higher-order functions:

  • Func can be made higher order, by just replacing T with Func. Then:
    1. Derived “is a” Base
    2. => Func “is a” Func (In Func, replaces T with Derived/Base. Comparing to 1, T is covariant for Func.)
    3. => Func<Func> “is a” Func<Func> (In Func, replaces T with Func/Func. Comparing to 1, T is covariant for Func<Func>.)
    4. => Func<Func<Func>> “is a” Func<Func<Func>> (In Func, replaces T with Func<Func> /Func<Func> . Comparing to 1, T is covariant for Func<Func<Func>>.)
    5. => …
  • Action can be made higher order, by just replacing T with Action. Then:
    1. Derived “is a” Base
    2. => Action “is a” Action (In Action, replaces T with Base/Derived. the direction of “Is-a” relationship reverses. Comparing to 1, T is contravariant for Action.)
    3. => Action<Action> “is a” Action<Action> (In Action, replaces T with Action/Action. the direction of “Is-a” relationship reverses again, so that Derived goes back to left, and Base goes back to right. Comparing to 1, T is covariant for Action<Action>.)
    4. => Action<Action<Action>> “is a” Action<Action<Action>> (In Action, replaces T with Action<Action> /Action<Action>. Comparing to 1, T is contravariant for Action<Action<Action>>.)
    5. => …

In above code, ActionIn is equivalent to Action<Action>. So, T is covariant for Action<Action>/ActionIn, not contravariant. The fix is to use out keyword to decorate T, and swap the binding:

public static partial class HigherOrder
{
    // Action<Action<T>>
    public delegate void ActionIn<out T>(Action<T> action);


    public static void CovarianceOfInput() // Not contravariance.
    {
        // Higher-order funcitons:
        ActionIn<Derived> derivedInIn = (Action<Derived> derivedIn) => derivedIn(new Derived());
        ActionIn<Base> baseInIn = (Action<Base> baseIn) => baseIn(new Base());


        // Not derivedInIn = baseInIn;
        baseInIn = derivedInIn;


        // When calling baseInIn, derivedInIn executes.
        // baseInIn should have a Action<Base> input, while derivedInIn requires a Action<Derived> input.
        // The actual Action<Base> "is a" required Action<Derived>. This binding always works.
        baseInIn(new Action<Base>((Base @in) => { }));
    }
}

The other case, type parameter as output, is straightforward, because the type parameter is always covariant for any first-order/higher-order function:

public static partial class HigherOrder
{
    public delegate Func<TOut> FuncOut<out TOut>();


    public static void CovarianceOfOutput()
    {
        // First order functions.
        Func<Base> baseOut = () => new Base();
        Func<Derived> derivedOut = () => new Derived();
        // T is covarianct for Func<T>.
        baseOut = derivedOut;


        // Higher-order funcitons:
        FuncOut<Base> baseOutOut = () => baseOut;
        FuncOut<Derived> derivedOutOut = () => derivedOut;


        // Covariance of output: FuncOut<Derived> "is a" FuncOut<Base>
        baseOutOut = derivedOutOut;


        // When calling baseOutOut, derivedOutOut executes.
        // baseOutOut should output a Func<Base>, while derivedOutOut outputs a Func<Derived>.
        // The actual Func<Derived> "is a" required Func<Base>. This binding always works.
        baseOut = baseOutOut();
    }
}

Variances for higher-order function#

Variances are straightforward for first-order functions:

  • Covariance of output (out keyword): Derived “is a” Base => Func “is a” Func (“Is-a” remains.)
  • Contravariance of input (in keyword): Derived “is a” Base => Action “is a” Action (“Is-a” reverses.)

For higher-order functions:

  • Output is always covariant:
    • Derived “is a” Base
    • => Func “is a” Func
    • => Func<Func> “is a” Func<Func>
    • => …
  • Input can be either contravariant or covariant, depends on how many times the direction of “is-a” relationship reverses:
    1. Derived “is a” Base
    2. => Action “is a” Action (contravariance)
    3. => Action<Action> “is a” Action<Action> (covariance)
    4. => Action<Action<Action>> “is a” Action<Action<Action>> (contravariance)
    5. => …
public static class OutputCovarianceForHigherOrder
{
    public delegate T Func<out T>(); // Covariant T as output.


    // Func<Func<T>>
    public delegate Func<T> FuncOut<out T>(); // Covariant T as output.


    // Func<Func<Func<T>>>
    public delegate FuncOut<T> FuncOutOut<out T>(); // Covariant T as output.


    // Func<Func<Func<Func<T>>>>
    public delegate FuncOutOut<T> FuncOutOutOut<out T>(); // Covariant T as output.


    // ...
}


public static class InputVarianceReversalForHigherOrder
{
    public delegate void Action<in T>(T @in); // Contravariant T as input.


    // Action<Action<T>>
    public delegate void ActionIn<out T>(Action<T> action); // Covariant T as input.


    // Action<Action<Action<T>>>
    public delegate void ActionInIn<in T>(ActionIn<T> actionIn); // Contravariant T as input.


    // Action<Action<Action<Action<T>>>>
    public delegate void ActionInInIn<out T>(ActionInIn<T> actionInIn); // Covariant T as input.


    // ...
}
Understanding C# Covariance And Contravariance (5) Higher-order functions
https://dixin.github.io/posts/understanding-csharp-covariance-and-contravariance-5-higher-order-functions/
Author
Dixin
Published at
2009-08-31
License
CC BY-NC-SA 4.0
Understanding C# Covariance And Contravariance (4) Arrays
Understanding C# Covariance And Contravariance (2) Interfaces
© 2025 Dixin. All Rights Reserved. / RSS / Sitemap
Powered by Astro & Fuwari