Copyright | Brent Yorgey |
---|---|

Maintainer | byorgey@gmail.com |

Safe Haskell | None |

Language | Haskell2010 |

An *invertible enumeration* is a bijection between a set of values
and the natural numbers (or a finite prefix thereof), represented
as a pair of inverse functions, one in each direction. Hence they
support efficient indexing and can be constructed for very large
finite sets. A few examples are shown below.

Compared to Data.Enumeration, one can also build invertible
enumerations of functions (or other type formers with contravariant
arguments); however, invertible enumerations no longer make for
valid `Functor`

, `Applicative`

, or `Alternative`

instances.

This module exports many of the same names as Data.Enumeration; the expectation is that you will choose one or the other to import, though of course it is possible to import both if you qualify the imports.

## Synopsis

- data IEnumeration a
- data Cardinality
- card :: IEnumeration a -> Cardinality
- type Index = Integer
- select :: IEnumeration a -> Index -> a
- locate :: IEnumeration a -> a -> Index
- isFinite :: IEnumeration a -> Bool
- enumerate :: IEnumeration a -> [a]
- void :: IEnumeration a
- unit :: IEnumeration ()
- singleton :: a -> IEnumeration a
- finite :: Integer -> IEnumeration Integer
- finiteList :: Eq a => [a] -> IEnumeration a
- boundedEnum :: forall a. (Enum a, Bounded a) => IEnumeration a
- nat :: IEnumeration Integer
- int :: IEnumeration Integer
- cw :: IEnumeration Rational
- rat :: IEnumeration Rational
- mapE :: (a -> b) -> (b -> a) -> IEnumeration a -> IEnumeration b
- takeE :: Integer -> IEnumeration a -> IEnumeration a
- dropE :: Integer -> IEnumeration a -> IEnumeration a
- zipE :: IEnumeration a -> IEnumeration b -> IEnumeration (a, b)
- infinite :: IEnumeration a -> IEnumeration a
- (<+>) :: IEnumeration a -> IEnumeration b -> IEnumeration (Either a b)
- (><) :: IEnumeration a -> IEnumeration b -> IEnumeration (a, b)
- interleave :: IEnumeration (IEnumeration a) -> IEnumeration (Index, a)
- maybeOf :: IEnumeration a -> IEnumeration (Maybe a)
- eitherOf :: IEnumeration a -> IEnumeration b -> IEnumeration (Either a b)
- listOf :: IEnumeration a -> IEnumeration [a]
- finiteSubsetOf :: IEnumeration a -> IEnumeration [a]
- finiteEnumerationOf :: Int -> IEnumeration a -> IEnumeration (Enumeration a)
- functionOf :: IEnumeration a -> IEnumeration b -> IEnumeration (a -> b)
- undiagonal :: (Integer, Integer) -> Integer

# Invertible enumerations

data IEnumeration a Source #

An invertible enumeration is a bijection between a set of enumerated values and the natural numbers, or a finite prefix of the natural numbers. An invertible enumeration is represented as a function from natural numbers to values, paired with an inverse function that returns the natural number index of a given value. Enumerations can thus easily be constructed for very large sets, and support efficient indexing and random sampling.

Note that `IEnumeration`

cannot be made an instance of `Functor`

,
`Applicative`

, or `Alternative`

. However, it does support the
`functionOf`

combinator which cannot be supported by
Data.Enumeration.

## Using enumerations

data Cardinality Source #

The cardinality of a countable set: either a specific finite natural number, or countably infinite.

## Instances

card :: IEnumeration a -> Cardinality Source #

Get the cardinality of an enumeration.

select :: IEnumeration a -> Index -> a Source #

Select the value at a particular index. Precondition: the index must be strictly less than the cardinality.

locate :: IEnumeration a -> a -> Index Source #

Compute the index of a particular value in its enumeration.
Note that the result of `locate`

is only valid when given a
value which is actually in the range of the enumeration.

