{-# LANGUAGE TemplateHaskell #-} -- for automated testing

import Test.QuickCheck
import Data.List

-- Insert an element 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)

prop_same_length :: [Int] -> Bool
prop_same_length xs = length xs == length (isort xs)

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

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

-- The first element of the sorted list must be the smallest one
prop_smallest_first :: [Int] -> Property
prop_smallest_first xs = not (null xs) ==> head (isort xs) == minimum xs

-- Tests again an existing sort function (Data.List: sort)
prop_reference :: [Int] -> Bool
prop_reference xs = isort xs == sort xs

-- Unit test:
prop_isort514 :: Bool
prop_isort514 = isort [5,1,4] == [1,4,5]

return [] -- for automated testing
runTests = $quickCheckAll