[Haskell-cafe] QuickCheck behaving strange

Tobias Olausson tobsan at gmail.com
Fri Jul 24 14:11:12 EDT 2009


Hey Guys!
I was writing a small implementation of the earliest-end-first algorithm
for the Interval Scheduling problem just now. When I was done, I thought
it would be a nice thing to have a QuickCheck property for my code. This
is what I came up with:

-- Intervals are just triplets
type Interval a t = (a,t,t)

end :: Interval a t -> t
end (_,_,t) = t

begin :: Interval a t -> t
begin (_,t,_) = t

And so the property:

prop_schedule :: Ord t => [Interval a t] -> Bool
prop_schedule []        = True
prop_schedule [a]       = True
prop_schedule (x:y:ys)  = end x <= begin y && prop_schedule (y:ys)

Essentially, it looks up wheather the given list is "sorted" (given
the constraints
of the problem). However, in this property I forgot to add that the
lists should have
been run through my algorithm, which I noticed only after this strange problem
appeared:

*Interval> quickCheck prop_schedule
+++ OK, passed 100 tests.

How come QuickCheck passes 100 tests of random lists? One would think that
at least one of the generated lists would be unsorted. It also passes
1000 and even
10000 tests.

It also seems that changing the type helps:
prop_schedule :: [Interval a Int] -> Bool
...
*Interval> quickCheck prop_schedule
*** Failed! Falsifiable (after 5 tests and 1 shrink):
[((),0,0),((),-1,0)]

-- 
Tobias Olausson
tobsan at gmail.com


More information about the Haskell-Cafe mailing list