Sunday, July 1, 2012

Understanding variance using functions

Statically typed languages that support parametrized types (generics) and types hierarchies (inheritance) sometimes support covariance and contravariance, concepts which many find confusing.

I think I have finally understood these, thanks to a blog post by Tomas Petricek on the subject.

In this post I'll try to formulate my own understanding, and how I got there using functions instead of classes.

Step 1: values

Let us start easy, with simple values. Consider a base type, for instance IPrintable, and two derived types MyString and MyInt.

I can use a string with any function that accepts a printable object.

type IPrintable =
    interface
    end

type MyInt() =
    interface IPrintable

type MyString() =
    interface IPrintable

// Step 1: simple value
let ``expects an IPrintable``(x : IPrintable) = ()

let n = MyInt()
let s = MyString()

``expects an IPrintable`` n // OK
``expects an IPrintable`` s // OK

Step 2: Parameterless functions

The next step deals with a function that takes another function which doesn't take any parameter and returns an IPrintable. If that's confusing, think of a generic function that creates a new random printable object, then prints it. This function would let the caller be responsible for providing a function which creates the random printable object.

The code below illustrates this, but I've removed the random part. Note also that F# does not support covariance, which forces me to use flexible types.

// Step 2: a function without arguments
// No covariance in F#, see http://msdn.microsoft.com/en-us/library/dd233198.aspx
let ``expects a constructor``(f : unit -> #IPrintable) = ()

let mkInt() = MyInt()
let mkString() = MyString()

``expects a constructor`` mkInt // OK
``expects a constructor`` mkString // OK

Step 3: Functions of a single parameter

Let us now consider a variation of the function described above where the function responsible for creating a random object takes a MyInt (it could be the seed, for instance). Assume I have two functions newRandomMyIntWithSeed and newRandomMyStringWithSeed that both take an IPrintable. Importantly, these two functions are safe to call with any instance of IPrintable. One can imagine that such a function would use the printable representation to generate some number, used as the seed for the random generator.

I can use newRandomMyIntWithSeed and newRandomMyStringWithSeed where a function with signature MyInt -> IPrintable is expected. Notice how the relationship on types for the parameter has been inverted, compared with the case of a value or a return type. This is an example of contravariance.

No code here, but see below for a more complete example.

Step 4: Functions of multiple parameters

It's possible to keep adding more parameters, and currying helps understand which functions are safe to use.
For this last example, I'll switch to another set of types: IScalar and IVector, with their respective implementations Float32 and Vector3. We can imagine there might be other implementations, e.g. Float64 and Vector4. A function which computes the product of a scalar and a vector must return a vector. Using currying, it can also be seen as a function takes a scalar and returns a function which takes a vector and returns a vector.

If I have a function with signature Float32 -> Vector3 -> Vector3, where can I use it?

I can use it where the exact same signature is expected, obviously.

I can use it where a Float32 -> Vector3 -> IVector is expected:
  • The final return types match, as shown in step 1.
  • The other parameters obviously match.
I cannot use it where a Float32 -> IVector -> Vector3 or a Float32 -> IVector -> IVector is expected. Although the final return types are compatible in either case, the next step in the matching process fails.

A more general function with signature IScalar -> IVector -> Vector3 can be used where a Float32 -> Vector3 -> IVector is expected:
  • Vector3 as a simple value can be used anywhere any IVector is expected.
  • A function accepting any IVector accepts in particular Vector3, meaning such a function can be used where a function expecting a Vector3 is expected (!), provided their return types match (which was shown above).
  • By the same reasoning applied on the first (and only) argument of the function with signature IScalar -> (IVector -> Vector3), we conclude that the more general function can be used.
The code below illustrates this example.

// Step 4: a function with arguments
type IScalar =
    interface
    end

type IVector =
    interface
    end

type Float32() =
    interface IScalar

type Vector3() =
    interface IVector

let prodGeneral (s : IScalar) (v : IVector) : Vector3 =
    failwith "..."

// Interesting: flexible types are needed for the return type (no covariance),
// but not for the parameters (contravariance)
let apply prod (s : Float32) (v : Vector3) : #IVector = prod s v // OK

let k = Float32()
let v = Vector3()
let u = apply prodGeneral k v

Conclusion

I hope that wasn't excessively complex. Other explanations on the subject which I have seen often use container classes instead of functions, which is confusing, as it brings in read-only vs writable and reference-type vs value-type into the picture. Another problem is that using containers tends to mislead readers into thinking that T<B> can always be used where T<A> is expected if B inherits from A. Although that makes sense when T is IEumerable, it doesn't work when T is Action.
Looking at the problem with a functional mindset really helped clarify the picture.

I was a bit disappointed when I first saw F# did not support covariance, but flexible types do the job with very little additional syntax (a single # before the type). I was surprised to notice F# does support contravariance for function parameters, as it's often heard that F# supports neither covariance nor contravariance. That's not quite true, as it turns out.

If functions are powerful enough to model all other types, it may be interesting to see what kind of variance one should expect for unions, tuples, records and eventually classes. That's probably already been done, but it would be an interesting exercise.

3 comments:

Dave Thomas said...

Flexible types are good but it can be irritating to do the coercion which is implicit in C#. I suppose thats my biggest gripe. You can't expect an explicitly typed language to drop its guard for you.

Johann Deneux said...

@Dave: In this particular case, I don't think you can call it "dropping its guard".

(unit -> Something) should be implicitly convertible to (unit -> ISomething), if only for the sake of consistency with:

- Something being implicitly convertible to ISomething and,

- (ISomething -> unit) being implicitly convertible to (Something -> unit).

Dave Thomas said...

I was just being polite! :)

I think these sorts of issues should of been addressed in F#3.0