import Test.QuickCheck
-- some more examples of recursive functions over lists, including properties
-- slow definition of "reverse", uses a quadratic number of steps
rev :: [a] -> [a]
rev [] = []
rev (x:xs) = rev xs ++ [x]
---------------------------------------------------------------------------
-- faster definition of "reverse", uses a linear number of steps
rev2 :: [a] -> [a]
rev2 xs = revHelp xs []
revHelp :: [a] -> [a] -> [a]
revHelp [] korg = korg
revHelp (x:xs) korg = revHelp xs (x:korg)
-- Note: The technique used in rev2 can be useful in lab 2 (e.g shuffling a deck
-- of cards).
---------------------------------------------------------------------------
-- properties of "reverse" that can be tested using QuickCheck
-- the length of a reversed lists should be the same as the original list
prop_ReverseLength xs =
length (rev2 xs) == length (xs :: [Int])
-- indexing in the original list should give the same result as indexing
-- "from the back" in the reversed list
prop_ReverseIndex xs i =
0 <= i && i < length (xs :: [Int]) ==>
xs !! i == rev2 xs !! (length xs - 1 - i)
{-
0 1 2 3 4 (5)
['a','b','c','d','e']
0 1 2 3 4
['e','d','c','b','a']
-}
-- testing a property
-- A ==> B
-- will find 100 tests that make A true, and then test B
-- this is a worse version of the above property, because all tests we run
-- are counted towards the 100 tests, even the ones where A is false
prop_ReverseIndex' :: [Int] -> Int -> Bool
prop_ReverseIndex' xs i
| 0 <= i && i < length xs = xs !! i == rev2 xs !! (length xs - 1 - i)
| otherwise = True
---------------------------------------------------------------------------
-- definition of "take"
tak :: Int -> [a] -> [a]
tak n _ | n <= 0 = []
tak _ [] = []
tak n (x:xs) = x : tak (n-1) xs
-- predicting the length of the result of take, for values that are
-- small: if we take n elements from a list with at least n elements, the
-- result has length n
prop_TakeLength :: Int -> [Int] -> Property
prop_TakeLength n xs =
0 <= n && n <= length xs ==>
length (tak n xs) == n
-- predicting the length of the result of take, for values that are
-- small: if we take n elements from a list smaller than n elements, the
-- result has all the elements
prop_TakeLengthTooBig :: Int -> [Int] -> Property
prop_TakeLengthTooBig n xs =
n > length xs ==>
tak n xs == xs
-- property stating the relationship between the functions "take" and "drop"
prop_TakeDrop :: Int -> [Int] -> Bool
prop_TakeDrop n xs =
take n xs ++ drop n xs == xs
prop_Maximum_Greater :: [Int] -> Bool
prop_Maximum_Greater xs =
and [ maximum xs >= x | x <- xs ]
prop_Maximum_Element :: [Int] -> Property
prop_Maximum_Element xs =
length xs > 0 ==>
maximum xs `elem` xs
-- be careful, QuickCheck says the following is true
-- (because the type of xs defaults to [()])
prop_Reverse_Wierd xs =
reverse xs == xs
-- proper test
prop_Reverse xs =
reverse (reverse xs) == xs
where
_ = xs :: [Int]