Endofunction作为幺半群

Question

我正在尝试这个（仅用于学习）：

{-# LANGUAGE FlexibleInstances #-}

instance Monoid (a -> a) where
  mempty = id
  mappend f g = f . g

期望id <> id等于id . id

然而，使用(id <> id) 1会收到以下错误：

Non type-variable argument in the constraint: Monoid (a -> a)

我应该改变什么来使它运行？

这只是为了更好地理解幺半群和Haskell类型类，而不是为了任何实际用途。

- Ivan Kleshnin

---

我无法重现你的错误。可能与你的问题无关的一个问题是，已经存在一个标准的 Monoid b => Monoid (a->b) 实例，这会与你的实例产生冲突。请尝试使用 newtype 包装器，这样你就有了一个“干净的状态”。(newtype Fun a b = Fun (a->b), 就是这个意思。) - leftaroundabout

@leftaroundabout 可能更好的是 newtype Endo a = Endo (a -> a)，就像在 Data.Monoid 中一样。 - lisyarus

@lisyarus 原则上是可以的，但这并不能完全复制 OP 最初提出的实例的特征。 - leftaroundabout

Answer 1

因为GHC.Base有Monoid (a -> b)实例（其中b是一个Monoid），所以这将需要{-# OVERLAPPING #-}编译指令：

{-# LANGUAGE FlexibleInstances #-}
import Data.Monoid (Monoid, mempty, mappend, (<>))

instance {-# OVERLAPPING #-} Monoid (a -> a) where
    mempty = id
    mappend f g = f . g

那么，即使 a 是一个 Monoid，在上述实例中也将为 a -> a 调用。

\> (id <> id) 1
1
\> (id <> id) [1]
[1]

如果使用 Monoid b => a -> b，将会调用 GHC.Base 中的实例：

\> ((:[]) <> (:[])) 1
[1,1]

注意，Data.Monoid 提供了与您的实例完全相同的实例，用于 a -> a，但在那里，重叠部分使用newtype Endo a进行绕过。

- behzad.nouri

---

谢谢。我知道Endo，但对这个特定的实现很感兴趣，因为它在Frege中起作用：https://github.com/Frege/frege/blob/c1260d53b388e1712f7fbdcda0b5f2cc8b24d4d9/frege/data/Monoid.fr#L90-L92，并且我看到有文章暗示它也应该在Haskell中起作用。 - Ivan Kleshnin

不要重叠！绝对不能！而且，现有的实例让我感到难过。我更喜欢 instance a ~ b => Monoid (a -> b)，它与 instance Category (->) 完全匹配。on 版本应该明确地有一个新类型包装器。 - dfeuer

@dfeuer，恐怕您的回复对于像我这样的普通读者来说有些晦涩。 - Ivan Kleshnin

@IvanKleshnin，我已经将其扩展为一个答案。 - dfeuer

Answer 2

Haskell的Category类提供了一些方法，用于处理对象为某种Haskell类型的范畴。具体而言，

class Category c where
  id :: c x x
  (.) :: c y z -> c x y -> c x z

方法的名称应该非常熟悉。特别是，

instance Category (->) where
  id x = x
  f . g = \x -> f (g x)

您可能知道，单子是具有身份识别的半群，在Haskell中使用表达

class Monoid a where
  mappend :: a -> a -> a
  mempty :: a

但是另一个数学角度认为它们是具有一个对象的类别。如果我们有一个幺半群，我们可以轻松地将其转化为一个类别：

-- We don't really need this extension, but
-- invoking it will make the code below more useful.
{-# LANGUAGE PolyKinds #-}

import Control.Category
import Data.Monoid
import Prelude hiding ((.), id)

newtype Mon m a b = Mon m

instance Monoid m => Category (Mon m) where
  id = Mon mempty
  Mon x . Mon y = Mon (x `mappend` y)

走另一条路有点棘手。一种方法是选择一个只有一个类型的种类，并查看其唯一对象为该类型的类别（如果您愿意，可以跳过难看的代码位）。这表明我们可以自由地在() 种类中将对象类型 '() 的 Category 和一个 Monoid 之间进行转换。类别的箭头成为幺半群的元素。

{-# LANGUAGE DataKinds, GADTs, PolyKinds #-}

data Cat (c :: () -> () -> *) where
  Cat :: c '() '() -> Cat c
instance Category c => Monoid (Cat c) where
  mempty = Cat id
  Cat f `mappend` Cat g = Cat (f . g)

但这太糟糕了！呃！而且过于紧密地固定东西通常从实际角度来看也没有什么作用。但是我们可以通过玩一个小把戏来获得功能，而不会弄得一团糟！

{-# LANGUAGE GADTs, PolyKinds #-} 

import Control.Category
import Data.Monoid
import Prelude hiding ((.), id)

newtype Cat' (c :: k -> k -> *) (a :: k) (b :: k) = Cat' (c a b)

instance (a ~ b, Category c) => Monoid (Cat' c a b) where
  mempty = Cat' id
  Cat' f `mappend` Cat' g = Cat' (f . g)

与其局限在仅有一个对象的Category中，我们可以只看一次性地看一个对象。

对于函数而言，现有的Monoid实例让我感到难过。我认为基于它们的Category实例使用Cat'方法创建函数的Monoid实例会更加自然：

instance a ~ b => Monoid (a -> b) where
  mempty = id
  mappend = (.)

既然已经有了一个Monoid实例，并且重叠实例很危险，我们必须使用newtype。 我们可以直接使用。

newtype Morph a b = Morph {appMorph :: a -> b}

然后编写代码

instance a ~ b => Monoid (Morph a b) where
  mempty = Morph id
  Morph f `mappend` Morph g = Morph (f . g)

对于某些目的来说，这可能是可行的方式，但由于我们已经在使用newtype，通常最好放弃非标准的等式上下文，并使用Data.Monoid.Endo，该类型内置了相等性：

newtype Endo a = Endo {appEndo :: a -> a}

instance Monoid (Endo a) where
  mempty = Endo id
  Endo f `mappend` Endo g = Endo (f . g)

- dfeuer