copilot-libraries-3.2: Libraries for the Copilot language.
Copyright (c) 2011 National Institute of Aerospace / Galois Inc. Safe-Inferred Haskell2010

Copilot.Library.Voting

Description

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:

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.

Synopsis

Documentation

Arguments

 :: (Eq a, Typed a) => [Stream a] Vote streams -> Stream a Candidate stream

Majority vote first pass: choosing a candidate.

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.