{-# LANGUAGE TemplateHaskell #-}

import Test.QuickCheck
import Data.List ( (\\), sort )
import Prelude hiding (Either(..))

qsort :: Ord a => [a] -> [a]
qsort []     = []
qsort (x:xs) = qsort (filter (<x) xs) ++ [x] ++ qsort (filter (>=x) xs)


prop_idempotence :: [Int] -> Bool
prop_idempotence xs = qsort (qsort xs) == qsort xs

-- All elements of the argument occur in the result list:
prop_preservation :: [Int] -> Bool
prop_preservation xs = null (xs \\ qsort xs) && null (qsort xs \\ xs)

-- first element of a sorted list is the smallest one:
prop_smallest_first :: [Int] -> Property
prop_smallest_first xs =
  not (null xs) ==> head (qsort xs) == minimum xs

-- Test against a reference implementation:
prop_reference :: [Int] -> Bool
prop_reference xs = qsort xs == sort xs

prop_reference_classify :: [Int] -> Property
prop_reference_classify xs = 
  classify (length xs < 5) "small" $
  classify (length xs > 20) "big" $
    qsort xs == sort xs

prop_reference_collect :: [Int] -> Property
prop_reference_collect xs =
  collect (length xs) $ qsort xs == sort xs

-- Small numbers:
data Digit = Digit Int
  deriving (Eq, Ord)

instance Show Digit where
  show (Digit d) = show d

instance Arbitrary Digit where
  arbitrary = do --d <- elements [0 .. 9]
                 d <- choose (0,9)
                 return (Digit d)

prop_reference_digit :: [Digit] -> Bool
prop_reference_digit xs = qsort xs == sort xs

data Either a b = Left a | Right b
 deriving (Eq,Ord,Show)

instance (Arbitrary a, Arbitrary b) => Arbitrary (Either a b) where
  arbitrary = do x <- arbitrary
                 y <- arbitrary
                 oneof [return (Left x), return (Right y)]

-- Execute all prop_ tests in a module:
--return []
--testAll = $quickCheckAll