Why does quickcheck pass for these two different functions Haskell?

Question

I have two functions. They are:

f1 [] = []
f1 (x:xs) = if contains x xs then f1 xs else x:f1 xs

and

f6 xs = f1 (rev xs)

It would not make sense that these two functions return the same list for anything other than the empty list and any list with one element, but when running quickcheck on this function:

prop_sort6 xs = (f1 xs == f6 xs) == True

all of the tests pass. Why is this the case?

Edit:

For example doing this: (f1 [1,2,3] == f6 [1, 2, 3]) obviously leads to False, but quickcheck still passes.

Oxidize

Please never write p == True. This is always superfluous, equivalent to p all by itself. Specifically with QuickCheck, it also removes valuable information, namely what went wrong in case the equality is not fulfilled. You should write f1 xs === f2 xs instead. – Deoxyribonuclease

Answer 1

We can do some investigating by using verboseCheck rather than quickCheck.

*Main Test.QuickCheck> verboseCheck prop_sort6
Passed:
[]

Passed:
[]

Passed:
[(),()]

Passed:
[(),()]

Passed:
[(),(),(),()]

... (you get the picture) ...

quickCheck (and verboseCheck, by the same token) has the signature

quickCheck :: Testable prop => prop -> IO ()

Now, we can follow the rabbit hole down and look up what Testable is, but the bottom line is that, whatever prop is, it's going to have to be monomorphic at runtime. That is, it can't have any pesky lingering type variables. Now, the type of prop_sort6 is inferred to be

prop_sort6 :: Eq a => [a] -> Bool

So we need a good concrete a which satisfies Eq. For most typeclasses, this would be an ambiguous type error. If we wrote the following,

class Foo a

myProp :: Foo a => a -> Bool
myProp _ = True

Then quickCheck myProp produces

<interactive>:29:1: error:
    • Ambiguous type variable ‘a0’ arising from a use of ‘quickCheck’
      prevents the constraint ‘(Arbitrary a0)’ from being solved.
      Probable fix: use a type annotation to specify what ‘a0’ should be.
      These potential instances exist:
        instance (Arbitrary a, Arbitrary b) => Arbitrary (Either a b)
          -- Defined in ‘Test.QuickCheck.Arbitrary’
        instance Arbitrary Ordering
          -- Defined in ‘Test.QuickCheck.Arbitrary’
        instance Arbitrary Integer
          -- Defined in ‘Test.QuickCheck.Arbitrary’
        ...plus 19 others
        ...plus 61 instances involving out-of-scope types
        (use -fprint-potential-instances to see them all)
    • In the expression: quickCheck myProp
      In an equation for ‘it’: it = quickCheck myProp

<interactive>:29:12: error:
    • No instance for (Foo a0) arising from a use of ‘myProp’
    • In the first argument of ‘quickCheck’, namely ‘myProp’
      In the expression: quickCheck myProp
      In an equation for ‘it’: it = quickCheck myProp

However, Eq is special. In GHCi (and only in GHCi), Eq has type defaulting rules so that, in the absence of any additional information, Eq a will be assumed to be Eq () (the unit type). This is only true in GHCi. If we make a main function which calls quickCheck, it's an ambiguous type error. However, in GHCi, it defaults to ().

Now, of course, () only has one instance, so we only end up testing the function with lists of () over and over again, and since your two functions will always produce lists of the same length, the test passes. You probably want to run it on Int instead.

*Main Test.QuickCheck> quickCheck (prop_sort6 :: [Int] -> Bool)
*** Failed! Falsified (after 5 tests and 1 shrink):
[0,1]

Note that the compiler flag -Wtype-defaults (enabled by -Wall) will warn you about type defaulting and will let you know that something is amiss. With -Wtype-defaults active:

*Main Test.QuickCheck> quickCheck prop_sort6

<interactive>:11:1: warning: [-Wtype-defaults]
    • Defaulting the following constraints to type ‘()’
        (Arbitrary a0)
          arising from a use of ‘quickCheck’ at <interactive>:11:1-21
        (Show a0)
          arising from a use of ‘quickCheck’ at <interactive>:11:1-21
        (Eq a0)
          arising from a use of ‘prop_sort6’ at <interactive>:11:12-21
    • In the first argument of ‘GHC.GHCi.ghciStepIO ::
                                  forall a. IO a -> IO a’, namely
        ‘(quickCheck prop_sort6)’
      In a stmt of an interactive GHCi command:
        it <- GHC.GHCi.ghciStepIO :: forall a. IO a -> IO a
              (quickCheck prop_sort6)
+++ OK, passed 100 tests.

Shelly

Answer 2

Specify that your function should be tested on e.g. lists of ints:

prop_sort6 :: [Int] -> Bool
prop_sort6 xs = (f1 xs == f6 xs) == True

If you don't specify a type, QuickCheck will fill in [a] as [()] and [(), (), (), (), (), ...] will not find any bugs in your case.

Machute