{-# LANGUAGE TemplateHaskell #-}

import Test.QuickCheck hiding (Small)
import Data.List
import Prelude hiding (Either(..))

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

-- Idempotence: IF we sort a sorted list, it will be the same:
prop_idempotence :: [Int] -> Bool
prop_idempotence xs = qsort (qsort xs) == qsort xs

-- Element preservation: all elements of the input are also in the output
prop_preservation :: [Int] -> Bool
prop_preservation xs = null (xs \\ qsort xs) && null (qsort xs \\ xs)

-- The first element of a sorted lists is the minimum:
prop_first_sorted :: [Int] -> Property
prop_first_sorted xs = not (null xs) ==> head (qsort xs) == minimum xs

-- Test against a reference implementation:
prop_reference :: [Int] -> Bool
prop_reference xs = qsort xs == Data.List.sort xs
                     
prop_reference_classify :: [Int] -> Property
prop_reference_classify xs =
    classify (length xs <= 4)                    "small"    $
    classify (length xs > 20 && length xs <= 50) "big"      $
    classify (length xs > 50)                    "very big" $
      qsort xs == Data.List.sort xs
                    
prop_reference_collect :: [Int] -> Property
prop_reference_collect xs =
    collect (length xs) $
      qsort xs == Data.List.sort xs

-- Data type for small numbers:
data Small = Small Int
 deriving (Eq,Ord)

instance Show Small where
  show (Small x) = show x

-- Instance definition for Arbitrary:
instance Arbitrary Small where
  arbitrary = do --d <- elements [0..19]
                 d <- choose (0,19)
                 return (Small d)
                        
prop_reference_small :: [Small] -> Bool
prop_reference_small xs = qsort xs == Data.List.sort xs

-- Defining an instance for the Either type:
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)]

-- Definition of my own lists (to avoid conflict with generators
-- for predefined lists):
data MyList a = MyList [a]

-- Generator for my lists:
instance Arbitrary a => Arbitrary (MyList a) where
  arbitrary = sized $ \n -> do k <- choose (0,n)
                               makeArbitraries k

-- Predefined as `vector`:
makeArbitraries :: Arbitrary a => Int -> Gen (MyList a)
makeArbitraries n | n<=0      = return (MyList [])
                  | otherwise = do x <- arbitrary
                                   MyList xs <- makeArbitraries (n-1)
                                   return (MyList (x:xs))
              
-- run all property tests:
return []
tests = $quickCheckAll