How does QuickCheck detect datatypes?

0
votes

If we define a function like this 

fun :: Int -> Property

and then run 

quickCheck fun

The quickCheck starts generating random data of type Int. The question is how does quickCheck detect that the argument datatype of fun is Int and not any other datatype? If I make the question more general I should ask that if we have a function called fun like this

fun :: datatype_1 -> datatype_2 -> ... -> datatype_n -> Property

How does quickCheck detect the type of each individual datatype_1, datatype_2, ... and datatype_n? And also how does it detect how many arguments the function fun takes?

2
haskellquickcheck
It does not have to detect that, it simply constraints it to an instance of Arbitrary. - Willem Van Onsem
As for the number of data types. In Haskell, every function takes exactly one parameter. It thus uses some sort of recursion to recurse on the function that is returned out of that function, etc. - Willem Van Onsem

2 Answers

3
votes

Roughly, this is how type classes work. One can declare

class C a where
   foo :: a -> Bool

and then

instance C (Int -> Bool) where
   foo f = f 42
instance C (String -> Bool) where
   foo f = f "hello"
instance C (String -> [Int]) where
   foo f = sum (f "hello") > 42

and so on.

This has the apparent effect to make foo "detect" the type of its argument f and act accordingly. Actually, what happens is that Haskell performs type inference, during which the appropriate instance is selected -- at compile time. At runtime, no "type detection" happens; indeed, types are erased after compilation, and there is no type information available at runtime, so it would be impossible to detect which type f belongs to.

The actual QuickCheck mechanism is much more complex, of course. To handle functions with an arbitrary number of arguments, a set of "recursive" instances is used, handling each argument every "recursive call", so to speak. This is a rather tricky technique, also used in printf and other "variadic" functions. If you are unfamiliar with type classes, I do not recommend to start learning them from such a complex trick.

0
votes

A bit late to the party, but this is the instance you're looking for in the current implementation.

instance (Arbitrary a, Show a, Testable prop) => Testable (a -> prop) where
  property f =
    propertyForAllShrinkShow arbitrary shrink (return . show) f
  propertyForAllShrinkShow gen shr shw f =
    -- gen :: Gen b, shr :: b -> [b], f :: b -> a -> prop
    -- Idea: Generate and shrink (b, a) as a pair
    propertyForAllShrinkShow
      (liftM2 (,) gen arbitrary)
      (liftShrink2 shr shrink)
      (\(x, y) -> shw x ++ [show y])
      (uncurry f)

As @chi correctly stated, there is recursion happening here. The recursive call is propertyForAllShrinkShow calling propertyForAllShrinkShow, and by calling uncurry, a property in the form a -> b -> c -> Bool gets turned into (a, b) -> c -> Bool. As (a, b) is a valid arbitrary because there is an instance of Arbitrary (a, b), the same instance of Testable will run again where prop is c -> Bool. Then, the same will run again as ((a, b), c, and prop will then be just Bool. At that point, the Bool instance of Testable kicks in, which uses the default propertyForAllShrinkShow, which creates the actual application of f x. So another way to say it is that quickcheck generates all of the values at the same time as an arbitrary tuple and uses recursion in the instance of Testable to construct the tuple.