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 pathsThat'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.