copilot-libraries-4.7.1: Libraries for the Copilot language.

Copyright | (c) 2011 National Institute of Aerospace / Galois Inc.
Safe Haskell | Safe-Inferred
Language | 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:

- 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 and copilot-discussion explain 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/Voting.hs` in the Copilot repository.

Synopsis

- majority :: (Eq a, Typed a) => [Stream a] -> Stream a
- aMajority :: (Eq a, Typed a) => [Stream a] -> Stream a -> Stream Bool

# Documentation

majority Source #

Arguments

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

Majority vote first pass: choosing a candidate.

aMajority Source #

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.