import Prelude hiding (Either(..))

import Test.QuickCheck
import Data.List

-- Insertion sort

-- Insert an integer into a sorted list of integers
--ins :: Int -> [Int] -> [Int]
ins x []     = [x]
ins x (y:ys) = if x < y then x : y : ys
                        else y : ins x ys

-- Insertion sort on a list of integers
--isort :: [Int] -> [Int]
isort []     = []
isort (x:xs) = ins x (isort xs)

-- Property: the length of the list is unchanged
prop_same_length :: [Int] -> Bool
prop_same_length xs = length (isort xs) == length xs

-- ....

-- Test against a reference implementation.
prop_reference :: [Int] -> Bool
prop_reference xs = isort xs == Data.List.sort xs

-- Test against a reference implementation with test classification.
prop_reference_small :: [Int] -> Property
prop_reference_small xs =
  classify (length xs < 5) "small" $
  isort xs == Data.List.sort xs

-- Test against a reference implementation with test classification.
prop_reference_small_big :: [Int] -> Property
prop_reference_small_big xs =
  classify (length xs < 5) "small" $
  classify (length xs > 20) "big" $
  isort xs == Data.List.sort xs

-- Test against a reference implementation with test classification.
prop_reference_collect :: [Int] -> Property
prop_reference_collect xs =
  collect (length xs) $
  isort xs == Data.List.sort xs

--------------------------------------------------------------------
-- Own guessing of values:

{-
class Aribtrary a where 
  arbitrary :: Gen a  -- a generator producing values of type a
-- Gen is a monad!!!
-}

data Digit = Digit Int
  deriving (Eq,Ord)

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

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

-- Test against a reference implementation.
prop_reference_digit :: [Digit] -> Bool
prop_reference_digit xs = isort xs == Data.List.sort xs

-- Test against a reference implementation with test classification.
prop_reference_small_big_digit :: [Digit] -> Property
prop_reference_small_big_digit xs =
  classify (length xs < 5) "small" $
  classify (length xs > 20) "big" $
  isort xs == Data.List.sort xs

data Either a b = Left a | Right b

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

-- A list instance for Arbitrary:
instance Arbitrary a => Arbitrary [a] where
  arbitrary = sized $ \n -> do k <- choose (0,n)
                              makeArbitraries k

-- Guess a list with elements of a given length:
-- (predefined as `vector`)
makeArbitraries :: Arbitrary a -> Int -> Gen [a]
makeArbitraries | n <= 0    = return []
                | otherwise = do x <- arbitrary
                                 xs <- makeArbitraries (n - 1)
                                 return (x:xs)