import Test.QuickCheck -- Lecture 2B. Still doing Lists -- Recursion over lists -- quickCheck properties -- Polymorphic types -- recursion using a helper function ------------------------------------------ -- (:) and [] are the contructors: -- the basic building blocks for lists -- Prelude functions null, head and tail null' [] = True null' _ = False tail' :: [t] -> [t] tail' (_ : xs) = xs head' :: [t] -> t head' (x:_) = x -- polymorphic types -- Show show ------------------------------------------ -- Recall primitive recursion: fac 0 = 1 fac n | n > 0 = n * fac (n-1) -- [stupid slides] -- length length' [] = 0 length' (x:xs) = 1 + length' xs sum' :: Num a => [a] -> a sum' [] = 0 sum' (n:ns) = n + sum' ns -- init and last last' :: [a] -> a -- last' [] = error "last of empty list" last' [x] = x last' (_:xs) = last' xs init' :: [a] -> [a] init' [x] = [] init' (x:xs) = x:init' xs -- prop_initLast :: Bool -> [Bool] -> Property prop_initLast xs = not(null xs) ==> xs == init xs ++ [last xs] where _ = xs :: [Bool] -- alternative to defining the whole type -- quickCheck property -- reverse (inefficient) reverse' :: [a] -> [a] reverse' [] = [] reverse' (x:xs) = reverse' xs ++ [x] reverse'' xs = rev xs [] where -- tail recursion rev [] ys = ys rev (x:xs) ys = rev xs (x:ys) -- append -- (++) append :: [a] -> [a] -> [a] append [] ys = ys append (x:xs) ys = x:append xs ys -- smart reverse -- maximum -- index (!!) -- take, drop take' n [] = [] take' n xs | null xs || n <= 0 = [] take' n (x:xs) = x:take' (n-1) xs -- (!!)