# Crate discrete [−] [src]

Combinatorial phantom types for discrete mathematics.

All discrete spaces have the following functions:

fn count(dim) -> usize;
fn to_index(dim, pos) -> usize;
fn to_pos(dim, index, &mut pos);

A discrete space is countable and has a one-to-one map with the natural numbers.

For example, a pair of natural numbers is a discrete space. There exists an algorithm that converts each pair of numbers into a number. Likewise there exists an algorithm that takes a number and converts it into a pair.

To construct a pair, you write:

let x: Pair<Data> = Construct::new();

The x above is a phantom variable, it does not use memory in the compiled program. It represents the discrete space that we have constructed. Now we can call methods on the space to examine its discrete structure.

A pair can be visualized as edges between points. If we have 4 points then we can create 6 edges:

o---o
|\ /|
| X |
|/ \|
o---o

To check this we can write:

let dim = 4; // number of points
assert_eq!(x.count(dim), 6); // count edges

Phantom types makes it possible to construct advanced discrete spaces. By using generic program, the algorithms to examine the structure follows from the construction of the space.

This makes it possible to solve tasks as:

• Compute upper bounds for certain problems
• Store data with a non-trivial structure
• Convert from and to natural numbers
• Iterate through the space
• Pick a random object of the space

Iterating through the space can be done simply by counting from zero up to the size of the space. For each number, we convert to a position within the space.

Pick a random object of the space can be done by generating a random number between 0 and the size of the space.