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
-- (!!)