import Test.QuickCheck -- Lecture 3A. Still doing Lists -- 2018-09-13 ------------------------------------------ -- (:) and [] are the contructors: -- the basic building blocks for lists -- length length' :: [a] -> Int length' [] = 0 length' (_:xs) = 1 + length' xs -- sum sum' :: Num a => [a] -> a sum' [] = 0 sum' (n:ns) = n + sum' ns -- init and last last' [] = error "last of empty list BBBAAAADD!" last' [x] = x last' (_:xs) = last' xs init' [x] = [] -- skip the last element init' (x:xs) = x:init' xs -- keep the rest -- quickCheck property that relates init and last -- prop_initLast :: Bool -> [Bool] -> Property -- [See the video linked from the Web] -- quickCheck property -- reverse (inefficient) reverse' :: [a] -> [a] reverse' [] = [] reverse' (x:xs) = (reverse' xs) ++ [x] append :: [a] -> [a] -> [a] append [] ys = ys append (x:xs) ys = x : append xs ys -- tail recursion -- append -- (++) rev xs = rev' xs [] where rev' [] ys = ys rev' (x:xs) ys = rev' xs (x:ys) {- rev (1:2:[]) rev' (1:2:[]) [] rev' (2:[]) (1:[]) rev' [] (2:1:[]) (2:1:[]) -} -- maximum -- index (!!) -- take, drop -- (!!) -- [recording from here] -- Example: Recursive functions producing tuples data Vote = RG | A | Other deriving (Eq,Show) type Votes = [Vote] -- Compute the count of each type of vote tally,tally1,tally2 :: Votes -> (Int,Int,Int) -- Three different ways... -- Using a list comprehension: {- tally vs = ( length [ x | x <- vs, x == RG] , length [ x | x <- vs, x == A] , length [ x | x <- vs, x == Other] ) -- too much cut-and-paste! -} tally vs = (count RG, count A ,count Other) where count v = length [ x | x <- vs, x == v] -- Using a helper function with accumulating -- parameters tally1 vs = tal vs 0 0 0 where tal [] rg a o = (rg, a, o) tal (RG:ws) rg a o = tal ws (rg+1) a o tal (A:ws) rg a o = tal ws rg (a+1) o tal (Other:ws) rg a o = tal ws rg a (o+1) -- Direct recursive definition tally2 [] = (0,0,0) tally2 (v:vs) = count v (tally2 vs) where count RG (rg,a,o) = (rg+1,a,o) count A (rg,a,o) = (rg,a+1,o) count Other (rg,a,o) = (rg,a,o+1)