How to define an arbitrary for a custom list in scalacheck?

Question

I defined a custom list and want to test it with scalacheck:

sealed trait MyList[+A] {
  def flatMap[B](f: A => MyList[B]): MyList[B]
  def map[B](f: A => B): MyList[B]
}

case object MyNil extends MyList[Nothing] {
  override def flatMap[B](f: (Nothing) => MyList[B]): MyList[B] = ???
  override def map[B](f: (Nothing) => B): MyList[B] = ???
}

case class MyCons[A](head: A, tail: MyList[A]) extends MyList[A] {
  override def flatMap[B](f: (A) => MyList[B]): MyList[B] = ???
  override def map[B](f: (A) => B): MyList[B] = ???
}

My test is:

import org.scalacheck.{Gen, Arbitrary}
import org.scalatest.{ShouldMatchers, FunSuite}
import org.scalatest.prop.Checkers
import org.scalacheck.Prop.forAll

class MyListSpec extends FunSuite with ShouldMatchers with Checkers {

  private def myConsGen[T]: Gen[MyList[T]] = for {
    head <- Arbitrary.arbitrary[T]
    tail <- Gen.oneOf(myNilGen, myConsGen[T])
  } yield MyCons(head, tail)

  private val myNilGen: Gen[MyList[Nothing]] = Gen.wrap(MyNil)

  implicit def myListArbitrary[T]: Arbitrary[MyList[T]] = Arbitrary[MyList[T]](Gen.oneOf(myNilGen, myConsGen[T]))

  test("map") {
    check(forAll { l: MyList[String] =>
      l.map(s => s) == l
    })
  }

}

But when I compile it, it will report error:

Error:(12, 32) could not find implicit value for parameter a: org.scalacheck.Arbitrary[T]
    head <- Arbitrary.arbitrary[T]
                               ^
Error:(12, 32) not enough arguments for method arbitrary: (implicit a: org.scalacheck.Arbitrary[T])org.scalacheck.Gen[T].
Unspecified value parameter a.
    head <- Arbitrary.arbitrary[T]
                               ^

How to fix it? And is my approach able to be improved?

Answer 1

You need to provide proof that T has an Arbitrary instance.

def myConsGen[T:Arbitrary]: Gen[MyList[T]]

and

implicit def myListArbitrary[T:Arbitrary]