Определение типа данных, который не требуется определять

Question

У меня есть тип данных Polynomial r для полиномов в Haskell и экземпляр Ring для него. (class Ring r where plus :: r -> r -> r ; times :: r -> r -> r ; negative :: r -> r ; zero :: r ; one :: r - это просто упрощенная версия Num).

Теперь я мог определить полином, такие как gauss = x^2 + 1 или eisenstein = x^2 + x + 1, а затем работать в «полиномиального Integer/(гс)» для гауссовых целых чисел или «полиномиальной Integer/(Эйзенштейн)» для целых чисел Эйзенштейна. В этом проблема, я написал ее в кавычках, потому что это не настоящий тип данных, и я не могу понять, как ее определить.

я первый попытался сделать что-то вроде data Quotient p = Quot p p, а затем, например, мы бы plus (Quot a i) (Quot b i') | i == i' = Quot (plus a b) i Конечно, это очень плохо, но уже это даже не представляется возможным определить one и zero. Поэтому я изменил его на data Quotient p = Quot p (Maybe p), и я думаю, что у меня есть рабочая реализация, но вы точно не знаете, будет ли работать plus (ему нужно хотя бы один Just, а если их два, то они должны быть одинаковыми).

Есть ли какой-либо тип безопасного (я имею в виду не использовать небезопасные функции) способ программирования этого в haskell? Я довольно тупой. Благодаря!

Answer 1

В статье implicit configurations (каббализированный here) используются коэффициенты Z; это должно быть просто, чтобы адаптировать его к кольцам полиномов (если только я чего-то не хватает).

Редактировать: Не говорят неявные конфигурации сами просты, далеко от него;) - просто модификация.

Answer 2

Возможно, вы могли бы увеличить свой полиномиальный тип с помощью индекса или тега? Если я правильно понимаю, ваш нормальный модуль будет что-то вроде:

data Poly r = Poly r 

class Ring r where 
    plus :: r -> r -> r 
    times :: r -> r -> r 

instance Ring (Poly Integer) where 
    plus (Poly x) (Poly y) = Poly (x + y) 
    times (Poly x) (Poly y) = Poly (x * y) 

gauss :: Poly Integer 
gauss = Poly 1 

eins :: Poly Integer 
eins = Poly 2 

И вы хотите, чтобы иметь возможность безопасно дифференциальному между двумя «подвидов» колец. Может быть, вы могли бы пометить их как так:

newtype PolyI i r = PolyI r 

instance Show r => Show (PolyI i r) where 
    show (PolyI p) = show p 

instance Ring (PolyI i Integer) where 
    plus (PolyI x) (PolyI y) = PolyI (x + y) 
    times (PolyI x) (PolyI y) = PolyI (x * y) 

Наши экземпляры кольца теперь требуют дополнительный тип-аргумент i, который мы можем создать, имея простые типы не-конструктор.

data Gauss 
data Eins 

Тогда мы просто создать конкретные полиномы с индексом в качестве аргумента:

gaussI :: PolyI Gauss Integer 
gaussI = PolyI 11 

einsI :: PolyI Eins Integer 
einsI = PolyI 20 

С Show экземпляра выше, мы получаем следующий вывод:

*Poly> plus einsI einsI 
40 

, а затем

*Poly> plus einsI gaussI 

Couldn't match expected type `Eins' with actual type `Gauss' 
Expected type: PolyI Eins Integer 
    Actual type: PolyI Gauss Integer 
In the second argument of `plus', namely `gaussI' 

Это что-то похожее на то, что вы искали?

Edit: после комментария к вопросу о newtype, я думаю, что это может также элегантное решение, если вы используете NewtypeDeriving, чтобы облегчить бремя повторно реализующего экземпляр Poly Integer. Я думаю, что в итоге это было бы похоже, если бы немного элегантнее этого подхода.