議席数をドント方式で

• http://ja.doukaku.org/26/

ちょっと無理めかもしれませんが、勉強のために合成モナドを使いました。

import Data.List
import Control.Monad.State
import Control.Monad.Writer

data Vote = V {idx::Int, num::Double, poll::Double} deriving Show
type Votes = [Vote]
type Proc a = StateT Votes (Writer [Int]) a

runProc :: Proc () -> Votes -> [Int]
runProc proc vs = map length $ group $ sort $ snd $ runWriter $ evalStateT proc vs

mkProc :: Int -> Proc ()
mkProc seats = if seats == 0 then return ()
               else do vs <- get 
                       let (V i n p:ts) = sortBy (\x y -> f y `compare` f x) vs
                         in tell [i] >> put ((V i (n + 1) p):ts) >> mkProc (seats - 1)
  where f x = poll x / (num x + 1)

exec x xs = runProc (mkProc x) (zipWith (\x y -> V x 0 y) [1..(length xs)] xs)