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