定义不想定义的数据类型

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然后在"多项式整数/(高斯)"中为高斯整数或"多项式整数/(爱森斯坦)"用于爱森斯坦整数.这就是问题,我在引号中写了它,因为它不是真正的数据类型,我无法弄清楚如何定义它.

我首先尝试做类似的事情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

也许你可以使用索引或标记来扩充多项式类型？如果我理解正确,你的正常模块将是这样的:

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)

我们的Ring实例现在需要一个额外的类型参数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'

这是你想要的东西吗？

编辑:在对问题的评论之后newtype,我认为如果你NewtypeDeriving用来减轻重新实现Poly Integer实例的负担,这也可能是一个优雅的解决方案.我认为最终会有类似的,如果比这种方法稍微优雅一点.

Answer 2

隐式配置论文（此处已简化）使用Z的商作为示例；将其适应多项式环应该很简单（除非我遗漏了一些东西）。

编辑：并不是说隐式配置本身很简单，远非如此;) - 只是修改。