isFinite :: IEnumeration a -> Bool Source #

Test whether an enumeration is finite.

`>>>`

True`isFinite (finiteList [1,2,3])`

`>>>`

False`isFinite nat`

enumerate :: IEnumeration a -> [a] Source #

List the elements of an enumeration in order. Inverse of
`finiteList`

.

## Primitive enumerations

void :: IEnumeration a Source #

The empty enumeration, with cardinality zero and no elements.

`>>>`

Finite 0`card void`

`>>>`

[]`enumerate void`

unit :: IEnumeration () Source #

The unit enumeration, with a single value of `()`

at index 0.

`>>>`

Finite 1`card unit`

`>>>`

[()]`enumerate unit`

`>>>`

0`locate unit ()`

singleton :: a -> IEnumeration a Source #

An enumeration of a single given element at index 0.

`>>>`

Finite 1`card (singleton 17)`

`>>>`

[17]`enumerate (singleton 17)`

`>>>`

0`locate (singleton 17) 17`

finite :: Integer -> IEnumeration Integer Source #

A finite prefix of the natural numbers.

`>>>`

Finite 5`card (finite 5)`

`>>>`

Finite 1234567890987654321`card (finite 1234567890987654321)`

`>>>`

[0,1,2,3,4]`enumerate (finite 5)`

`>>>`

[]`enumerate (finite 0)`

`>>>`

2`locate (finite 5) 2`

finiteList :: Eq a => [a] -> IEnumeration a Source #

Construct an enumeration from the elements of a *finite* list.
The elements of the list must all be distinct. To turn an
enumeration back into a list, use `enumerate`

.

`>>>`

[2,3,8,1]`enumerate (finiteList [2,3,8,1])`

`>>>`

8`select (finiteList [2,3,8,1]) 2`

`>>>`

2`locate (finiteList [2,3,8,1]) 8`

`finiteList`

does not work on infinite lists: inspecting the
cardinality of the resulting enumeration (something many of the
enumeration combinators need to do) will hang trying to compute
the length of the infinite list.

`finiteList`

uses (`!!`

) and `findIndex`

internally (which both
take $O(n)$ time), so you probably want to avoid using it on long
lists. It would be possible to make a version with better
indexing performance by allocating a vector internally, but I am
too lazy to do it. If you have a good use case let me know
(better yet, submit a pull request).

boundedEnum :: forall a. (Enum a, Bounded a) => IEnumeration a Source #

Enumerate all the values of a bounded `Enum`

instance.

`>>>`

[False,True]`enumerate (boundedEnum @Bool)`

`>>>`

'a'`select (boundedEnum @Char) 97`

`>>>`

90`locate (boundedEnum @Char) 'Z'`

`>>>`

Finite 18446744073709551616`card (boundedEnum @Int)`

`>>>`

-9223372036854775808`select (boundedEnum @Int) 0`

nat :: IEnumeration Integer Source #

The natural numbers, `0, 1, 2, ...`

.

`>>>`

[0,1,2,3,4,5,6,7,8,9]`enumerate . takeE 10 $ nat`

int :: IEnumeration Integer Source #

All integers in the order `0, 1, -1, 2, -2, 3, -3, ...`

.

cw :: IEnumeration Rational Source #

The positive rational numbers, enumerated according to the Calkin-Wilf sequence.

`>>>`

[1 % 1,1 % 2,2 % 1,1 % 3,3 % 2,2 % 3,3 % 1,1 % 4,4 % 3,3 % 5]`enumerate . takeE 10 $ cw`

`>>>`

4`locate cw (3 % 2)`

`>>>`

3183`locate cw (23 % 99)`

rat :: IEnumeration Rational Source #

An enumeration of all rational numbers: 0 first, then each rational in the Calkin-Wilf sequence followed by its negative.

`>>>`

