[Haskell-cafe] QuickCheck behaving strange
Tobias Olausson
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
tob...@gmail.com
_______________________________________________
Haskell-Cafe mailing list
Haskel...@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Felipe Lessa
> 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)
> 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.
Probably it was defaulting to 'Interval () ()'. Try to do
:s -Wall
on your GHCi prompt to see when these things happen.
--
Felipe.
Jason Dagit
On Fri, Jul 24, 2009 at 08:11:12PM +0200, Tobias Olausson wrote:[..]
> 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)
> How come QuickCheck passes 100 tests of random lists? One would think thatProbably it was defaulting to 'Interval () ()'. Try to do
> at least one of the generated lists would be unsorted. It also passes
> 1000 and even
> 10000 tests.
Cases like this make me feel as though the instance of Ord for () was a mistake.
Jason
Tobias Olausson
/Tobias
2009/7/24 Felipe Lessa <felipe...@gmail.com>:
--
Tobias Olausson
tob...@gmail.com
Miguel Mitrofanov
natural.