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.

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

Get the cardinality of an enumeration.

An index into an enumeration.

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

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.

Test whether an enumeration is finite.

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

>>> isFinite nat
False

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

The empty enumeration, with cardinality zero and no elements.

>>> card void
Finite 0

>>> enumerate void
[]

The unit enumeration, with a single value of () at index 0.

>>> card unit
Finite 1

>>> enumerate unit
[()]

>>> locate unit ()
0

An enumeration of a single given element at index 0.

>>> card (singleton 17)
Finite 1

>>> enumerate (singleton 17)
[17]

>>> locate (singleton 17) 17
0

A finite prefix of the natural numbers.

>>> card (finite 5)
Finite 5
>>> card (finite 1234567890987654321)
Finite 1234567890987654321

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

>>> locate (finite 5) 2
2

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.

>>> enumerate (finiteList [2,3,8,1])
[2,3,8,1]
>>> select (finiteList [2,3,8,1]) 2
8
>>> locate (finiteList [2,3,8,1]) 8
2

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).

Enumerate all the values of a bounded Enum instance.

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

>>> select (boundedEnum @Char) 97
'a'
>>> locate (boundedEnum @Char) 'Z'
90

>>> card (boundedEnum @Int)
Finite 18446744073709551616
>>> select (boundedEnum @Int) 0
-9223372036854775808

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

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

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

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

>>> enumerate . takeE 10 $ cw
[1 % 1,1 % 2,2 % 1,1 % 3,3 % 2,2 % 3,3 % 1,1 % 4,4 % 3,3 % 5]
>>> locate cw (3 % 2)
4
>>> locate cw (23 % 99)
3183

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

>>> enumerate . takeE 10 $ rat
[0 % 1,1 % 1,(-1) % 1,1 % 2,(-1) % 2,2 % 1,(-2) % 1,1 % 3,(-1) % 3,3 % 2]
>>> locate rat (-45 % 61)
2540

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.

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.

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

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

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

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

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.

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

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

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

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.

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

>>> cs = mapE (uncurry replicate) (length &&& head) (zipE (finiteList [1..10]) (dropE 35 (boundedEnum @Char)))
>>> enumerate cs
["#","$$","%%%","&&&&","'''''","((((((",")))))))","********","+++++++++",",,,,,,,,,,"]
>>> locate cs "********"
7

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:

>>> card trees
Infinite
>>> enumerate . takeE 3 $ trees
[L,B L L,B L (B L L)]
>>> select trees 87239862967296
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 123
B (B L (B L L)) (B (B L (B L L)) (B L (B L L)))
>>> locate trees (B (B L (B L L)) (B (B L (B L L)) (B L (B L L))))
123

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.

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

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

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

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

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.

>>> enumerate $ finiteList [1..3] >< finiteList "abcd"
[(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 . takeE 10 $ finiteList "abc" >< nat
[('a',0),('b',0),('c',0),('a',1),('b',1),('c',1),('a',2),('b',2),('c',2),('a',3)]

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

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

>>> locate (nat >< nat) (1,1)
4
>>> locate (nat >< nat) (36,45)
3357

Like (<+>), this operation is also not associative (not even up to reassociating tuples).

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 diagonals.

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.

Enumerate all possible values of type `Maybe a`, where the values of type a are taken from the given enumeration.

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

Enumerae all possible values of type Either a b with inner values taken from the given enumerations.

Note that for invertible enumerations, eitherOf is simply a synonym for <+>.

>>> enumerate . takeE 6 $ eitherOf nat nat
[Left 0,Right 0,Left 1,Right 1,Left 2,Right 2]

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

>>> enumerate . takeE 15 $ listOf nat
[[],[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]]
>>> locate (listOf nat) [3,4,20,5,19]
666270815854068922513792635440014

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.

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

>>> locate (finiteSubsetOf nat) [2,3,6,8]
332
>>> 332 == 2^8 + 2^6 + 2^3 + 2^2
True

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

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

>>> map E.enumerate . take 10 . enumerate $ finiteEnumerationOf 3 nat
[[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]]

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. There are two exceptions: first, if b has cardinality 1, we get an enumeration of exactly one function which constantly returns the one element of b, even if a is infinite. Second, if b has cardinality 0, we get a singleton enumeration if a also has cardinality 0, and an empty enumeration otherwise (even if a is infinite).

>>> bbs = functionOf (boundedEnum @Bool) (boundedEnum @Bool)
>>> card bbs
Finite 4
>>> map (select bbs 2) [False, True]
[True,False]
>>> locate bbs not
2

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

>>> n2u = functionOf nat unit
>>> card n2u
Finite 1
>>> (select n2u 0) 57
()

>>> n2o = functionOf nat void
>>> card n2o
Finite 0
>>> o2o = functionOf void void
>>> card o2o
Finite 1

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