Определение модуля алгебры с использованием пакета конструктивной алгебры

Конструктивная алгебра пакета позволяет вам определять экземпляры алгебраических модулей (например, векторных пространств, но с использованием кольца, где требуется поле)

Это моя попытка определить модуль:

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

Не могли бы вы объяснить это?

2 ответа

Решение

Пакет содержит

instance Ring a => Group a where ...

Глава инстанции a соответствует каждому выражению типа, поэтому любой экземпляр с любым другим выражением типа будет перекрываться. Это перекрытие вызывает ошибку только в том случае, если такой экземпляр действительно где-то используется. В вашем модуле вы используете экземпляр в

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

Module класс имеет AbelianGroup ограничение на m parameter¹. Это подразумевает Group ограничение. Так что для этого случая Group экземпляр 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)] список.

Этот тип проверяет без противного расширения языка.

{-# 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; они являются совершенно отдельными символами, но затем они сводятся вместе в общем случае, который делает все RingsGroups, так что если Ring определено, Group не должно быть определено, так как это уже сказано. Я не уверен, что это навязывается автору из-за того, что работает система классов типов. Module требует Ring или скорее CommutativeRing, CommutativeRing просто в основном переименование Ring; дальше ничего не надо определять. Он должен связать вас с тем, что в Хаскеле является неопровержимым утверждением коммутативности. Таким образом, вы должны "доказать CommutativeRing законы ", так сказать, вне модуля, прежде чем делать Module пример. Однако обратите внимание, что эти законы выражены в предложениях по быстрой проверке, поэтому вы должны запустить propMulComm а также propCommutativeRing специализируется на этом типе.

Не знаю, что делать с единицей и нулем, но вы можете обойти пункт о заказе, используя подходящую структуру, может быть:

 import qualified Data.Set as S

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

Но имея новый тип, вы также можете, например, переопределить Eq на А, чтобы понять это, я полагаю. На самом деле вы должны выполнить предложения по быстрой проверке.


Редактировать: вот версия с добавленным материалом, необходимым для QuickCheck http://hpaste.org/68351 вместе с инструкциями quickcheck "Failed" и "OK" для разных экземпляров Eq. Этот пакет кажется довольно разумным для меня; Я думаю, что вам следует переопределить Module, если вы не хотите бизнеса Ring и CommulativeRing, поскольку он говорит, что "рассмотрите [s] только коммутативный случай, вместо этого можно будет реализовать левый и правый модули". В противном случае вы не сможете использовать QuickCheck, который, несомненно, является основным пунктом пакета, теперь, когда я вижу, что случилось, и что он сделал это невероятно легко сделать. Поскольку это А, это именно та вещь, которую он пытается исключить с помощью повсеместного использования быстрой проверки, которую, конечно, было бы очень трудно обмануть в подобном случае.

Другие вопросы по тегам