In a previous post I introduced a new Haskell library for enumerations (now on Hackage as simple-enumeration). The `Data.Enumeration`

module defines a type `Enumeration a`

, represented simply by a function `Integer -> a`

which picks out the value of type `a`

at a given index. This representation has a number of advantages, including the ability to quickly index into very large enumerations, and the convenience that comes from having `Functor`

, `Applicative`

, and `Alternative`

instances for `Enumeration`

.

I’ve just uploaded version 0.2 of the package, which adds a new `Data.Enumeration.Invertible`

module with a new type, `IEnumeration a`

, representing *invertible* enumerations. Whereas a normal enumeration is just a function from index to value, an invertible enumeration is a *bijection* between indices and values. In particular, alongside the `Integer -> a`

function for picking out the value at an index, an invertible enumeration also stores an inverse function `a -> Integer`

(called `locate`

) for finding the index of a given value.

On the one hand, this comes at a cost: because the type parameter `a`

now occurs both co- and contravariantly, `IEnumeration`

i s no longer an instance of `Functor`

, `Applicative`

, or `Alternative`

. There is a `mapE`

combinator provided for mapping `IEnumeration a`

to `IEnumeration b`

, but in order to work it needs both an `a -> b`

function *and* an inverse `b -> a`

.

On the other hand, we also gain something: of course the ability to look up the index of a value is nifty, and beyond that we also get a combinator

`functionOf :: IEnumeration a -> IEnumeration b -> IEnumeration (a -> b)`

which works as long as the `IEnumeration a`

is finite. This is not possible to implement with normal, non-invertible enumerations: we have to take an index and turn it into a function `a -> b`

, but that function has to take an `a`

as input and decide what to do with it. There’s nothing we can possibly do with a value of type `a`

unless we have a way to connect it back to the `IEnumeration a`

it came from.

Here’s a simple example of using the `functionOf`

combinator to enumerate all `Bool -> Bool`

functions, and then locating the index of `not`

:

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

And here’s an example of enumerating recursive trees, which is parallel to an example given in my previous post. Note, however, how we can no longer use combinators like `<$>`

, `<*>`

, and `<|>`

, but must explicitly use `<+>`

(disjoint sum of enumerations) and `><`

(enumeration product) in combination with `mapE`

. In return, though, we can find the index of any given tree in addition to selecting trees by index.

```
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)
trees :: IEnumeration Tree
trees = infinite $ mapE toTree fromTree (unit <+> (trees >< trees))
>>> locate trees (B (B L (B L L)) (B (B L (B L L)) (B L (B L L))))
123
>>> select trees 123
B (B L (B L L)) (B (B L (B L L)) (B L (B L L)))
```

Of course, the original `Data.Enumeration`

module remains available; there is clearly an inherent tradeoff to invertibility, and you are free to choose either style depending on your needs. Other than the tradeoffs outlined above and a couple other minor exceptions, the two modules export largely identical APIs.

Pingback: Resumen de lecturas compartidas durante julio de 2019 | Vestigium

Pingback: Competitive programming in Haskell: Enumeration | blog :: Brent -> [String]