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

  • blog moved

    As described elsewhere, I've quit LiveJournal. If you're interested in my continuing posts, you should look at one of these (each contains feed…

  • dremel

    They published a paper on Dremel, my favorite previously-unpublished tool from the Google toolchest. Greg Linden discusses it: "[...] it is capable…

  • treemaps

    I finally wrote up my recent adventures in treemapping, complete with nifty clickable visualizations.

  • 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.