使用GHC.Generics推导默认实例

Question

我有一个类型类Cyclic我希望能够提供泛型实例。

class Cyclic g where 
    gen :: g 
    rot :: g -> g 
    ord :: g -> Int 

考虑之类无参构造函数，

data T3 = A | B | C deriving (Generic, Show) 

我要生成实例相当于这一个：

instance Cyclic T3 where 
    gen = A 
    rot A = B 
    rot B = C 
    rot C = A 
    ord _ = 3 

我试图找出所需Generic机械像这样

{-# LANGUAGE DefaultSignatures, FlexibleContexts, ScopedTypeVariables, TypeOperators #-} 

import GHC.Generics 

class GCyclic f where 
    ggen :: f a 
    grot :: f a -> f a 
    gord :: f a -> Int 

instance GCyclic U1 where 
    ggen = U1 
    grot _ = U1 
    gord _ = 1 

instance Cyclic c => GCyclic (K1 i c) where 
    ggen = K1 gen 
    grot (K1 a) = K1 (rot a) 
    gord (K1 a) = ord a 

instance GCyclic f => GCyclic (M1 i c f) where 
    ggen = M1 ggen 
    grot (M1 a) = M1 (grot a) 
    gord (M1 a) = gord a  

instance (GCyclic f, GCyclic g) => GCyclic (f :*: g) where 
    ggen = ggen :*: ggen 
    grot (a :*: b) = grot a :*: grot b 
    gord (a :*: b) = gord a `lcm` gord b 

instance (GCyclic f, GCyclic g) => GCyclic (f :+: g) where 
    ggen = L1 ggen 
    -- grot is incorrect 
    grot (L1 a) = L1 (grot a) 
    grot (R1 b) = R1 (grot b) 
    gord _ = gord (undefined :: f a) 
      + gord (undefined :: g b) 

现在

我可以使用GCyclicCyclic为提供默认的实现：

class Cyclic g where 
    gen :: g 
    rot :: g -> g 
    ord :: g -> Int 

    default gen :: (Generic g, GCyclic (Rep g)) => g 
    gen = to ggen 

    default rot :: (Generic g, GCyclic (Rep g)) => g -> g 
    rot = to . grot . from 

    default ord :: (Generic g, GCyclic (Rep g)) => g -> Int 
    ord = gord . from 

但我GCyclic情况下是不正确的。从上面

λ. map rot [A, B, C] -- == [B, C, A] 
[A, B, C] 

很清楚为什么rot相当于id这里使用T3。 grot向下递减结构T3，直到它遇到基础案例grot U1 = U1。

在#haskell上建议使用M1的构造函数信息，所以grot可以选择下一个构造函数进行递归，但我不确定如何执行此操作。

是否可以使用GHC.Generics或某种其他形式的Scrap Your Boilerplate生成所需的Cyclic实例？

编辑：我可以编写使用Bounded和Enum

class Cyclic g where 
    gen :: g 
    rot :: g -> g 
    ord :: g -> Int 

    default gen :: Bounded g => g 
    gen = minBound 

    default rot :: (Bounded g, Enum g, Eq g) => g -> g 
    rot g | g == maxBound = minBound 
      | otherwise  = succ g 

    default ord :: (Bounded g, Enum g) => g -> Int 
    ord g = 1 + fromEnum (maxBound `asTypeOf` g) 

，但（这是），这是不能令人满意的，因为它要求所有的Bounded，Enum和EqCyclic。此外，在某些情况下，Enum不能由GHC自动派生，而更稳健的Generic可以。

Answer 1

编辑重读什么ord的解释是：之后，再次尝试解决该product of two cycles problem

你可以计算出什么时候去构造的总和的另一边，如果你能告诉什么里面已经在最后一个构造函数中，这就是新的函数所做的功能end和gend。我无法想象我们无法定义的循环组end。

您可以实现gord作为总和而不需要检查值; ScopedTypeVariables扩展有助于此。我已经更改签名以使用代理，因为您现在正在混合undefined并试图解构代码中的值。

import Data.Proxy 

这里是Cyclic类end，默认值和（而不是假设Int）为ord

class Cyclic g where 
    gen :: g 
    rot :: g -> g 
    end :: g -> Bool 
    ord :: Integral n => Proxy g -> n 

    default gen :: (Generic g, GCyclic (Rep g)) => g 
    gen = to ggen 

    default rot :: (Generic g, GCyclic (Rep g)) => g -> g 
    rot = to . grot . from 

    default end :: (Generic g, GCyclic (Rep g)) => g -> Bool 
    end = gend . from 

    default ord :: (Generic g, GCyclic (Rep g), Integral n) => Proxy g -> n 
    ord = gord . fmap from 

而且GCyclic类和它的实现：

class GCyclic f where 
    ggen :: f a 
    gend :: f a -> Bool 
    grot :: f a -> f a 
    gord :: Integral n => Proxy (f()) -> n 

instance GCyclic U1 where 
    ggen = U1 
    grot _ = U1 
    gend _ = True 
    gord _ = 1 

instance Cyclic c => GCyclic (K1 i c) where 
    ggen  = K1 gen 
    grot (K1 a) = K1 (rot a) 
    gend (K1 a) = end a 
    gord _  = ord (Proxy :: Proxy c) 

instance GCyclic f => GCyclic (M1 i c f) where 
    ggen  = M1 ggen 
    grot (M1 a) = M1 (grot a) 
    gend (M1 a) = gend a 
    gord _  = gord (Proxy :: Proxy (f())) 

我可以没有足够的压力，以下是使等价类超过亩这两个周期的乘积的一个循环子群。由于需要检测和的结尾，并且面对lcm和gcm的计算不是懒惰的，所以我们不能再像[a]那样做一些有趣的事情，例如派生循环实例。

-- The product of two cyclic groups is a cyclic group iff their orders are coprime, so this shouldn't really work 
instance (GCyclic f, GCyclic g) => GCyclic (f :*: g) where 
    ggen   = ggen       :*: ggen 
    grot (a :*: b) = grot a      :*: grot b 
    gend (a :*: b) = gend a      && (any gend . take (gord (Proxy :: Proxy (f())) `gcd` gord (Proxy :: Proxy (g()))) . iterate grot) b 
    gord _  = gord (Proxy :: Proxy (f())) `lcm` gord (Proxy :: Proxy (g())) 

instance (GCyclic f, GCyclic g) => GCyclic (f :+: g) where 
    ggen  = L1 ggen 
    grot (L1 a) = if gend a 
        then R1 (ggen) 
        else L1 (grot a) 
    grot (R1 b) = if gend b 
        then L1 (ggen) 
        else R1 (grot b) 
    gend (L1 _) = False 
    gend (R1 b) = gend b 
    gord _  = gord (Proxy :: Proxy (f())) + gord (Proxy :: Proxy (g())) 

下面是一些例子实例：

-- Perfectly fine instances 
instance Cyclic() 
instance Cyclic Bool 
instance (Cyclic a, Cyclic b) => Cyclic (Either a b) 

-- Not actually possible (the product of two arbitrary cycles is a cyclic group iff they are coprime) 
instance (Cyclic a, Cyclic b) => Cyclic (a, b) 

-- Doesn't have a finite order, doesn't seem to be a prime transfinite number. 
-- instance (Cyclic a) => Cyclic [a] 

而且一些示例代码来运行：

typeOf :: a -> Proxy a 
typeOf _ = Proxy 

generate :: (Cyclic g) => Proxy g -> [g] 
generate _ = go gen 
    where 
     go g = if end g 
       then [g] 
       else g : go (rot g) 

main = do 
    print . generate . typeOf $ A 
    print . map rot . generate . typeOf $ A 
    putStrLn [] 

    print . generate $ (Proxy :: Proxy (Either T3 Bool)) 
    print . map rot . generate $ (Proxy :: Proxy (Either T3 Bool)) 
    putStrLn [] 

    print . generate . typeOf $ (A, False) 
    print . map rot . generate . typeOf $ (A, False) 
    putStrLn [] 

    print . generate . typeOf $ (False, False) 
    print . map rot . generate . typeOf $ (False, False) 
    print . take 4 . iterate rot $ (False, True) 
    putStrLn [] 

    print . generate $ (Proxy :: Proxy (Either() (Bool, Bool))) 
    print . map rot . generate $ (Proxy :: Proxy (Either() (Bool, Bool))) 
    print . take 8 . iterate rot $ (Right (False,True) :: Either() (Bool, Bool)) 
    putStrLn [] 

第四个和第五个例子展示发生了什么事，当我们做一个实例订单不互质的两个循环组的乘积。