-- Lecture 2B
-- Lists
-- David Sands 
-- 2016-09-09

import Test.QuickCheck

----------------------------------------------------------
-- Recall lists...
-- We have seen the datatype for Hand (cardplay):

-- data Hand = Empty | Add Card Hand
{-
size :: Hand -> Int
size Empty = 0
size (Add c h) = 1 + size h
 -}

data ListInt    = EmptyInt | AddInt Int ListInt
data ListString = EmptyString | AddString String ListString

-- haskell psudocode
-- data [a] = [] | a : [a]


data List a = Empty | Add a (List a)
  deriving (Eq,Show)

eg1 :: List Bool
eg1 = Add True Empty

eg2 :: List String
eg2 = Add "Hello" (Add "World" Empty)

-- 
-- Examples of functions over lists
-- modules Prelude (and Data.List)
--

-- length
size :: [a] -> Int
size []     = 0
size (x:xs) = 1 + size xs

-- sum
sum' :: Num t => [t] -> t
sum' []     = 0
sum' (n:ns) = n + sum' ns

-- maximum 
maximum' :: Ord t => [t] -> t
maximum' []  = error "Empty list"
maximum' [x] = x
maximum' (x:xs) = max x (maximum' xs)


head' (x:_) = x
tail' (_:xs) = xs

last' [x]    = x
last' (_:xs) = last' xs

last'' xs = head (reverse xs)

prop_initlast :: [Bool] -> Property
prop_initlast xs = xs /= [] ==>
              init xs ++ [last xs] == xs


-- reverse
reverse' :: [a] -> [a]
reverse' []     = []
reverse' (x:xs) = (reverse' xs) ++ [x]

rev :: [a] -> [a]
rev xs = revHelper xs []
  where
   revHelper []     acc = acc
   revHelper (x:xs) acc = revHelper xs (x:acc)

{-
rev [1,2]
== rev (1:2:[])
== revHelper (1:2:[]) []
== revHelper (2:[])   (1:[])
== revHelper []       (2:1:[])
== (2:1:[])
== [2,1]
 -}
-- prop_reverse

-- index (!!)


-- take, drop
take',drop' :: Int -> [a] -> [a]
take' n _ | n <= 0    = []
take' _ []            = []
take' n (x:xs)        = x:take' (n-1) xs

drop' n xs | n <= 0   = xs
drop' _ []            = []
drop' n (x:xs)        = drop' (n-1) xs


prop_takedrop n xs = take' n xs ++ drop' n xs == xs
    where types = xs :: [Bool]