-- voting algorithms

-- sample data
votes1 :: [String]
votes1 = ["Red","Blue","Green","Blue","Blue","Red","Yellow","Blue","Blue"]

ballots :: [[String]]
ballots = [["Red", "Green", "Blue"],
           ["Blue"],
           ["Green","Yellow","Red","Blue"],
           ["Blue","Green","Red"],
           ["Green"]]


-- helper functions
-- (observe that we have used composition and excluded the list parameter from the definition
-- (but it is included in the type signature))
count :: Eq a => a -> [a] -> Int
count x = length . filter (== x)

removeDups :: Eq a => [a] -> [a]
removeDups [] = []
removeDups (x:xs) = x : filter (/= x) (removeDups xs)

result :: Ord a => [a] -> [(a, Int)]
result vs = sort [(v, count v vs) | v <- removeDups vs]

-- more helper functions (used only in the alternative vote algorithm)
removeEmpty :: Eq a => [[a]] -> [[a]]
removeEmpty = filter (/= [])

eliminate :: Eq a => a -> [[a]] -> [[a]]
eliminate x = map (filter (/= x))

rank :: Ord a => [[a]] -> [a]
rank = map fst.result.map head


-- as implemented, this will return the member that appears last in the sorted list
-- this does not mean this member had more votes than everyone else (the second-last 
-- etc might have the same number of votes) nor does it mean that the member was
-- 'first past the post' as it does not check that the member's share was >50% of the total
mostVotes :: Ord a => [a] -> a
mostVotes = fst . last . result

lastStanding :: Ord a => [[a]] -> a
lastStanding bs = case rank (removeEmpty bs) of
                       [c]    -> c
                       (c:cs) -> lastStanding (eliminate c bs)
