Copilot.Library.Voting

This is an implementation of the Boyer-Moore Majority Vote Algorithm for Copilot, which solves the majority vote problem in linear time and constant memory in two passes. majority implements the first pass, and aMajority the second pass. For details of the Boyer-Moore Majority Vote Algorithm see the following papers:

• Wim H. Hesselink, "The Boyer-Moore Majority Vote Algorithm", 2005
• Robert S. Boyer and J Strother Moore, "MJRTY - A Fast Majority Vote Algorithm", 1981

In addition, An Introduction to Copilot in copilot-discussion explains a form of this code in section 4.

For instance, with four streams passed to majority, and the candidate stream then passed to aMajority:

vote1:       vote2:       vote3:       vote4:       majority:    aMajority:
0            0            0            0            0            true
1            0            0            0            0            true
1            1            0            0            1            false
1            1            1            0            1            true
1            1            1            1            1            true

For other examples, see Examples/VotingExamples.hs in the Copilot repository.

Documentation

majority

Arguments

:: (Eq a, Typed a)

=> [Stream a]

Vote streams

-> Stream a

Candidate stream

Majority vote first pass: choosing a candidate.

aMajority

Arguments

:: (Eq a, Typed a)

=> [Stream a]

Vote streams

-> Stream a

Candidate stream

-> Stream Bool

True if candidate holds majority

Majority vote second pass: checking that a candidate indeed has more than half the votes.