Sunday, July 14, 2013

Function1[-T1, +R] -- What the heck?

In this post, I'll try to cover an important notion of the Scala's Type System -- and a Java's Terra Incognita.

(generic) Type covariance or contravariance.

Ho yeah, I heard you... yet another post... right?
... right! but it seems that it needs a more gentle one, where Category Theory is left apart. Because, Category Theory must come when you want yet more fun, not to get basic concepts!

That's why we'll see what are these constraints in a more pragmatic way, using (important) examples.
Afterwards, I'll let you read the blogs using Category Theory ... if you like.

I thought that taking the problem from the Java side might be easier to explain, thus the following parts
  • Problem: Assignments failures using Java Generics
    • Solution: Covariance Type in Scala
  • Problem: Unuseful generics for method parameter in Java
    • Solution: Contravariance Type in Scala

Problem: Java tells me that Kids aren't Humans

Since Java 5, as Java developers, we were really interested in the new breaking feature that was added: Generic Types.
And it was rather interesting enough thanks to the java.util.Collection API, but also the syntactic sugar for (A a: as).
However, we also felt really quickly on the problem that the hierarchy of Generics doesn't span to upper level type (as explain in the Java tutorial).

Let's clarify the situation with an example.
First we define a model with an classical hierarchy:

Okay, with this setup, one might want to create a list of kids and assign it to a list of human. Why? 
  1. because they are...
  2. because they grow!
Recall: in OO a model (should) represents the domain.

Fine! Here is several tries:

See? You just can't in Java! Because a ArrayList is not considered to be an instance of ArrayList. This will impact all your further algorithms, unless you use the tricky tip to anonymise your type and to constrain it with a the Human type as bound.

At least we spotted the real problem... Let's see the solution that Scala offers.

Solution: Covariance

In Scala, a type can be defined to be covariant to one (or several) of its generic type (roughly speaking).
We can simply check the Scala's List definition: 

sealed abstract classList[+A]

Here, we tells the compiler that List is covariant with its generic type A.

In other words? List will vary accordingly with the variance of A!

And life gets simple (respecting the OO concepts):

Following the type of generic type is pretty cool and useful, but there are cases where it won't help... let's jump to the next section if you don't believe me...

Problem: Java tells me that Kids aren't Human and Integer isn't a Number...

To illustrate this case, we'll create two helper type that define no-arg procedure and an action (a function) with one argument.
Simple as simple.

We also created to action definitions, one that maps a single integer onto a single human, and another one that maps a number onto an adult.

This will help us defining an higher order operation that, for instance, can map a list of integers into a new list of humans. For that, we'll create the ListMapper class (see below) that will map an input type I to an output type O.

Using this ListMapper, we'll try to convert:
  • a list of integer into a list of humans 
  • a list of numbers into a list of adults
We can easily imagine that the logic should remain in the actions introduced in above. Right?
Let's see how it goes in Java thus:
huh?
It seems that the mapper from Integer to Human is only able to deal with an action that takes exactly these types as input and output resp.
But, it's weird, because something that works on Number should be able to handle any Integer, isn't it?
And, if the returned object is an Adult, it should be ok to assign it to an Human? True?

For sure, but for the same reason as before, Java is not able to deal with such multi-levels hierarchies. crap...

Before going ahead, one might have noticed that the inheritance hierarchies are opposites:
  • Number is extended by Integer
  • Adult extends Human
But the mapper should be able to accept both pairs of input/output type! damn... the action type doesn't seems to vary the same way for input as for output!

Indeed, an action must be contravariant on its Input and covariant with its Output.

Here we are.

Solution: Contravariance

In the example above, we introduce action that acted as function taking a single argument. And those actions had to behave differently on the type of the input and the output.

Let's check this out in Scala, looking at what looks like such function:

traitFunction1[-T1+R]

Bloody hell, a function type in Scala will vary in the opposite way as for the covariant types. That's why a minus sign is used on the T1 type.

Simple said: a function F will be extended by any function that respect either or both of these cases:
  • its argument is a super-type of the F's argument.
  • its type (output type) is a sub-type of the F's type.
Let's see everything in action now:
That was for illustration purpose because the types weren't optimize for maximal genericity, however we can see that we were able to use a function that takes an AnyVal argument and results into an Adult object where a function from an Int to a Human were used!

Conclusion

A lot for nothing? Maybe?
But it's a question that is very common for Scala newcomers. And I think it's one of the most important ones, thus it must be answered in the more precise and accessible way.

Furthermore, it also demonstrates that Scala is even more Object Oriented that Java can be.

--
Please let me know, if it can be more clearer, this blog is meant to be organic, so any comments, concerns, helps are more than welcome