F-bound over a generic type in Scala

In this article, I will be mentioning Comonads. If you know what they are, great, and if you don’t know, no worries, because this article’s main topic isn’t Comonads. It’s actually about Scala generics, about F-bound, about returning the “Current” Type in Scala.

In my odyssey to understand Comonads, the first thing I did after reading about them was to implement a series of tests that would make them a little bit clearer, and I did it using the NonEmptyList implementation of the scalaz library.

But obviously testing a specific implementation wouldn’t get me to the end of it, so I decided to implement an IdentityComonad by myself, a Comonad without added functionality.

F-bound over a Scala generics type

I ended up with something like this:

case class IdentityComonad[A](a: A) {
   def map[B](f: A => B): IdentityComonad[B] = IdentityComonad(f(a))
   def counit: A = a
   def duplicate: IdentityComonad[IdentityComonad[A]] = IdentityComonad(this)
   def cojoin = duplicate
   def cobind[B](f: IdentityComonad[A] => B): IdentityComonad[B] =  IdentityComonad(f(this))
 }

The tests I had done for the NonEmptyList also passed, and in my opinion, it didn’t seem that bad, so I thought about abstracting an interface to be able to do more Comonads, you know… just for fun.

And the first version of the interface, designing all the methods that I had already defined, was this:

trait IComonad[A] {
 def map[B](f: A => B): IComonad[B]
 def counit: A
 def cojoin: IComonad[IComonad[A]]
 def duplicate = cojoin
 def cobind[B](f: IComonad[A] => B): IComonad[B]
}

So the IdentityComonad evolved to this:

case class IdentityComonad[A](a: A) extends IComonad[A] {
 override def map[B](f: A => B): IdentityComonad[B] = IdentityComonad(f(a))
 override def counit: A = a
 override def cojoin: IdentityComonad[IdentityComonad[A]] = IdentityComonad(this)
 override def cobind[B](f: IdentityComonad[A] => B): IdentityComonad[B] =  IdentityComonad(f(this))
}

And right here, we found the first problem: Until this point,  we only found IdentityComonad (IComonad in the trait) in the return types, but…

override def cobind[B](f: IdentityComonad[A] => B): IdentityComonad[B] =  IdentityComonad(f(this))

Oh, in the cobind method, the type is also present in the input parameter (f), and I am anticipating from now that this will not compile, because IdentityComonad[A] isn’t IComonad[A]

This is when we tell ourselves, compilation or death, and we change the cobind to use IComonad:

case class IdentityComonad[A](a: A) extends IComonad[A] {
 override def map[B](f: A => B): IdentityComonad[B] = IdentityComonad(f(a))
 override def counit: A = a
 override def cojoin: IdentityComonad[IdentityComonad[A]] = IdentityComonad(this)
 override def cobind[B](f: IComonad[A] => B): IdentityComonad[B] =  IdentityComonad(f(this))
}

Hey! Everything compiles, and it even works… cool, right?
The problem is if we leave this method signature for cobind in the interface:

override def cobind[B](f: IComonad[A] => B): IComonad[B] =  ???

We could accept any other Comonad that extends from IComonad as a parameter in f.

We need to change IComonad to ensure that the type used in f will be exactly the subclass that we are implementing and not a generic IComonad.

But it doesn’t all end here… The return type of the map method is also IComonad… Ouch.

This means that in our implementation of map in IdentityComonad, we could return any other implementation of IComonad, not necessarily IdentityComonad, which would make our Comonad stop making sense.

Getting at this phase, you remember having read about something called F-Bounded types, so we look for information and try to use it:

trait IComonad[A, F[A]] {
 def map[B](f: A => B): F[B]
 def counit: A
 def cojoin: F[F[A]]
 def duplicate = cojoin
 def cobind[B](f: F[A] => B): F[B]
}

If you are not very used to generics… right now you might be getting a strong migraine.
This way, IComonad uses A, just like before, but now it also uses  F[A], determining the type used in the implementation.

It may seem very confusing & messy, but to sum up, the implementation tells to its interface who it is, so that the interface can force the types.

The implementation could look like that:

case class IdentityComonad[A](a: A) extends IComonad[A, IdentityComonad] {
 override def map[B](f: A => B): IdentityComonad[B] = IdentityComonad(f(a))
 override def counit: A = a
 override def cojoin: IdentityComonad[IdentityComonad[A]] = IdentityComonad(this)
 override def cobind[B](f: IdentityComonad[A] => B): IdentityComonad[B] =  IdentityComonad(f(this))
}