[0 % 1,1 % 1,(-1) % 1,1 % 2,(-1) % 2,2 % 1,(-2) % 1,1 % 3,(-1) % 3,3 % 2]`enumerate . takeE 10 $ rat`

`>>>`

2540`locate rat (-45 % 61)`

## Enumeration combinators

mapE :: (a -> b) -> (b -> a) -> IEnumeration a -> IEnumeration b Source #

Map a pair of inverse functions over an invertible enumeration of
`a`

values to turn it into an invertible enumeration of `b`

values. Because invertible enumerations contain a *bijection* to
the natural numbers, we really do need both directions of a
bijection between `a`

and `b`

in order to map. This is why
`IEnumeration`

cannot be an instance of `Functor`

.

takeE :: Integer -> IEnumeration a -> IEnumeration a Source #

Take a finite prefix from the beginning of an enumeration. ```
takeE
k e
```

always yields the empty enumeration for \(k \leq 0\), and
results in `e`

whenever `k`

is greater than or equal to the
cardinality of the enumeration. Otherwise `takeE k e`

has
cardinality `k`

and matches `e`

from `0`

to `k-1`

.

`>>>`

[-9223372036854775808,-9223372036854775807,-9223372036854775806]`enumerate $ takeE 3 (boundedEnum @Int)`

`>>>`

[1,2]`enumerate $ takeE 2 (finiteList [1..5])`

`>>>`

[]`enumerate $ takeE 0 (finiteList [1..5])`

`>>>`

[1,2,3,4,5]`enumerate $ takeE 7 (finiteList [1..5])`

dropE :: Integer -> IEnumeration a -> IEnumeration a Source #

Drop some elements from the beginning of an enumeration. ```
dropE k
e
```

yields `e`

unchanged if \(k \leq 0\), and results in the empty
enumeration whenever `k`

is greater than or equal to the
cardinality of `e`

.

`>>>`

[3,4,5]`enumerate $ dropE 2 (finiteList [1..5])`

`>>>`

[1,2,3,4,5]`enumerate $ dropE 0 (finiteList [1..5])`

`>>>`

[]`enumerate $ dropE 7 (finiteList [1..5])`

zipE :: IEnumeration a -> IEnumeration b -> IEnumeration (a, b) Source #

Zip two enumerations in parallel, producing the pair of elements at each index. The resulting enumeration is truncated to the cardinality of the smaller of the two arguments.

Note that defining `zipWithE`

as in Data.Enumeration is not
possible since there would be no way to invert it in general.
However, one can use `zipE`

in combination with `mapE`

to achieve
a similar result.

`>>>`

[(0,False),(1,True)]`enumerate $ zipE nat (boundedEnum @Bool)`

`>>>`

`cs = mapE (uncurry replicate) (length &&& head) (zipE (finiteList [1..10]) (dropE 35 (boundedEnum @Char)))`

`>>>`

["#","$$","%%%","&&&&","'''''","((((((",")))))))","********","+++++++++",",,,,,,,,,,"]`enumerate cs`

`>>>`

7`locate cs "********"`

infinite :: IEnumeration a -> IEnumeration a Source #

Explicitly mark an enumeration as having an infinite cardinality, ignoring the previous cardinality. It is sometimes necessary to use this as a "hint" when constructing a recursive enumeration whose cardinality would otherwise consist of an infinite sum of finite cardinalities.

For example, consider the following definitions:

data Tree = L | B Tree Tree deriving Show toTree :: Either () (Tree, Tree) -> Tree toTree = either (const L) (uncurry B) fromTree :: Tree -> Either () (Tree, Tree) fromTree L = Left () fromTree (B l r) = Right (l,r) treesBad :: IEnumeration Tree treesBad = mapE toTree fromTree (unit`<+>`

(treesBad`><`

treesBad)) trees :: IEnumeration Tree trees = infinite $ mapE toTree fromTree (unit`<+>`

(trees`><`

trees))

Trying to use `treesBad`

at all will simply hang, since trying to
compute its cardinality leads to infinite recursion.

