gistfile1.hs

import Test.QuickCheck
import Data.List

--
-- aux functions for verifications
--
isOrdered :: Ord a => [a] -> Bool
isOrdered [] = True
isOrdered [x] = True
isOrdered (x:x2:xs) = x <= x2 && isOrdered (x2:xs)

isPermuted :: Eq a => [a] -> [a] -> Bool
isPermuted xs ys | length xs /= length ys = False
                 | otherwise = isSubPermuted xs ys

isSubPermuted :: Eq a => [a] -> [a] -> Bool
isSubPermuted [] _ = True
isSubPermuted (x:xs) ys = x `elem` ys && isSubPermuted xs ys

--
-- sorting algorithms
--
qsort :: Ord a => [a] -> [a]
qsort [] = []
qsort (x:xs) = qsort small ++ [x] ++ qsort big
    where small = [y | y <- xs, y <= x]
          big = [y | y <- xs, y > x]

insertionSort :: Ord a => [a] -> [a]
insertionSort [] = []
insertionSort ys = insertionSortAux [] ys
    where insertionSortAux xs [] = xs
          insertionSortAux xs (y:ys) = insertionSortAux (insert y xs) ys

-- pracitce implementing insert
myInsert :: Ord a => a -> [a] -> [a]
myInsert x [] = [x]
myInsert x (y:ys) | x <= y = (x:y:ys)
                  | otherwise = y : myInsert x ys

--
-- verification
--
prop_qsort xs = isOrdered (qsort xs) && isPermuted xs (qsort xs)
prop_insertionSoret xs = isOrdered (insertionSort xs) && isPermuted xs (insertionSort xs)