majority (empty) → 1.0

raw patch · 6 files changed

+181/−0 lines, 6 filesdep +haskell2010setup-changed

Dependencies added: haskell2010

Files

• LICENSE +2/−0
• README.md +38/−0
• Setup.hs +2/−0
• majority.cabal +39/−0
• src/Algorithms/Majority.hs +53/−0
• test/Properties.hs +47/−0

@@ -0,0 +1,2 @@+CC0 1.0 Universal Public Domain Dedication+http://creativecommons.org/publicdomain/zero/1.0/

@@ -0,0 +1,38 @@+Majority+========++The Boyer-Moore Majority Vote Algorithm determines if there in a list of votes+is a candidate that holds more than half of the majority, and if so, finds+this candidate. It does so in time linear in the length of the input list and+constant memory. For a detailed description of the algorithm, see these papers:++  * Wim H. Hesselink,+    \"/The Boyer-Moore Majority Vote Algorithm/\",+    2005;++  * Robert S. Boyer and J. Strother Moore,+    \"/MJRTY - A Fast Majority Vote Algorithm/\",+    1982.++Install+-------++[Haskell Platform]: http://hackage.haskell.org/platform/++Assuming you have installed the [Haskell Platform][] use cabal:++    $ cabal install majority++Bugs+----++Comments, bug reports, and patches will be much appreciated:++  * <niswegmann@gmail.com>++License+-------++This library is distributed under a CC0 1.0 Universal Public Domain Dedication:++  * <http://creativecommons.org/publicdomain/zero/1.0/>

@@ -0,0 +1,2 @@+import Distribution.Simple+main = defaultMain

@@ -0,0 +1,39 @@+name:                majority+version:             1.0+synopsis:            Boyer-Moore Majority Vote Algorithm+category:            Algorithms+stability:           provisional+license:             PublicDomain+license-file:        LICENSE+author:              Nis N. Wegmann+maintainer:          niswegmann@gmail.com+homepage:            https://github.com/niswegmann/majority+extra-source-files:  README.md, test/Properties.hs+build-type:          Simple+cabal-version:       >= 1.10++description:++  The Boyer-Moore Majority Vote Algorithm determines if there in a list of votes+  is a candidate that holds more than half of the majority, and if so, finds+  this candidate. It does so in time linear in the length of the input list and+  constant memory. For a detailed description of the algorithm, see these papers:+  .+    * Wim H. Hesselink,+      \"/The Boyer-Moore Majority Vote Algorithm/\",+      2005;+  .+    * Robert S. Boyer and J. Strother Moore,+      \"/MJRTY - A Fast Majority Vote Algorithm/\",+      1982.++source-repository head+  type:     git+  location: https://github.com/niswegmann/majority.git++library+  default-language:  Haskell2010+  build-depends:     haskell2010+  ghc-options:       -O2 -Wall -fwarn-tabs+  hs-source-dirs:    src+  exposed-modules:   Algorithms.Majority

@@ -0,0 +1,53 @@+{-|+License     :  CC0 1.0 Universal Public Domain Dedication+Maintainer  :  niswegmann@gmail.com+Stability   :  provisional+Portability :  portable (Haskell 2010)+-}++module Algorithms.Majority+  ( majority+  ) where++import Data.List (foldr)+import Prelude hiding (foldr)++-- | /O(length xs)/, Determines if there in a list of votes /xs/ is a candidate+-- that has more than half of the votes, and if so, returns that canditate.+--+-- E.g. applying @majority@ on the string @\"AAACCBBCCCBCC\"@ yields+-- @Just \'C\'@, since @\'C\'@ has 7 out of 13 votes.++majority :: Eq a => [a] -> Maybe a+majority xs = eliminate xs >>= verify xs++-- First pass: eliminates all but a single candidate.+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++    {-# INLINE step #-}+    step x (can, cnt)+      | can == x  = (can, succ cnt)+      | cnt == 0  = (x  , 1       )+      | otherwise = (can, pred cnt)++-- Second pass: asserts that the remaining candidate is a majority.+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++    {-# INLINE step #-}+    step x cnt+      | can == x  = succ cnt+      | otherwise = pred cnt

@@ -0,0 +1,47 @@+module Main (main) where++import Algorithms.Majority (majority)+import Data.Function (on)+import Data.List (group, maximumBy, partition)+import Data.Map (empty, insertWith, toList)+import Test.QuickCheck (quickCheck)++verify :: Eq a => a -> [a] -> Maybe a+verify can xs | length ys > length zs = Just can+              | otherwise             = Nothing++  where++    (ys, zs) = partition (== can) xs++maximumByWeight :: [(a, Int)] -> a+maximumByWeight = fst . maximumBy (compare `on` snd)++majority_map :: Ord a => [a] -> Maybe a+majority_map xs = verify can xs++  where++    acc = foldr (\ x -> insertWith (+) x 1) empty xs++    can = maximumByWeight (toList acc)++majority_group :: Eq a => [a] -> Maybe a+majority_group xs = verify can xs++  where++    acc = [ (head ys, length ys) | ys <- group xs ]++    can = maximumByWeight acc++prop_majority_map :: [Int] -> Bool+prop_majority_map xs = majority xs == majority_map xs++prop_majority_group :: [Int] -> Bool+prop_majority_group xs = majority xs == majority_group xs++main =+  do+    quickCheck prop_majority_map+    quickCheck prop_majority_group