Эндофункция как моноид

Для этого потребуется прагма {-# OVERLAPPING #-}, так как GHC.Base имеет экземпляр для Monoid (a -> b), когда 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 является моноидом:

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

тогда как с Monoid b => a -> b будет вызываться экземпляр из GHC.Base:

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

Обратите внимание, что Data.Monoid предоставляет точно такой же такой же, как ваш для a -> a, но здесь перекрытие обходится с помощью newtype Endo a.

Класс 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 для функций меня огорчает. Я думаю, что было бы гораздо более естественно использовать экземпляр 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)