Type variance explained with cats

Reasoning about subtype relations between parameterised types tend to confuse developers. If you are a Java developer you’ve probably seen the syntax ? extends T and ? super T, or might even used it to create flexible method signatures. I was very confused at first when I tried to use them as their meaning wasn’t clear to me. So, I just placed extends everywhere, and changed it to super when the compiler complained. Where is it even valid to place only super types of some T? It made no sense to me at first. But as it turns out, it makes all the sense. Let’s start at the beginning.

Say you have a Cat class extending the Animal class. Here, Cat is the subtype of Animal, by definition.

animal_cat

Now, let’s create four XInYOut classes, each of them having a single method apply, and use these two classes with them. It doesn’t matter what this apply method does, we only care about its signature: it takes one input parameter, and returns an output. Why do we create four? To cover all combinations of the Animal and Cat classes, in the input and output parameters.

Without generic parameters yet, what are possible subtyping relations between these classes?

The most straightforward is that AnimalInCatOut is a subtype of AnimalInAnimalOut, because wherever you return an Animal you could also return a Cat as it is its subtype. The same thing applies to CatInCatOut  and CatInAnimalOut.

aico

subtype_2

 

Might be a bit trickier to see that AnimalInAnimalOut is a subtype of CatInAnimalOut. The first one can replace the second one on call-site without breaking type safety, because the caller expects something the needs a Cat , and so they must provide an argument that is subtype of Cat, and this always satisfy Animal. Of course the same applies to AnimalInCatOut and CatInCatOut.

suebtype_1

subtype_0

AnimalInCatOut and CatInAnimalOut combine both treats of the upper two cases; both the former’s input a supertype, the output the subtype of the latter. So AnimalInCatOut is a subtype of CatInAnimalOut.

Lastly, CatInCatOut cannot be a subtype of AnimalInAnimalOut as it breaks the contract of its input parameter, vice versa it breaks the output, so there is no relation between them. To sum things up:

whole

Now, onto generics. Let’s make one generic class by depending on two types: In and Out.

generic

 

The same rules applies here as well:

  • Function<Animal, Cat> is a subtype of Function<Animal, Animal> and Function<Cat, Cat> is a subtype of Function<Cat, Animal>. Here the subtype relation’s direction of the dependent type Function is the same as the parameter Out, making Out a covariant type parameter.
  • Function<Animal, Animal> is a subtype of Function<Cat, Animal>, Function<Animal, Cat> is a subtype of Function<Cat, Cat>. Here the subtype relation’s direction of the dependent type Function is opposite to the direction of the subtype relation between the parameter In making In a contravariant type parameter.
  • Making use of both parameters’ variance, Function<Animal, Cat> is a subtype of Function<Cat, Animal>.

In some languages, like Scala, variance is declared class level, using + for covariant, - for contravariant parameters.

anno2

In Java however, the developer has a cumbersome job: the language does not known class level variance. Instead one has to specify the type variables’ variance every place they are used: ? extends T for covariant, ? super T for contravariant positions. If you miss to specify the variance at a place, you lose the information for consequent uses.

Hope this clarified things a bit about type variance. Cheers!

 

Java, The Bad Parts: Recursive lambdas

Have you ever tried to create a recursive lambda in Java?

You might ask why on earth would somebody do that. For you I have a confession to begin with: I’ve been spoiled. I’ve been spoiled with the overwhelming expressiveness of functional programming.

I’ve been using Scala and JavaScript for more almost 2 years now, and that leaves a trace. I think about problems differently than an average Java developer does. Both Scala and JavaScript gives you the ability to express your problems more or less functionally. Neither of them are purely functional languages, but occupy a sweet spot to be fairly convenient to use.

But why do then I mess around in Java? Not for fun, sure. I had a homework assignment for a university course which involved writing a breadth first traversal component for a graph. During traversal, you may inspect your current paths, and run some solver on it that classifies it as good or bad, and if it’s bad you have to bail out with the level on which the bad path appeared and the path itself.

