Derivazione di istanze predefinite utilizzando GHC.Generics

Question

Ho una classe di caratteri Cyclic per cui vorrei essere in grado di fornire istanze generiche.

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

Dato un tipo somma di costruttori nullaria,

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

voglio generare un'istanza equivalente a questo:

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

Ho cercato di capire la richiesta Generic macchinari Così

{-# 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) 

Ora posso fornire implementazioni di default per Cyclic utilizzando GCyclic:

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 

ma i miei GCyclic casi non sono corretti. Utilizzando T3 dall'alto

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

E 'chiaro perché rot è equivalente a id qui. grot ricorre la struttura (:+:) di T3 finché non colpisce la base grot U1 = U1.

È stato suggerito il #haskell per utilizzare le informazioni del costruttore da M1 in modo che grot possa scegliere il prossimo costruttore da recitare, ma non sono sicuro di come farlo.

È possibile generare le istanze desiderate di Cyclic utilizzando GHC.Generics o qualche altra forma di Scrap Your Boilerplate?

EDIT: Hopotuto scrivere Cyclic utilizzando Bounded e 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) 

ma (come è) questo è insoddisfacente, in quanto richiede tutti Bounded, Enum e Eq. Inoltre, Enum non può essere derivato automaticamente da GHC in alcuni casi mentre il più robusto Generic può.

Answer 1

cura dopo aver riletto quello che ord dovrebbe significare, e di nuovo per cercare di affrontare il product of two cycles problem

Si può capire quando andare verso l'altro lato di una somma di costruttori, se si può dire che cosa è all'interno è già nell'ultimo costruttore, che è ciò che fanno le nuove funzioni end e gend. Non riesco ad immaginare un gruppo ciclico per il quale non possiamo definire end.

È possibile implementare gord per somme senza nemmeno esaminare i valori; l'estensione ScopedTypeVariables aiuta con questo. Ho modificato le firme per utilizzare i proxy, poiché ora stai mescolando undefined e provando a decostruire un valore nel codice.

import Data.Proxy 

Ecco la classe Cyclic con end, valori predefiniti, e (invece di assumere Int) per 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 

E la classe GCyclic e le sue implementazioni:

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())) 

posso t abbastanza forte che quanto segue sta facendo una lezione di equivalenza su mu altri sottogruppi ciclici del prodotto dei due cicli. A causa della necessità di rilevare le estremità per somme e il fatto che i calcoli per lcm e gcm non sono pigri, non possiamo più fare cose divertenti come derivare un'istanza ciclica per [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())) 

Qui ci sono alcuni più istanze esempio:

-- 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] 

e alcuni codice di esempio per l'esecuzione:

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 [] 

Il quarto e quinto esempi in mostra ciò che accade quando facciamo un esempio per il prodotto di due gruppi ciclici i cui ordini non sono coprimi.