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
Alternative instances for
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
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
>>> 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
<|>, 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.