Skip to content

Instantly share code, notes, and snippets.

@wrhall
Last active August 29, 2015 14:01
Show Gist options
  • Save wrhall/7caa7b091537489fa740 to your computer and use it in GitHub Desktop.
Save wrhall/7caa7b091537489fa740 to your computer and use it in GitHub Desktop.
Majority Element Algorithm implemented in Haskell
module Majority
( isMajority
, majority
, occurrences
) where
majority :: Eq a => [a] -> Maybe a
majority [] = Nothing
majority xs'@(x: xs) = if isMajority majority' xs' then Just majority' else Nothing
where
-- Find unique candidate for the majority
(majority', _) = foldr majAcc (x, 1) xs
-- Accumulator function for finding a candidate majority element using foldr
majAcc :: (Eq t, Eq a, Num a) => t -> (t, a) -> (t, a)
majAcc elt (maj, num)
| elt == maj = (maj, num + 1)
| num == 0 = (elt, 1)
| otherwise = (maj, num - 1)
isMajority :: Eq a => a -> [a] -> Bool
isMajority maj l = (occurrences maj l) > (length l) `div` 2
occurrences :: (Eq a, Num b) => a -> [a] -> b
occurrences a = foldr (\x acc -> if x == a then acc + 1 else acc) 0
main :: IO ()
main = print $ majority [1,1,1,3,1,5]
@wrhall
Copy link
Author

wrhall commented May 29, 2014

What do you think of my occurrences method vs this count I just found on SO:
count x = length . filter (\x' -> x' == x)

(I maybe find theirs to be slightly clearer, but I'm not sure)

@wrhall
Copy link
Author

wrhall commented May 29, 2014

The general goal here (which may or may not be apparent) was just to use foldr a lot.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment