Is it possible to re-embed "Enum" output using GHC generics

Question

Is it possible to Enum type class output using GHC generics?

At first it looks simple:

 data Foo -- representation without metadata (wrong): = Foo -- L1 U1 | Bar -- R1 (L1 U1) | Baz -- R1 (R1 (L1 U1)) | Quux -- R1 (R1 (R1 U1)) deriving (Show, Eq, Generic) -- Rep Foo p = (U1 :+: (U1 :+: (U1 :+: U1))) p instance Enum Foo where toEnum = undefined -- FIXME fromEnum = gfromEnum . from class GEnum f where gfromEnum :: fp -> Int instance GEnum U1 where gfromEnum U1 = 0 instance GEnum f => GEnum (M1 itf) where gfromEnum (M1 x) = gfromEnum x instance (GEnum x, GEnum y) => GEnum (x :+: y) where gfromEnum (L1 x) = gfromEnum x gfromEnum (R1 y) = 1 + gfromEnum y 

However, this will not work:

 λ> fromEnum Foo 0 λ> fromEnum Bar 1 λ> fromEnum Baz 1 λ> fromEnum Quux 2 

This is because we cannot rely on how the arguments are grouped together (:+:) . In In this case, it seems that they are nested as follows:

 ((U1 :+: U1) :+: (U1 :+: U1)) p 

So, is it possible to get Enum with Generics ? If so, how?

Answer 1

GHC infuses Generic in such a way that variants L and R form a tree in which the leaves are in Enum order. Consider the following example (with cropped output):

 ghci> data D = A | B | C | D | E deriving (Generic) ghci> from A L1 (L1 U1) ghci> from B L1 (R1 U1) ghci> from C R1 (L1 U1) ghci> from D R1 (R1 (L1 U1)) ghci> from E R1 (R1 (R1 U1))) 

Note that if you placed them as a tree, toEnum `map` [1..] will be the left and right leaf toEnum `map` [1..] . With this intuition, we start by defining the GLeaves class, which counts the number of leaves that have a common type (not value!) In its tree.

 {-# LANGUAGE ScopedTypeVariables, PolyKinds, TypeApplications, TypeOperators, DefaultSignatures, FlexibleContexts, TypeFamilies #-} import GHC.Generics import Data.Proxy class GLeaves f where -- | Counts the number of "leaves" (ie U1's) in the type `f` gSize :: Proxy f -> Int instance GLeaves U1 where gSize _ = 1 instance GLeaves x => GLeaves (M1 itx) where gSize _ = gSize (Proxy :: Proxy x) instance (GLeaves x, GLeaves y) => GLeaves (x :+: y) where gSize _ = gSize (Proxy :: Proxy x) + gSize (Proxy :: Proxy y) 

Now we have a form for defining GEnum . As usual in this setup, we define our Enum' class and have default signatures that rely on GEnum .

 class Enum' a where toEnum' :: Int -> a fromEnum' :: a -> Int default toEnum' :: (Generic a, GEnum (Rep a)) => Int -> a toEnum' = to . gToEnum default fromEnum' :: (Generic a, GEnum (Rep a)) => a -> Int fromEnum' = gFromEnum . from class GEnum f where gFromEnum :: fp -> Int gToEnum :: Int -> fp 

Finally, we get to the good. For U1 and M1 , gFromEnum and gToEnum are simple. For :+: gFromEnum needs to find all the leaves to the left of it, so if this is the correct subtree, we add the size of the left subtree (and if it is the left subtree, we do not add anything). Similarly, gToEnum checks to see if it belongs in the left or right subtree, checking if it is less than the number of leaves in the left subtree.

 instance GEnum U1 where gFromEnum U1 = 0 gToEnum n = if n == 0 then U1 else error "Outside enumeration range" instance GEnum f => GEnum (M1 itf) where gFromEnum (M1 x) = gFromEnum x gToEnum n = M1 (gToEnum n) instance (GLeaves x, GEnum x, GEnum y) => GEnum (x :+: y) where gFromEnum (L1 x) = gFromEnum x gFromEnum (R1 y) = gSize (Proxy :: Proxy x) + gFromEnum y gToEnum n = let s = gSize (Proxy :: Proxy x) in if n < s then L1 (gToEnum n) else R1 (gToEnum (n - s)) 

Finally, you can check this out in GHCi:

 ghci> :set -XDeriveAnyClass -XDeriveGeneric ghci> data D = A | B | C | D | E deriving (Show, Generic, Enum, Enum') ghci> toEnum `map` [0 .. 4] :: [D] [A,B,C,D,E] ghci> toEnum' `map` [0 .. 4] :: [D] [A,B,C,D,E] ghci> fromEnum `map` [A .. E] :: [Int] [A,B,C,D,E] ghci> fromEnum' `map` [A .. E] :: [Int] [A,B,C,D,E] 

Performance

You may think to yourself: this is super inefficient! As a result, we recount a bunch of sizes over and over again - the worst performance is at least O(n^2) . The trick (hopefully) is that the GHC will be able to optimize / implement the hell out of our specific Enum' instances until there is nothing left of the Generic initial structure.

Answer 2

Enum is one of many examples that are slightly inconvenient for writing using the standard G6C Generics view because most data types remain implicit (for example, how nested and data constructors are nested and where metadata occurs).

With generics-sop, you can (re) define common Enum instances in a slightly more straightforward way:

 {-# LANGUAGE ConstraintKinds, DataKinds, DeriveGeneric #-} {-# LANGUAGE FlexibleContexts, GADTs, PolyKinds #-} {-# LANGUAGE TypeApplications, TypeOperators #-} import Generics.SOP import qualified GHC.Generics as GHC 

We define a synonym for a type that captures what it means to be an enumerated type:

 type IsEnumType a = All ((~) '[]) (Code a) 

(Unfortunately, the (~) '[] construct triggers an error in GHC 8.0.1, but works fine in GHC 8.0.2.) In generics-sop, data type code is a list of type lists. An external list contains an element for each constructor; internal lists contain types of arguments to the constructor. The IsEnumType says that all internal lists must be empty, which means that none of the constructors should have any arguments.

 gfromEnum :: (Generic a, IsEnumType a) => a -> Int gfromEnum = conIndex . unSOP . from where conIndex :: NS f xs -> Int conIndex (Z _) = 0 conIndex (S i) = 1 + conIndex i 

The from function turns the value into a representation of the total output, and unSOP breaks the external constructor. Then we have a sum structure to go through. The NS data type, representing n-ary sums, has constructors Z and S that indicate which constructor is used, so we can just move around and count.

 gtoEnum :: (Generic a, IsEnumType a) => Int -> a gtoEnum i = to (SOP (apInjs_NP (hcpure (Proxy @ ((~) '[])) Nil) !! i)) 

Here the call to apInjs_NP (hcpure ...) creates representations of empty design applications for all data type constructors. Unlike the gfromEnum function gfromEnum this actually uses the IsEnumType constraint for the correct input (since we rely on none of the constructors to accept any arguments). Then we selected the i -th constructor from the list and return it from the general view to the actual type, applying SOP first and then to .

To apply it to your sample type, you must create it for both the GHC classes and the generic-sop Generic class (or you can also use TH to do this):

 data Foo = Foo | Bar | Baz | Quux deriving (Show, Eq, GHC.Generic) instance Generic Foo 

Then you can check it out:

 GHCi> gfromEnum Baz 2 GHCi> gtoEnum 2 :: Foo Baz 

If you want, you can make gfromEnum and gtoEnum default definitions for a class like Enum, like in G6C Generics.