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?


scala specifications category-theory scalacheck
person Hugo Sereno Ferreira    schedule 09.05.2012    source источник
comment
Я не знаю точного ответа на ваш вопрос, но он мне напоминает проверки монадных законов в scalaz. Возможно, вас может вдохновить github. com/scalaz/scalaz/blob/master/tests/src/test/scala/   -  person Kristian Domagala    schedule 10.05.2012
comment
возможно, stackoverflow.com/users/53013/daniel-c-sobral знает ответ?   -  person Ashkan Kh. Nazary    schedule 12.05.2012
comment
Если тип выбран произвольно, вы можете рассматривать это как универсальную количественную оценку с помощью эпсилона Гильберта. См. gist.github.com/2659013.   -  person Miles Sabin    schedule 14.05.2012

Ответы (1)


arrow_upward
6
arrow_downward

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

Во-первых, определите базовый класс для функций, которые вы собираетесь создать. В общем, можно генерировать функции с неопределенными результатами (например, деление на ноль), поэтому мы будем использовать 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), чтобы избежать неопределенных результатов.

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))
}

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

person leedm777    schedule 21.05.2012