[][src]Crate discrete

Combinatorial phantom types for discrete mathematics.

All discrete spaces have the following functions:

This example is not tested
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:

This example is not tested
let x: Pair<Data> = Construct::new();

The x above is a phantom variable, which means it does not use memory in the compiled program. The phantom variable 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:

This example is not tested
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 a generic program, the algorithms to examine the structure follows from the construction of the space.

This makes it possible to solve tasks such as:

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

Iterating through all elements of a 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.

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

Advanced spaces

Phantom types are used because they represent the general spaces. For example, we can represent a general two-dimensional space, instead of binding the type to the size.

For any constructed space, there is a dimension and position type. The dimension and position types are compositions, given by the type of the constructed space.

Structs

Context

A discrete space that can model spatial operations over arbitrary states, therefore useful for context analysis.

Data

Used by the final subspace.

Dimension

Dimension is natural number, position is the same as index.

DimensionN

Dimension is a list of numbers, position is a list of numbers.

DirectedContext

Same as Context, but for directed edges.

Either

Selects between two spaces.

EqPair

Dimension is natural number, position is (min, max).

Homotopy

A discrete space that models undirected homotopy paths at a specified homotopy level.

NeqPair

Dimension is natural number, position is (a, b). Represents all directional pairs that has not same element for a and b.

Of

Used to combine the dimensional and position types.

Pair

Dimension is natural number, position is (min, max).

Permutation

Dimension is natural number, position is a list of numbers.

PowerSet

Dimension is natural number, position is a list of numbers.

SqPair

A discrete space that models a full square of NxN pairs.

Enums

HPoint

Stores a higher order point for homotopy spaces.

Select

Selects between spaces.

Traits

Construct

Constructs a new space.

Count

Implemented by spaces that can count the number of objects.

ToIndex

Implemented by spaces that can convert position to index.

ToPos

Implemented for spaces which can convert an index to position type.

Zero

Used to construct an uninitialized element of a discrete space.