module Work_List where import Data.Char import Test.QuickCheck --------------------------------------------------------------------------- -- From last lecture -- l1 +++ l2 (a.k.a. ++) appends l2 after l1 (+++) :: [a] -> [a] -> [a] [] +++ bs = [] (a:as) +++ bs = a : (as +++ bs) -- property expressing that +++ is associative prop_appendAssoc :: [Int] -> [Int] -> [Int] -> Bool prop_appendAssoc as bs cs = as +++ (bs +++ cs) == (as +++ bs) +++ cs -- value s returns the number represented by the string s as an integer value :: String -> Int value str = valueHelp (reverse str) valueHelp :: String -> Int valueHelp "" = 0 valueHelp (d:ds) = digitToInt d + 10 * valueHelp ds -- Property of value and show prop_value :: String -> Property prop_value str = (s /= "" && head s /= '0') ==> show (value s) == s where s = [d | d <- str, isDigit d] prop_value' :: String -> Property prop_value' str | s /= "" && head s /= '0' = collect "interesting" (show (value s) == s) | otherwise = collect "uninteresting" True where s = [d | d <- str, isDigit d] prop_value2 :: Int -> Property prop_value2 n = n >= 0 ==> value (show n) == n --------------------------------------------------------------------------- -- slow definition of "reverse", uses a quadratic number of steps rev :: [a] -> [a] rev [] = [] rev (a:as) = rev as ++ [a] -- rev (1 : (2 : (3 : []))) -- [1,2,3] -- = rev (2 : (3 : [])) ++ [1] -- = (rev (3 : []) ++ [2]) ++ [1] -- = ((rev [] ++ [3]) ++ [2]) ++ [1] -- = (([] ++ [3]) ++ [2]) ++ [1] -- faster definition of "reverse", uses a linear number of steps rev2 :: [a] -> [a] rev2 as = revHelp as [] where revHelp [] korg = korg revHelp (a:as) korg = revHelp as (a:korg) -- rev2 (1 : (2 : (3 : []))) -- = revHelp (1 : (2 : (3 : []))) [] -- = revHelp (2 : (3 : []))) (1 : []) -- = revHelp (3 : []) (2 : (1 : [])) -- = revHelp [] (3 : (2 : (1 : []))) -- = (3 : (2 : (1 : []))) -- Show evaluation of -- rev (1 : (2 : (3 : []))) -- rev2 (1 : (2 : (3 : []))) -- Note: The technique used in the fast reverse 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 :: [Int] -> Bool prop_ReverseLength xs = length (reverse xs) == length xs -- indexing in the original list should give the same result as indexing -- "from the back" in the reversed list prop_ReverseIndex :: [Int] -> Int -> Property prop_ReverseIndex xs i = length xs > i && i >= 0 && length xs > 0 ==> (reverse xs !! i) == (xs !! (length xs - i - 1)) {- 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 -- Bad idea: replace ==> with guards -- Use collect to see why --------------------------------------------------------------------------- -- definition of "take" tak :: Int -> [a] -> [a] tak n [] = [] tak 0 _ = [] tak n (a:as) = a : tak (n-1) as -- 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 = length xs >= n && n >= 0 ==> length (tak n xs) == n prop_TakeLength' :: Int -> [Int] -> Property prop_TakeLength' n xs | length xs >= n = n >= 0 ==> length (tak n xs) == n | otherwise = n >= 0 ==> length (tak n xs) == length xs -- 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 = undefined -- 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 -- property stating that the result of maximum is greater >= all elements in the -- list prop_Maximum_Greater :: [Int] -> Bool prop_Maximum_Greater xs = undefined -- property stating that the result of maximum appears in the list prop_Maximum_Element :: [Int] -> Property prop_Maximum_Element xs = undefined -- 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]