QuickCheck behaving strange

24 Jul 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@gmail.com

Tobias Olausson

Felipe Lessa

Jason Dagit

Miguel Mitrofanov

Tobias Olausson

tags

participants (4)