CODEWITHSUNDEEP
listfunctionhaskellrecursionquickcheck
Brad
Brad

Reputation: 133

Why is Haskell giving "ambiguous type variable" error?

A past paper problem asked me; to define a function p :: [a] -> [a] that swaps every two items in a list. Your function should swap the first with the second item, the third with the fourth, and so on. define one by list comprehension another by recursion.

Well this is what I came up with:

import Test.QuickCheck
p :: [a] -> [a]
p [] = []
p xs = concat [ [y,x] | ((x,y),i) <- zip (zip xs (tail xs)) [1..], odd i]
q :: [a] -> [a]
q [] = []
q (x:y:zs) | even (length zs) = [y,x] ++ q zs
           | otherwise = error "The list provided is not of even length"
prop_2 xs = even (length xs) ==> p xs == q xs
check2 = quickCheck prop_2

The functions work fine, but I wanted to check if the two are identical, so I put the quickCheck below; but this gives me an error for some reason saying "ambiguous type variable [a0] arising from the use of prop_2"

I just don't understand what's wrong here, I looks perfectly sensible to me... what exactly is Haskell complaining??

Upvotes: 3

Views: 1807

Answers (1)

kosmikus
kosmikus

Reputation: 19657

Let's start by commenting out check2 and asking GHCi what the type of prop_2 is:

*Main> :t prop_2
prop_2 :: Eq a => [a] -> Property

Ok, so the way you've written prop_2, it works for lists of any element type that is in the equality class.

Now, you want to pass prop_2 to the quickCheck function. Let's look at the type of quickCheck next:

*Main> :t quickCheck
quickCheck :: Testable prop => prop -> IO ()

This function actually has an immensely general type. It works on anything that's in the Testable class. So how does this Testable class work? There are a couple of base instances here, for example:

instance Testable Bool
instance Testable Property  -- this is a simplification, but it's more or less true

These instances are defined in the QuickCheck library and tell you that you can quick-check constant Booleans as well as elements of type Property.

Now, testing properties that do not depend on any inputs isn't particularly interesting. The interesting instance is this one:

instance (Arbitrary a, Show a, Testable prop) => Testable (a -> prop)

What this says is that if you know how to generate random values of a particular type (Arbitrary a) and how to show values of that type (Show a), then you can also test functions from that type a to an already testable type prop.

Why? Because that's how QuickCheck operates. In such a situation, QuickCheck will consult the Arbitrary instance in order to come up with random test cases of type a, apply the function to each of them, and check if the outcome is positive. If any of the tests fails, it will print a message informing you about the test failure, and it will print the test case (that's why there's a Show requirement, too).

Now, in our situation this means that we should be able to quick-check prop_2: it is a function that results in a Property. The important thing is that the function argument (of type [a] as long as Eq a holds) is a member of class Arbitrary and a member of class Show.

Here we arrive at the source of the error. The information available is not sufficient to make that conclusion. As I said in the beginning, prop_2 works for lists of any element type that admits equality. There's no built-in rule that says that all these type are in Arbitrary and Show. But even if there was, what kind of lists should QuickCheck generate? Should it generate lists of Booleans, lists of unit type, lists of functions, lists of characters, lists of integers? So many options, and the choice of element type may well affect whether you find a bug or not. (Consider that GHC would pick the unit type () with just one element. Then your property would hold for any two functions p and q that preserve the input lists' length, regardless of whether they have your desired swapping property or not.)

This is why you need to provide extra type information to GHC so that it can resolve which element type to use for the list. Doing so is simple enough. You can either annotate prop_2 itself:

prop_2 :: [Integer] -> Property

Or, if you don't want that (because you might want to run the tests on different kinds of lists without reimplementing prop_2), you can add a type annotation when calling quickCheck:

check2 = quickCheck (prop_2 :: [Integer] -> Property)

Now the code compiles, and we can run check2:

Main*> check2
+++ OK, passed 100 tests.

Upvotes: 9

Related Questions