Is it possible to generate arbitrary functions in QuickCheck

Question

I was trying to write a QuickCheck test for the identity

f $ y = f y

My initial plan was to write an arbitrary generator that returns functions & Integer, having the signature Gen (Int -> Int, Int)

and in the prop_DollerDoesNothing test that function application with / without the $ gives the same result.

This was my code:

  prop_DollarDoesNothing :: Property
  prop_DollarDoesNothing =
    forAll arbitraryFuncInt (\(f, y) -> (f $ y) == (f y))

  arbitraryFuncInt :: Gen (Int -> Int, Int)
  arbitraryFuncInt = do
    f <- elements [(\x -> x*2), (\x -> x+3), (\x -> x-2)]
    y <- arbitrary :: Gen Int
    return (f, y)

And it generated the following helpful error message:

    * No instance for (Show (Int -> Int))
        arising from a use of `forAll'
        (maybe you haven't applied a function to enough arguments?)
    * In the expression:
        forAll arbitraryFuncInt (\ (f, y) -> (f $ y) == (f y))
      In an equation for `prop_DollarDoesNothing':
          prop_DollarDoesNothing
            = forAll arbitraryFuncInt (\ (f, y) -> (f $ y) == (f y))

So, I fixed the error and got the test working by applying the arbitrary function and returning a pair of ints from arbitraryFuncInt

  prop_DollarDoesNothing :: Property
  prop_DollarDoesNothing =
    forAll arbitraryFuncInt (\(x, y) -> x == y)

  arbitraryFuncInt :: Gen (Int, Int)
  arbitraryFuncInt = do
    f <- elements [(\x -> x*2), (\x -> x+3), (\x -> x-2)]
    y <- arbitrary :: Gen Int
    return (f $ y, f y)

My questions are:

is it simply not possible to return arbitrary functions that aren't fully applied due to not having an instance for Show?
Can I write an instance for Show (Int -> Int) to make # 1 possible?
Can QuickCheck generate arbitrary functions given a type signature, for cases where I'm testing identities that are true for all functions (of a given type). Above, I specify the 3 test functions by hand, I'd like to automate that somehow, ideally something like this f <- arbitrary :: Gen (Int -> Int)

Li-yao Xia Li-yao Xia · Accepted Answer · 2018-05-31T21:59:37

QuickCheck has support to generate, shrink and show functions, using the Fun type. CoArbitrary enables generation of functions. It is then converted to a (possibly infinite) trie-like structure, that can be inspected and shrunk to a finite value (because a test failure only depends on finitely many inputs), which can then be shown as a counterexample.

Concretely, you can write properties as function that take a Fun argument, which is a wrapper around (->) using the mechanism I described. Deconstruct it with the Fn pattern to get a function.

prop_dollarDoesNothing :: Property
prop_dollarDoesNothing = property $ \(Fn (f :: Int -> Int)) x ->
  (f $ x) === f x

For more information

The QuickCheck implementation: https://hackage.haskell.org/package/QuickCheck-2.11.3/docs/Test-QuickCheck-Function.html
The paper "Shrinking and showing functions" by Koen Claessen, which appears to be paywalled, but his talk is online: https://www.youtube.com/watch?v=CH8UQJiv9Q4

Is it possible to generate arbitrary functions in QuickCheck

2 Answers