Проверка ScalaCheck высокого уровня

Рассмотрим следующее определение категории:

trait Category[~>[_, _]] {
  def id[A]: A ~> A
  def compose[A, B, C](f: A ~> B)(g: B ~> C): A ~> C
}

Здесь экземпляр для унарных функций:

object Category {
  implicit def fCat = new Category[Function1] {
    def id[A] = identity
    def compose[A, B, C](f: A => B)(g: B => C) = g.compose(f)
  }
}

Теперь категории подчиняются некоторым законам. Относительная композиция (.) и тождество (id):

forall f: categoryArrow -> id . f == f . id == f

Я хочу протестировать это с помощью ScalaCheck. Пусть попробуйте функции над целыми числами:

"Categories" should {
  import Category._

  val intG  = { (_ : Int) - 5 }

  "left identity" ! check {
    forAll { (a: Int) => fCat.compose(fCat.id[Int])(intG)(a) == intG(a) }      
  }

  "right identity" ! check {
    forAll { (a: Int) => fCat.compose(intG)(fCat.id)(a) == intG(a) }      
  }
}

Но они определяются количественно по (i) конкретному типу (Int) и (ii) определенной функции (intG). Итак, вот мой вопрос: как далеко я могу пойти в плане обобщения вышеуказанных тестов и как? Или, другими словами, можно ли создать генератор произвольных функций A => B и предоставить их ScalaCheck?

Ответы

Ответ 1

Не зная точно с Hilbert epsilon, я бы взял более фундаментальный подход и использовал ScalaCheck Arbitrary и Gen, чтобы выбрать функции для использования.

Сначала определите базовый класс для функций, которые вы собираетесь генерировать. В общем случае возможно генерировать функции, имеющие undefined результаты (например, деление на ноль), поэтому мы будем использовать PartialFunction как наш базовый класс.

trait Fn[A, B] extends PartialFunction[A, B] {
  def isDefinedAt(a: A) = true
}

Теперь вы можете предоставить некоторые реализации. Переопределить toString, поэтому сообщения об ошибках ScalaCheck понятны.

object Identity extends Fn[Int, Int] {
  def apply(a: Int) = a
  override def toString = "a"
}
object Square extends Fn[Int, Int] {
  def apply(a: Int) = a * a
  override def toString = "a * a"
}
// etc.

Я решил генерировать унарные функции из двоичных функций, используя классы case, передавая дополнительные аргументы конструктору. Не единственный способ сделать это, но я считаю это самым простым.

case class Summation(b: Int) extends Fn[Int, Int] {
  def apply(a: Int) = a + b
  override def toString = "a + %d".format(b)
}
case class Quotient(b: Int) extends Fn[Int, Int] {
  def apply(a: Int) = a / b
  override def isDefinedAt(a: Int) = b != 0
  override def toString = "a / %d".format(b)
}
// etc.

Теперь вам нужно создать генератор Fn[Int, Int] и определить его как неявный Arbitrary[Fn[Int, Int]]. Вы можете продолжать добавлять генераторы, пока не будете синими в лице (полиномы, составляющие сложные функции из простых и т.д.).

val funcs = for {
  b <- arbitrary[Int]
  factory <- Gen.oneOf[Int => Fn[Int, Int]](
    Summation(_), Difference(_), Product(_), Sum(_), Quotient(_),
    InvDifference(_), InvQuotient(_), (_: Int) => Square, (_: Int) => Identity)
} yield factory(b)

implicit def arbFunc: Arbitrary[Fn[Int, Int]] = Arbitrary(funcs)

Теперь вы можете определить свои свойства. Используйте intG.isDefinedAt(a), чтобы избежать результатов undefined.

property("left identity simple funcs") = forAll { (a: Int, intG: Fn[Int, Int]) =>
  intG.isDefinedAt(a) ==> (fCat.compose(fCat.id[Int])(intG)(a) == intG(a))
}

property("right identity simple funcs") =  forAll { (a: Int, intG: Fn[Int, Int]) =>
  intG.isDefinedAt(a) ==> (fCat.compose(intG)(fCat.id)(a) == intG(a))
}

В то время как то, что я показал, только обобщает тестируемую функцию, надеюсь, это даст вам представление о том, как использовать обход расширенного типа для обобщения по типу.