>>> select treesBad 5 ^CInterrupted.

However, using `infinite`

, as in the definition of `trees`

,
provides the needed laziness:

`>>>`

Infinite`card trees`

`>>>`

[L,B L L,B L (B L L)]`enumerate . takeE 3 $ trees`

`>>>`

B (B (B (B (B L L) (B (B (B L L) L) L)) (B L (B L (B L L)))) (B (B (B L (B L (B L L))) (B (B L L) (B L L))) (B (B L (B L (B L L))) L))) (B (B L (B (B (B L (B L L)) (B L L)) L)) (B (B (B L (B L L)) L) L))`select trees 87239862967296`

`>>>`

B (B L (B L L)) (B (B L (B L L)) (B L (B L L)))`select trees 123`

`>>>`

123`locate trees (B (B L (B L L)) (B (B L (B L L)) (B L (B L L))))`

(<+>) :: IEnumeration a -> IEnumeration b -> IEnumeration (Either a b) Source #

Sum, *i.e.* disjoint union, of two enumerations. If both are
finite, all the values of the first will be enumerated before the
values of the second. If only one is finite, the values from the
finite enumeration will be listed first. If both are infinite, a
fair (alternating) interleaving is used, so that every value ends
up at a finite index in the result.

Note that this has a different type than the version in
Data.Enumeration. Here we require the output to carry an
explicit `Either`

tag to make it invertible.

`>>>`

[Left 17,Right 0,Right 1,Right 2,Right 3]`enumerate . takeE 5 $ singleton 17 <+> nat`

`>>>`

[Right 17,Left 0,Left 1,Left 2,Left 3]`enumerate . takeE 5 $ nat <+> singleton 17`

`>>>`

[Left 0,Right 0,Left 1,Right 1,Left 2]`enumerate . takeE 5 $ nat <+> nat`

`>>>`

71`locate (nat <+> nat) (Right 35)`

(><) :: IEnumeration a -> IEnumeration b -> IEnumeration (a, b) Source #

Cartesian product of enumerations. If both are finite, uses a
simple lexicographic ordering. If only one is finite, the
resulting enumeration is still in lexicographic order, with the
infinite enumeration as the most significant component. For two
infinite enumerations, uses a fair `diagonal`

interleaving.

`>>>`

[(1,'a'),(1,'b'),(1,'c'),(1,'d'),(2,'a'),(2,'b'),(2,'c'),(2,'d'),(3,'a'),(3,'b'),(3,'c'),(3,'d')]`enumerate $ finiteList [1..3] >< finiteList "abcd"`

`>>>`

[('a',0),('b',0),('c',0),('a',1),('b',1),('c',1),('a',2),('b',2),('c',2),('a',3)]`enumerate . takeE 10 $ finiteList "abc" >< nat`

`>>>`

[(0,'a'),(0,'b'),(0,'c'),(1,'a'),(1,'b'),(1,'c'),(2,'a'),(2,'b'),(2,'c'),(3,'a')]`enumerate . takeE 10 $ nat >< finiteList "abc"`

`>>>`

[(0,0),(0,1),(1,0),(0,2),(1,1),(2,0),(0,3),(1,2),(2,1),(3,0)]`enumerate . takeE 10 $ nat >< nat`

`>>>`

4`locate (nat >< nat) (1,1)`

`>>>`

3357`locate (nat >< nat) (36,45)`

Like (`<+>`

), this operation is also not associative (not even up
to reassociating tuples).

interleave :: IEnumeration (IEnumeration a) -> IEnumeration (Index, a) Source #

Fairly interleave a set of *infinite* enumerations.

For a finite set of infinite enumerations, a round-robin
interleaving is used. That is, if we think of an enumeration of
enumerations as a 2D matrix read off row-by-row, this corresponds
to taking the transpose of a matrix with finitely many infinite
rows, turning it into one with infinitely many finite rows. For
an infinite set of infinite enumerations, *i.e.* an infinite 2D
matrix, the resulting enumeration reads off the matrix by
`diagonal`

