-- 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]