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.

Have you tried def functorLaw[A, F[_]] (fn :Functor[F])(implicit arb: Arbitrary[F[A]]) :Prop = forAll { (fa :F[A]) => true } ? — Régis Jean-Gilles
This works very well! I shortened the code to 25% of what it was. Stackoverflow never disappoints you :). Could you post it as an answer so that I could accept it? There is still one more issues: this questions shows my dislike for implicits (and that I really do not understand them, and avoid in using them in my programs). We still did not manage to constraint F[_] in any way. Are implicits the only way? — Andrzej Wąsowski
@SK2751 There's a big differences between implicit type class instances and implicit conversions or implicit values as config, etc. For better or worse Scala's encoding of type classes is built on implicits, and trying to avoid them while working with types like Arbitrary is almost certainly going to be counterproductive. — Travis Brown
@TravisBrown, you are absolutely right, as my question proves :) — Andrzej Wąsowski

Régis Jean-Gilles Régis Jean-Gilles · Accepted Answer · 2015-09-16T07:38:42

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.

Type constraint for higher-kinded type in Scala

1 Answers