de orden superior ScalaCheck

Question

Considere la siguiente definición de una categoría:

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

He aquí un ejemplo para las funciones unarios:

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

Ahora, las categorías están sujetos a algunas leyes. composición relativa (.) y la identidad (id):

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

que quieren probar esto con ScalaCheck. Vamos a tratar de funciones sobre los números enteros:

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

Pero éstas se han cuantificado más de (i) un tipo específico (Int), y (ii) una función específica (intG). Así que aquí está mi pregunta: ¿hasta dónde puedo llegar en términos de generalizar las pruebas anteriores, y cómo? O, en otras palabras, ¿sería posible crear un generador de funciones arbitrarias A => B y proporcionarlas a ScalaCheck?

Answer 1

Sin saber exactamente con Hilbert's epsilon, tomaría un enfoque más fundamental y usaría ScalaCheck's Arbitrary y Gen para seleccionar funciones para usar.

Primero, defina una clase base para las funciones que va a generar. En general, es posible generar funciones que tengan resultados no definidos (como dividir por cero), así que usaremos PartialFunction como nuestra clase base.

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

Ahora puede proporcionar algunas implementaciones. Anule toString para que los mensajes de error de ScalaCheck sean inteligibles.

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. 

He elegido generar funciones únicas a partir de funciones binarias utilizando clases de casos, pasando argumentos adicionales al constructor. No es la única forma de hacerlo, pero me parece el más directo.

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. 

Ahora es necesario crear un generador de Fn[Int, Int], y definir que a medida que la implícita Arbitrary[Fn[Int, Int]]. Puedes seguir agregando generadores hasta que seas azul en la cara (polinomios, componer funciones complicadas a partir de las simples, etc.).

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) 

Ahora puede definir sus propiedades. Use intG.isDefinedAt(a) para evitar resultados indefinidos.

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

Si bien lo que he mostrado sólo generaliza la función de prueba, espero que esto le dará una idea sobre cómo utilizar el engaño avanzado sistema de tipo de generalizar sobre el tipo.