{-# LANGUAGE TemplateHaskell #-}

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)
--isort (x:xs) = 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


-- Property: idempotence
prop_idempotence :: [Int] -> Bool
prop_idempotence xs = isort (isort xs) == isort xs

-- Property: all elements in origin are in the result and vice versa
prop_preservation :: [Int] -> Bool
prop_preservation xs = null (xs \\ isort xs) && null (isort xs \\ xs)

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

-- Unit test:
prop_sort914 :: Bool
prop_sort914 = isort [9,1,4] == [1,4,9]

--prop_conc_commutative :: [Int] -> [Int] -> Bool
--prop_conc_commutative xs ys = xs ++ ys == ys ++ xs

-- In order to run all property tests:
return []
runMyTests = $quickCheckAll