Great, huh!? Now the return type must be exactly the type of the class that we are implementing (IdentityComonad), we no longer have the same problem we had before (being able to use sibling IdentityComonad types)

But… do you smell that? I smell it too… I am not being forced to tell IComonad that T is IdentityComonad.

I mean, IdentityComonad could extend IComonad [A, Something] (being Something another generic class that accepts [A]), and everything would work out (using Something as F)

It’s kind of hard to explain, so I’ll draw a picture to illustrate it:

Case class IdentityComonad[A](a: A) extends IComonad[A, Something] {
                 |                                         |
                 V                                         V
             this class             &                  this class

They may not be the same class, and it would still work! Look at this example with a “ListComonad” (not a valid implementation):

class ListComonad[A](list: List[A]) extends IComonad[A, List] {
   override def map[B](f: A => B): List[B] = list.map(f)
   override def counit: A = list.head
   override def cojoin: List[List[A]] = List(list)
   override def cobind[B](f: List[A] => B): List[B] =  List(f(list))
 }

See? Now I have a ListComonad, not bad huh? But this isn’t really a valid list Comonad, I am not returning a Comonad, so I can’t chain them either.

Also, the ListComonad parameter is not of type A, it is of type List[A], and this is a problem, because ListComonad should not depend of List (which is a monad).

But it doesn’t matter, let’s keep focus, the fact is that I just demonstrated that I can fool the interface to use types that I shouldn’t use (or do not want to use, it all depends on how you look at it).

And so we made it to the final implementation, the best I’ve arrived to until now (without using typeclasses).

Now we try to force F[A] in IComonad to be a subtype of IComonad (F[A] <: IComonad[A,F]), this makes more sense. Now List, wouldn’t be able to occupy the place of F.

However, it could be done by a FakeComonad or any other sibling type of IdentityComonad (which extends from IComonad), but at least we have limited the possibilities of “messing it up”:

object IComonad
{
  trait IComonad[A, F[A]  B): F[B]
    def counit: A
    def cojoin: F[F[A]]
    def duplicate = cojoin
    def cobind[B](f: F[A] => B): F[B]
  }
 case class IdentityComonad[A](a: A) extends IComonad[A, IdentityComonad] {
   override def map[B](f: A => B): IdentityComonad[B] = IdentityComonad(f(a))
   override def counit: A = a
   override def cojoin: IdentityComonad[IdentityComonad[A]] = IdentityComonad(this)
   override def cobind[B](f: IdentityComonad[A] => B): IdentityComonad[B] =  IdentityComonad(f(this))
 }

This would be the only case that could unfortunately happen to us.

case class FakeComonad[A](a:A) extends IComonad[A, IdentityComonad]{
   override def map[B](f: A => B): IdentityComonad[B] = IdentityComonad(f(a))
   override def counit: A = a
   override def cojoin: IdentityComonad[IdentityComonad[A]] = IdentityComonad(IdentityComonad(a))
   override def cobind[B](f: IdentityComonad[A] => B): IdentityComonad[B] =  IdentityComonad(f(IdentityComonad(a)))
 }
}

Obviously there will be people saying: but if this is just an F-bound! You could have done it from the beginning! Well, it is true, it’s an F-bound, however it has a special difficulty: it is an F-bound in the presence of 2 type parameters (A and F), meaning it’s an F-Bound on a type that already is generic, that forces us to use a higher kinded type (F[A]). That’s what is great about this experiment, getting to the point where just an F-Bound doesn’t work, and we have to use higher kinded types!

Once you get to the end and if you understood everything, it is not much more complicated than a normal one, but in the beginning it can be lousy.

Hey, and wouldn’t a typeclass solve your life? Of course, with a typeclass we get rid of these problems, since they have the type explicitly defined for each typeclass. But what’s nice is to check how far we can get, right? How far can we get using only this set of tools?

To those of you who want to see how to do this kind of thing with a typeclass, here’s a good reference. 

To conclude, throughout this flow of thought that we followed, we can see that the indiscriminate use of generics can give rise to curious holes.

This doesn’t mean that you should stop using them! It means that when creating very generic types, for libraries and others, special care must be taken, to monitor certain bugs that can be created.

If you found this article about Scala F-bound interesting, you might like… 

BDD: user interface testing

Scala generics I: Scala Type Bounds 

Microservices vs Monolithic architecture

“Almost-infinit” scalability