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