Связь между классами Semigroupoid и Semigroup

На прошлой неделе я пытался понять некоторые из «основных» типов и классов типов Haskell (но в общей сложности изучаю Haskell не более двух недель) и обнаружил кое-что, что меня беспокоит:

  • «Полугруппоид» - это обобщение «Категории», означающее, что любая Категория тривиально является Полугруппоидом, просто игнорируя ее собственную идентичность и определяя

o = (.)

  • также «Полугруппа» является обобщением «Моноида» в том же смысле, что и выше: нужно просто игнорировать пустоту и определять

(<>) = mappend

Одни только эти два факта и идея о том, что как Полугруппоиды, так и Полугруппы имеют только понятие комбинирования элементов (полугруппоидная композиция против полугруппового умножения), и как Категория, так и Моноид также имеют понятие «единства» (идентичность против единичного элемента), приводят к помните, что отношения между полугруппоидами и полугруппами, а также между категориями и моноидами можно выразить следующим образом:

import Prelude hiding (id, (.))

import Data.Semigroupoid
import Data.Semigroup

import Control.Category
import Data.Monoid

instance Semigroupoid c => Semigroup (c a a) where
    (<>) = o

instance Category c => Monoid (c a a) where
    mempty = id
    mappend = (.)

main = putStrLn "Does not type-check!"

Я не уверен, почему это не компилируется; компилятор ghc говорит:

All instance types must be of the form (T a1 ... an)
where a1 ... an are *distinct type variables*,
and each type variable appears at most once in the instance head.

но бывает, что в том числе

{-# LANGUAGE FlexibleInstances #-}

поверх файла все исправляет.

Выраженные выше отношения не кажутся встроенными в библиотеки, в то время как отношения между Semigroupoid и Category, а также между Semigroup и Monoid встроены.

Есть ли для этого какая-то конкретная причина, и я просто скучаю по ней?

Может быть, это как-то связано с загадочными «FlexibleInstances»?

Приветствуется любое понимание.


haskell monoids category-theory semigroup category-abstractions
person LorenzoPerticone    schedule 26.02.2017    source источник

Ответы (1)


arrow_upward
2
arrow_downward

Если бы это потребовалось только FlexibleInstances, никто бы не стал возражать (это расширение совершенно безвредно), но, к сожалению, это также приводит к тому, что требуется очень безобидное другое расширение, как только вы добавляете достаточно интересные другие экземпляры. А именно,

{-# LANGUAGE FlexibleInstances #-}

import Control.Category (Category)

instance Category c => Monoid (c a a)

data Nontrivial s q = Nontrivial {
      someLabel :: String
    , someValues :: [(s, Int)]
    , otherValues :: Maybe (String, q)
    , moreStuff :: ({-...-})
    }

instance (Monoid s, Monoid q) => Monoid (Nontrivial s q) where
  mempty = Nontrivial "" [] Nothing ()

main = case mempty :: Nontrivial String String of
  Nontrivial _ _ _ _ -> return ()

не компилируется:

$ runhaskell  wtmpf-file6064.hs 

wtmpf-file6064.hs:17:13:
    Overlapping instances for Monoid (Nontrivial String String)
      arising from a use of ‘mempty’
    Matching instances:
      instance Category c => Monoid (c a a)
        -- Defined at wtmpf-file6064.hs:5:10
      instance (Monoid s, Monoid q) => Monoid (Nontrivial s q)
        -- Defined at wtmpf-file6064.hs:14:10
    In the expression: mempty :: Nontrivial String String
    In the expression:
      case mempty :: Nontrivial String String of {
        Nontrivial _ _ _ _ -> return () }
    In an equation for ‘main’:
        main
          = case mempty :: Nontrivial String String of {
              Nontrivial _ _ _ _ -> return () }

Теперь вы можете заставить его работать, добавив {-# OVERLAPPABLE #-} Pragmas, но это довольно неудобное занятие, которое может привести к странному поведению. Таких случаев категорически избегают.

person leftaroundabout    schedule 26.02.2017
comment
Я не уверен, что понимаю, почему это происходит: конечно (в общем) Nontrivial - это не категория, но я хочу сказать, что любая категория автоматически превращается в моноид, тогда как Nontrivial - это моноид, когда параметры его типа тоже. Поскольку Nontrivial не является категорией, я не понимаю, на что жалуется ghc. - person LorenzoPerticone; 26.02.2017
comment
Вы знаете, что Nontrivial не является категорией. Компилятор не может этого знать; фактически любой мог сделать его категорией, определив позже instance Category Nontrivial сироту. Что, конечно, верно, это не могло быть правильно сформированным, потому что оба параметра s и q на самом деле ковариантны, но требование контравариантности первого параметра не является законом, класс Category явно упоминается в форме, понятной компилятору, так на каком основании предполагается отклонить возможность этого экземпляра? - person leftaroundabout; 26.02.2017