Получение экземпляров по умолчанию с использованием GHC.Generics
У меня есть класс типов 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)
Теперь я могу предоставить реализацию по умолчанию для Cyclic с помощью 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
но мой GCyclic случаи неверны. С помощью T3 сверху
λ. map rot [A, B, C] -- == [B, C, A]
[A, B, C]
Понятно почему rot эквивалентно id Вот. grot рекурсы вниз (:+:) структура T3 пока он не достиг базового варианта grot U1 = U1,
Было предложено на #haskell использовать информацию конструктора из M1 так grot Я могу выбрать следующий конструктор, чтобы продолжить, но я не уверен, как это сделать.
Можно ли создать желаемые экземпляры Cyclic с помощью 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 а также Eq, Дополнительно, Enum не может быть автоматически получен GHC в некоторых случаях, тогда как более надежный Generic Можно.
1 ответ
Отредактировано после перечитывания что ord должен означать, и снова попытаться решить проблему произведения двух циклов
Вы можете выяснить, когда переходить на другую сторону суммы конструкторов, если вы можете сказать, что внутри уже находится последний конструктор, то есть то, что новый end а также gend функции делают. Я не могу представить циклическую группу, для которой мы не можем определить end,
Вы можете реализовать gord для сумм даже без проверки значений; ScopedTypeVariables расширение помогает в этом. Я изменил подписи для использования прокси, так как вы сейчас микшируете undefined и пытается деконструировать значение в вашем коде.
import Data.Proxy
Вот Cyclic класс с end, по умолчанию и Integral n (вместо того, чтобы предполагать 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 []
Четвертый и пятый примеры демонстрируют, что происходит, когда мы создаем экземпляр для произведения двух циклических групп, чьи порядки не взаимно просты.