s.

Note that the type of this function is slightly different than
its counterpart in Data.Enumeration: each enumerated value in
the output is tagged with an index indicating which input
enumeration it came from. This is required to make the result
invertible, and is analogous to the way the output values of
`<+>`

are tagged with `Left`

or `Right`

; in fact, `interleave`

can be thought of as an iterated version of `<+>`

, but with a
more efficient implementation.

maybeOf :: IEnumeration a -> IEnumeration (Maybe a) Source #

Enumerate all possible values of type `Maybe a`, where the values
of type `a`

are taken from the given enumeration.

`>>>`

[Nothing,Just 1,Just 2,Just 3]`enumerate $ maybeOf (finiteList [1,2,3])`

`>>>`

3`locate (maybeOf (maybeOf (finiteList [1,2,3]))) (Just (Just 2))`

eitherOf :: IEnumeration a -> IEnumeration b -> IEnumeration (Either a b) Source #

listOf :: IEnumeration a -> IEnumeration [a] Source #

Enumerate all possible finite lists containing values from the given enumeration.

`>>>`

[[],[0],[0,0],[1],[0,0,0],[1,0],[2],[0,1],[1,0,0],[2,0],[3],[0,0,0,0],[1,1],[2,0,0],[3,0]]`enumerate . takeE 15 $ listOf nat`

`>>>`

666270815854068922513792635440014`locate (listOf nat) [3,4,20,5,19]`

finiteSubsetOf :: IEnumeration a -> IEnumeration [a] Source #

Enumerate all possible finite subsets of values from the given enumeration. The elements in each list will always occur in increasing order of their index in the given enumeration.

`>>>`

[[],[0],[1],[0,1],[2],[0,2],[1,2],[0,1,2]]`enumerate $ finiteSubsetOf (finite 3)`

`>>>`

332`locate (finiteSubsetOf nat) [2,3,6,8]`

`>>>`

True`332 == 2^8 + 2^6 + 2^3 + 2^2`

finiteEnumerationOf :: Int -> IEnumeration a -> IEnumeration (Enumeration a) Source #

`finiteEnumerationOf n a`

creates an enumeration of all sequences
of exactly n items taken from the enumeration `a`

.

`>>>`

[[0,0],[0,1],[0,2],[1,0],[1,1],[1,2],[2,0],[2,1],[2,2]]`map E.enumerate . enumerate $ finiteEnumerationOf 2 (finite 3)`

`>>>`

[[0,0,0],[0,0,1],[1,0,0],[0,1,0],[1,0,1],[2,0,0],[0,0,2],[1,1,0],[2,0,1],[3,0,0]]`map E.enumerate . take 10 . enumerate $ finiteEnumerationOf 3 nat`

functionOf :: IEnumeration a -> IEnumeration b -> IEnumeration (a -> b) Source #

`functionOf a b`

creates an enumeration of all functions taking
values from the enumeration `a`

and returning values from the
enumeration `b`

. As a precondition, `a`

must be finite;
otherwise `functionOf`

throws an error.

`>>>`

`bbs = functionOf (boundedEnum @Bool) (boundedEnum @Bool)`

`>>>`

Finite 4`card bbs`

`>>>`

[True,False]`map (select bbs 2) [False, True]`

`>>>`

2`locate bbs not`

`>>>`

5`locate (functionOf bbs (boundedEnum @Bool)) (\f -> f True)`

# Utilities

undiagonal :: (Integer, Integer) -> Integer Source #

The other half of the isomorphism between \(\mathbb{N}\) and \(\mathbb{N} \times \mathbb{N}\) which enumerates by diagonals: turn a pair of natural numbers giving a position in the 2D grid into the number in the cell, according to this numbering scheme:

0 1 3 6 ... 2 4 7 5 8 9