## Lightweight invertible enumerations in Haskell

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. 