module Algorithms.Majority
( majority
) where
import Data.List (foldr)
import Prelude hiding (foldr)
majority :: Eq a => [a] -> Maybe a
majority xs = eliminate xs >>= verify xs
eliminate :: Eq a => [a] -> Maybe a
eliminate [] = Nothing
eliminate (x:xs) = Just (eliminate1 x xs)
eliminate1 :: Eq a => a -> [a] -> a
eliminate1 can0 = fst . foldr step (can0, 1 :: Int)
where
step x (can, cnt)
| can == x = (can, succ cnt)
| cnt == 0 = (x , 1 )
| otherwise = (can, pred cnt)
verify :: Eq a => [a] -> a -> Maybe a
verify xs can | verify1 can xs = Just can
| otherwise = Nothing
verify1 :: Eq a => a -> [a] -> Bool
verify1 can = (> 0) . foldr step (0 :: Int)
where
step x cnt
| can == x = succ cnt
| otherwise = pred cnt