It’s pretty straightforward right? I have a stream of trees, which starts with an initial tree consisting only the root node, then I recursively flatMap the tree’s outward edges to get a tree of longer paths, at every step I check if the new paths are bad…

… so I need lists, streams …

… let’s take a look at the standard Java collections.

 

OH GOD NO MEME

No. Just simply no.

So I started implementing my old own naive functional list. Guava provides a friendlier interface for Java collections, but I didn’t want to involve additional dependencies, and also it would have solved my need for functional lazy streams. (This is only a guess, I haven’t looked at Guava since 3 years.)

Finally I’m at the point: creating my tree stream involved recursive lambdas.

Let’s take a look at a dummy example with natural numbers.

In Scala it’s as simple as a cake:

def naturals: Stream[Int] = 0 #:: naturals.map(_ + 1)
 
 naturals.take(5).foreach(println)
 // 0
 // 1
 // 2
 // 3
 // 4

In Java I tried this:

Function<Void, Stream<Integer>> n = (Void) -> Stream.cons(
     (Void _1) -> 0,
     (Void _1) -> n.andThen(x -> x.map(y -> y + 1)).apply(null));
 
 Stream<Integer> naturals = n.apply(null);
 
 naturals.take(5).foreach(x -> System.out.println(x));

This looks awful already, but even worse, it doesn’t compile.

Let’s see why it looks awful:

  • because it’s Java?
  • Java doesn’t let you have a variable in the same name in an inner scope as in an outer one, while in Scala and JavaScript this works and called shadowing. That is why I had to find another name than x in my map function.
  • I couldn’t find a function type with no input arguments, I had to use Function<Void, T> instead. The Void class is a dummy class, that cannot be instantiated (null is the only valid value), so it acts like a void more or less.  That’s why you will never need the value for a Void. So you can omit it right? Hold on. The same no redeclaration rule that we faced above holds for unnamed parameters. You cannot omit the name when an omitted name shadows another one omitted name. What the actual f*ck??? How can a non-existent name even shadow another? Someone really screwed something up with this language.

CLIENT EASTWOOD DISGUSTED MEME

 

And then, it doesn’t compile. It doesn’t, because n may have been uninitialized at the time of use in the lambda. The compiler is thinking it’s smarter than me. I understand it’s a dangerous situation because if that lambda runs before defining the outer function, I get a NullPointerException. But I’m clever enough not to do this. Why doesn’t it allow me? So I don’t have to use this hack, which circumvents this foul attempt to stop me:

@SuppressWarnings("rawtypes")
 final Function[] _n = { null };
 @SuppressWarnings("unchecked")
 Function<Void, Stream<Integer>> __n = _n[0];
 __n = (Void) -> Stream.cons(
     (Void _0) -> 0,
     (Void _0) -> {
       @SuppressWarnings("unchecked")
       Stream<Integer> f = ((Function<Void, Stream<Integer>>)_n[0])
          .andThen(x -> x.map(y -> y + 1)).apply(null);
       return f;
     }
   );
 _n[0] = __n;
 
 Stream<Integer> naturals = __n.apply(null);
 
 naturals.take(5).foreach(x -> System.out.println(x));
 // 0
 // 1
 // 2
 // 3
 // 4

Beautiful. Luckily you can hide this ugliness if you abstract it:

static <U> Stream<U> recursively(Function<Void, U> base, Function<U, U> next) {
   @SuppressWarnings("rawtypes")
   final Function[] _n = { null };
   @SuppressWarnings("unchecked")
     Function<Void, Stream<U>> __n = _n[0];
     __n = (Void) -> Stream.cons(
       base, 
       (Void _0) -> {
         @SuppressWarnings("unchecked")
         Stream<U> f = ((Function<Void, Stream<U>>)_n[0]).andThen(x -> x.map(y -> next.apply(y))).apply(null);
           return f;
         }
       );
     _n[0] = __n;
     return __n.apply(null);

The lesson was learned and it is: Java makes you life harder than it should be when you write functional code.

Hard enough to don’t even bother.

Source for the List and Stream classes is here