使用构造代数包定义代数模块

Question

包constructive-algebra允许您定义代数模块的实例(比如向量空间，但使用需要字段的环)。

这是我定义模块的尝试。

{-# LANGUAGE MultiParamTypeClasses, TypeSynonymInstances #-}
module A where
import Algebra.Structures.Module
import Algebra.Structures.CommutativeRing
import Algebra.Structures.Group

newtype A = A [(Integer,String)]

instance Group A where
    (A a) <+> (A b) = A $ a ++ b
    zero = A []
    neg (A a) = A $ [((-k),c) | (k,c) <-  a]


instance Module Integer A where
    r *> (A as) = A [(r <*> k,c) | (k,c) <- as]

它失败的原因是：

A.hs:15:10:
    Overlapping instances for Group A
      arising from the superclasses of an instance declaration
    Matching instances:
      instance Ring a => Group a -- Defined in Algebra.Structures.Group
      instance Group A -- Defined at A.hs:9:10-16
    In the instance declaration for `Module Integer A'

A.hs:15:10:
    No instance for (Ring A)
      arising from the superclasses of an instance declaration
    Possible fix: add an instance declaration for (Ring A)
    In the instance declaration for `Module Integer A'
Failed, modules loaded: none.

如果我将Group实例注释掉，那么：

A.hs:16:10:
    No instance for (Ring A)
      arising from the superclasses of an instance declaration
    Possible fix: add an instance declaration for (Ring A)
    In the instance declaration for `Module Integer A'
Failed, modules loaded: none.

我将此理解为要求Ring A的一个实例具有Module Integer A，这在类定义中是不合理的，也不是必需的：

class (CommutativeRing r, AbelianGroup m) => Module r m where
  -- | Scalar multiplication.
  (*>) :: r -> m -> m

你能解释一下吗？

Answer 1

包包含一个

instance Ring a => Group a where ...

实例头a匹配每个类型表达式，因此任何实例与任何其他类型表达式都将重叠。如果实际在某个地方使用这样的实例，则这种重叠只会导致错误。在您的模块中，使用

instance Module Integer A where
    r *> (A as) = A [(r <*> k,c) | (k,c) <- as]

Module类对m参数1具有一个AbelianGroup约束。这意味着一个Group约束。因此，对于这个实例，必须查找A的A实例。编译器找到两个匹配的实例。

这是第一个报告的错误。

第二个原因是编译器试图为AbelianGroup找到一个A实例。编译器当时唯一知道的实例是

instance (Group a, Ring a) => AbelianGroup a

因此，它试图找到instance Ring A where ...，但当然没有。

与其注释掉instance Group A where ...，不如添加一个

instance AbelianGroup a

(即使这是一个谎言，我们现在只想让它编译)并将OverlappingInstances添加到

{-# LANGUAGE #-}语用学

使用OverlappingInstances，将选择最具体的匹配实例，因此它可以在这里实现您想要的功能。

顺便说一句，您的A不是AbelianGroup的一个实例，除非顺序在[(Integer,String)]列表中不相关，否则就不可能是正确的。

Answer 2

这种类型检查没有讨厌的语言扩展。

{-# LANGUAGE MultiParamTypeClasses, TypeSynonymInstances #-}
module A where
import Algebra.Structures.Module
import Algebra.Structures.CommutativeRing
import Algebra.Structures.Group

newtype A = A [(Integer,String)]

instance Ring A where 
  A xs <+> A ys = A (xs ++ ys)
  neg (A a) = A $ [((-k),c) | (k,c) <-  a]
  A x <*> A y = A [b | a <- x, b <- y ]
  one = A []
  zero = A []

instance Module Integer A where
     r *> (A as) = A [(r <*> k,c) | (k,c) <- as] 

<+> <*>和neg是在Ring和Group中独立定义的，这有点让人困惑；它们是完全独立的符号，但是它们在一般的例子中结合在一起，使得所有的Rings Groups，所以如果定义了Ring，就不能定义Group，因为它已经被定义了。我不确定这是由类型类系统的工作方式强加给作者的。Module需要Ring或者更确切地说是CommutativeRing。CommutativeRing基本上只是重命名Ring；没有什么需要进一步定义的。它应该将你投入到Haskell中的东西中，一个不可校验的交换性断言。因此，在创建CommutativeRing实例之前，您应该在模块之外“证明Module定律”。但是，请注意，这些规则是用quickcheck命题表示的，因此您应该在专门针对这种类型的propMulComm和propCommutativeRing上运行quickcheck。

不知道如何处理1和0，但您可以通过使用适当的结构来克服关于顺序的问题，也许：

 import qualified Data.Set as S

 newtype B = B {getBs :: S.Set (Integer,String) }

但是有了新的类型，你也可以，例如，重新定义A上的Eq来理解它，我想。实际上，您必须运行quickcheck命题。

编辑:这是一个版本，其中添加了QuickCheck http://hpaste.org/68351所需的材料，以及"Failed“和"OK”quickcheck--用于不同Eq实例的语句。这个包在我看来是相当合理的；我认为如果你不想要环网和CommutativeRing业务，你应该重新定义模块，因为他说他“只考虑了交换的情况，就有可能实现左模块和右模块。”否则，您将无法使用quickcheck，这显然是包的主要要点，现在我看到了发生了什么，而且他已经使它变得非常容易了。事实上，A正是他试图通过使用quickcheck来排除的那种事情，在这种情况下，这肯定是很难捉弄的。