{-# LANGUAGE TemplateHaskell #-}

import Test.QuickCheck
import Data.List  -- for the list difference operator (\\) and minimum

-- Insertion sort:
-- Insert an element in sorted order into a sorted list:
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:
isort :: [Int] -> [Int]
isort []     = []
isort (x:xs) = ins x (isort xs)

-- Property: the sorted list and the original list have the same length:
prop_same_length :: [Int] -> Bool
prop_same_length xs = length xs == length (isort xs)

-- Is isort idempotent?
prop_idempotence :: [Int] -> Bool
prop_idempotence xs = isort xs == isort (isort xs)

-- No new values, all old values are kept:
prop_preservation :: [Int] -> Bool
prop_preservation xs = null (xs \\ isort xs) && null (isort xs \\ xs)

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


-- Test against an existing sorting algorithm: Data.List.sort
prop_reference :: [Int] -> Bool
prop_reference xs = isort xs == sort xs


-- A unit test:
prop_isort_025 :: Bool
prop_isort_025 = isort [5,2,0] == [0,2,5]

----------------------------------------------------------------
-- Test all properties above:

return []
runAllTests = $quickCheckAll