Evan Martin (evan) wrote in evan_tech,
Evan Martin

condorcet haskell

Tonight I implemented the Schulze Condorcet algorithm in Haskell.

There was a lot of head scratching as I tried to figure out how to make a mutable 2d array, but ultimately it makes sense. There's a function effectively called "runWithState" that runs a function that uses some internal state* and returns its return value.

It's safe to call runWithState even from a state-free function, because the inner state-using function is always a function of its input: it only uses the state internally. But there's some type trickiness to make sure the state can't leak out via the return value, and so it took me a while to figure out how to actually write it.

This function is cute:
   winners :: VoteArray -> [Candidate]
1  winners paths = filter isWinner candidates where
2    isWinner c  = all (c `beats`) candidates
3    i `beats` j = paths!(i,j) >= paths!(j,i)
     candidates  = dim paths
That's saying:
1) winners are all candidates that satisfy isWinner;
2) a given candidate c isWinner if c "beats" all candidates;
3) a candidate i beats a candidate j if the path from i to j is greater than or equal to the path from j to i.

I like how each definition is short and simple. The paper's implementation uses an array of booleans and two nested for loops.

The paper also has this nasty nested for loop that I was busily copying when I realized it's a list comprehension:
[(i,j,k) | i<-range, j<-range, i/=j, k<-range, i/=k, j/=k]
That's: all (i,j,k), each drawn from range, where none of them are equal.

* Actually, the real definition is that a variable is passed along through the monad, but it feels like state and for a mutable array is actually implemented as state.
Tags: haskell, project

  • regular-expression parsing

    "Now you have two problems." Wikipedia has preliminary support for some new expressions in their markup, including an "if" statement. From the…

  • wikimedia drive

    The wikimedia foundation has a 2005 budget summary up. They want, among other things, $125k for hardware for this quarter alone. (The earlier…

  • two more wikipedia remarks

    I was thinking about some toy projects for Wikipedia data again and I poked around some Wikipedia code. Two observations: Good'ol timwi strikes…

  • Post a new comment


    default userpic
    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.