Am Sonntag, 22. Februar 2009 17:12 schrieb Keith Sheppard:

...

Message: 8 Date: Sun, 22 Feb 2009 01:15:30 +0000 From: "Matthew J. Williams" Subject: [Haskell-beginners] Majority Element To: beginners@haskell.org Message-ID: <49a0a726.278e420a.6b19.ffffe361@mx.google.com> Content-Type: text/plain; charset="us-ascii"; format=flowed

Dear listers

What is a majority element in an array?

Sincerely Matthew J. Williams

The answer is implicit in Keith's code below, but let's state it also in plain text: A majority element in a collection C of n things is a value that appears strictly more than n/2 times in C. In general, no majority element exists. I had never met the term before Matthew's post. Does anybody know for what it is important?

I think this gets you what you want:

majority nums = find (\x -> fromIntegral (length x) > (fromIntegral (length nums)) / 2) (group(sort(nums)))

You don't need the fromIntegral here, integer division does the right thing. In case a majority element a exists, this returns Just [a,a...], so you might add an "fmap head" to get the element itself.

It returns a "Maybe" list containing all majority elements. Something that avoids the sort would be faster though.

Not the naive algorithm. However, if the type of elements doesn't belong to Ord, we can't use sort :(

-Keith

findMajority :: Eq a => [a] -> Maybe a findMajority [] = Nothing findMajority xxs@(x:xs) = case sweep x 1 xs of Nothing -> Nothing Just candidate -> verify candidate 0 xxs where sweep a count [] | count == 0 = Nothing | otherwise = Just a sweep _ 0 (y:ys) = sweep y 1 ys sweep a count (y:ys) | a == y = sweep a (count+1) ys | otherwise = sweep a (count-1) ys verify c count (y:ys) | c == y = verify c (count+1) ys | otherwise = verify c (count-1) ys verify c count [] | count > 0 = Just c | otherwise = Nothing Cheers, Daniel