作为幺半群的内函数

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类型类，不用于任何实际用途。

Answer 1

当 b 是 Monoid 时需要 {-# OVERLAPPING #-} pragma since GHC.Base has an instance for Monoid (a -> b):

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

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

然后，上面的实例将被调用 a -> a，即使 a 是一个 Monoid:

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

而对于 Monoid b => a -> b，来自 GHC.Base 的实例将被调用：

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

请注意 Data.Monoid 提供 an exact same instance as yours for a -> a but there the overlap is bypassed using newtype Endo a。

Answer 2

Haskell Category class 提供了处理对象恰好是某种 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 函数实例让我很难过。我认为使用 natural 将 Monoid 实例用于基于 Category 实例的函数，使用 Cat' 方法：

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)

作为幺半群的内函数

Endofunction as Monoid

haskell

monoids