Data.Enumeration

Utilities for constructing enumerations over datatypes.

An Enumeration is a mapping between a particular datatype and a Path, which consists of a list of natural numbers. Conceptually, we can think of all the values of a given datatype as being organized into a tree, with nodes representing decisions that narrow down the choices. In such a scheme, a Path represents a path through the tree to a single value, and an Enumeration is a procedure for converting a Path to and from a value.

An Enumeration has two key functions: fromPath and toPath, which translate between paths and instances of a datatype. These functions are expected to be inverses; or:

• fromPath (toPath v) == v for all values in the domain

Beyond this, there are no additional restrictions. Specifically, two paths may map to the same value.

The numBranches function indicates the maximum value of the first path element for an Enumeration. The minimum value is always 0, and all values between 0 and numBranches must be valid. If there is no upper bound on the value of the first path element, numBranches returns Nothing. The toSizedPath maps a value to a path, which also contains the result of numBranches at each step in the path.

The withPrefix function supplies a partial path to an Enumeration, yielding a new Enumeration that maps each value to the same path(s) as the original Enumeration, with the prefix added or removed. More formally, if

• subenc = withPrefix enc prepath

Then

• toPath enc val == prepath ++ toPath subenc val

• fromPath enc (prepath ++ subpath) == fromPath subenc subpath

With multiple uses of withPrefix, the following must be true:

• withPrefix (withPrefix enc path1) path2 == withPrefix enc (path1 ++ path2)

Finally, if a complete path is given to withPrefix, then the result is a singleton encoding that gives the value associated with that path. That is:

• fromPath enc fullpath == fromPath (withPrefix enc fullpath) []

This provides "warm-start" functionality for Enumerations. When translating a large number of Paths with the same prefix, it will generally be much more efficient to use withPrefix and use the resulting Enumeration than to translate the Paths directly.

The prefix function gives the current prefix for an Enumeration. The following rule describes the relationship between prefix and withPrefix:

• prefix (withPrefix enc prepath) == prepath

Enumerations are similar to Encodings from the arith-encode library, except Enumerations are generally more flexible, and can more easily accomodate complex datatypes with invariants. However, as Paths are constructed from natural numbers, we can create an Enumeration using a series of Encodings for intermediate data. The functions in this module provide the ability to construct Enumerations using Encodings

A singleton Enumeration can be constructed using the singleton and singletonWithPrefix functions.

An Encoding for a datatype can be converted into an Enumeration (where all paths have a single element) using the fromEncoding and fromEncodingWithPrefix functions.

The step and stepWithPrefix functions construct an Enumeration from an Encoding for an intermediate value, and a generator function that produces an Enumeration from the intermediate value.

The withPrefix variants for each of these take a prefix path, where the non-withPrefix variants set the prefix to [].

Definitions

data Enumeration ty

A datatype that represents a mapping between Paths and tys. Note that unlike Encodings, not all Paths are necessarily valid.

type Path = [Integer]

A path that uniquely identifies a value in an Enumeration.

data BadPath

An exception thrown when a Path is invalid.

Constructors

BadPath String

Instances

Show BadPath

Exception BadPath

Typeable * BadPath

data IllegalArgument :: *

An exception to be thrown if an illegal argument is given to encode, decode.

Constructors

IllegalArgument !String

Instances

Show IllegalArgument

Exception IllegalArgument

Typeable * IllegalArgument

Using Enumerations

fromPath :: Enumeration ty -> Path -> ty

Generate a ty from a Path

toPath :: Enumeration ty -> ty -> Path

Convert a ty to a Path

toSizedPath :: Enumeration ty -> ty -> [(Integer, Maybe Integer)]

Convert to a list of pairs, where the fst holds the path entry, and snd holds numBranches. This is used primarily for encoding values as binary.

withPrefix :: Enumeration ty -> Path -> Enumeration ty

Given a prefix path, get an enumeration that generates tys from the rest of the path.

numBranches :: Enumeration ty -> Maybe Integer

Get the upper bound on values for the first path component, or Nothing if there is no bound.

prefix :: Enumeration ty -> Path

The prefix path.

Constructions

singleton

Arguments

:: Eq ty

=> ty

The value to map to and from the empty path.

-> Enumeration ty

Create an Enumeration with an empty prefix that maps a single value to and from the empty path. Equivalent to singletonWithPrefix []

singletonWithPrefix :: Eq ty => Path -> ty -> Enumeration ty

Create an Enumeration with a given prefix path that maps a single value to and from the empty path.

fromEncoding

Arguments

:: Eq ty

=> Encoding ty

The Encoding to use

-> Enumeration ty

Create an Enumeration with an empty prefix from a single Encoding. The Path will always be of length 1, and contains the encoded value.

fromEncodingWithPrefix :: Eq ty => Path -> Encoding ty -> Enumeration ty

Create an Enumeration with a given prefix from a single Encoding. The Path will always be of length 1, and contains the encoded value.

step

Arguments

:: Encoding ty1

The encoding for the first type.

-> (Path -> ty1 -> Enumeration ty2)

A function that produces an enumeration from the first type.

-> (ty2 -> ty1)

A function that extracts the first type from the second.

-> Enumeration ty2

Create an Enumeration with an empty prefix that uses an Encoding to convert the first element of the path to an interim value, then uses that value to construct an Enumeration to decode the rest of the path.

stepWithPrefix

Arguments

:: Path

The prefix path.

-> Encoding ty1

The Encoding for the first type.

-> (Path -> ty1 -> Enumeration ty2)

A function that produces an enumeration from the first type.

-> (ty2 -> ty1)

A function that extracts the first type from the second.

-> Enumeration ty2

Create an Enumeration with a prefix that uses an Encoding to convert the first element of the path to an interim value, then uses that value to construct an Enumeration to decode the rest of the path.