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

  • your vcs sucks

    I've been hacking on some Haskell stuff lately that's all managed in darcs and it's reminded me of an observation I made over two years ago now (see…

  • ghc llvm

    I read this thesis on an LLVM backend for GHC, primarily because I was curious to learn more about GHC internals. The thesis serves well as an…

  • found my bug!

    Not too interesting, but this has been bugging me for a week. Been working on a toy program that proxies a TCP connection. It was working fine for…

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