Type constraint for higher-kinded type in Scala

Question

I am trying to write a generic law for Functors in scala, in a format that I could reuse for many functors in scalacheck tests. The law should be parameterized by the constructor F[_] and by the type of elements, say A.

Ideally I would write something like that:

def functorLaw[A, F[_] :Arbitrary] (fn :Functor[F]) :Prop = forAll { (fa :F[A]) => true }

(I use true instead of law body, as the exact computation does not matter for my question)

However the best I could hack is to wrap it in an abstract class, providing an abstract implicit for generating arbitrary F[A] values:

abstract class  FunctorSpec[A :Arbitrary, F[_]] extends Properties("foo") {

  implicit def arbitraryFA :Arbitrary[F[A]]
  def functorLaw (fn :Functor[F]) :Prop = forAll { (fa :F[A]) => true } 

}

Now this works, but it is not ideal. I need to instantiate the class for each test, that I would like to run, and need to provide the arbitraryFA function there. Of course, the compiler needs this function, but for lots of types they exist implicits that should do it (for instance for List[Int]). However the compiler will not be able to guess that these implicit provide arbitraryFA, so I need to implement this myself, which is very repetitive. For example:

object IntListFunctorSpec extends FunctorSpec[Int, List] {
  def arbitraryFA :Arbitrary[List[Int]] = Arbitrary(arbitrary[List[Int]])

  ...
}

I should not need to tell scalacheck how to build lists of int, I think. Any suggestions how to do this more elegantly?

I tried other questions on higher-kinded type bounds, and I cannot figure out exactly how to use them, even though, they sound close. So I thought I would ask.

Answer 1

The reason why your attempt did not work is because you have a kind mismatch. The following:

def functorLaw[A, F[_] :Arbitrary] (fn :Functor[F]) :Prop = forAll { (fa :F[A]) => true }

is just a syntactic sugar for:

def functorLaw[A, F[_]] (fn :Functor[F])(implicit evidence: Arbitrary[F]) :Prop = forAll { (fa :F[A]) => true }

So in essence, the problem is that your method expects an implicit value of type Arbitrary[F] where F is an higher-order type (F[_]), but that does not make sense because Arbitrary does not take an higher order type:

// T is a first order type, it has the kind *
// Simply put, it is not a type constructor
class Arbitrary[T]

For your code to compile as is (and make sense), Arbitrary would have to be declared something like this:

// T is a type constructor, it has the kind * -> *
class Arbitrary[T[_]]

Now for how to fix it. In your case, the actual arbitrary values that you want are of type F[A], not F (which should go without saying as it's not a concrete type, but a type constructor), so the implicit you need is of type Arbitrary[F[A]]:

def functorLaw[A, F[_]] (fn :Functor[F])(implicit arb: Arbitrary[F[A]]) :Prop = forAll { (fa :F[A]) => true }

And because F[A] does not occur in the type parameter list (there is A and F, but not F[A]), the "context bound" syntactic sugar can not be used and we have to leave it at using an explicit (!) implicit parameter list.