di ordine superiore ScalaCheck

Question

Si consideri la seguente definizione di una categoria:

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

Ecco un esempio per le funzioni unari:

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

Ora, categorie sono soggetti ad alcune leggi. composizione relativa (.) e l'identità (id):

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

Voglio testare questo con ScalaCheck. Proviamo per le funzioni sopra interi:

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

Ma questi sono quantificate sopra (i) un tipo specifico (Int), e (ii) una specifica funzione (intG). Quindi, ecco la mia domanda: fino a che punto posso andare in termini di generalizzazione dei test precedenti e come? O, in altre parole, sarebbe possibile creare un generatore di funzioni arbitrarie A => B e fornire quelle a ScalaCheck?

Answer 1

Non sapendo esattamente con Epsilon di Hilbert, vorrei adottare un approccio più fondamentale e utilizzare Arbitrary di ScalaCheck e Gen per selezionare le funzioni da utilizzare.

Prima di tutto, definire una classe base per le funzioni che si intende generare. In generale, è possibile generare funzioni con risultati non definiti (come dividere per zero), quindi utilizzeremo lo PartialFunction come nostra classe base.

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

Ora è possibile fornire alcune implementazioni. Sostituire toString in modo che i messaggi di errore di ScalaCheck siano comprensibili.

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. 

Ho scelto di generare funzioni unarie da funzioni binarie utilizzando le classi caso, passando argomenti aggiuntivi al costruttore. Non è l'unico modo per farlo, ma lo trovo il più semplice.

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. 

Ora è necessario creare un generatore di Fn[Int, Int], e definire che, come l'implicito Arbitrary[Fn[Int, Int]]. Puoi continuare ad aggiungere generatori finché non sei blu in faccia (polinomi, componendo funzioni complicate da quelli semplici, ecc.).

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) 

Ora è possibile definire le proprietà. Utilizzare intG.isDefinedAt(a) per evitare risultati non definiti.

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

Mentre quello che ho mostrato generalizza solo la funzione di test, speriamo che questo vi darà un'idea su come utilizzare avanzate inganno tipo di sistema di generalizzare il tipo.