Endofunction as Monoid

Я пытаюсь это (в учебных целях):

{-# 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, а не для практического использования..

 lisyarus18 июн. 2016 г., 18:14
@leftaroundabout Наверное, лучшеnewtype Endo a = Endo (a -> a), как в Data.Monoid.
 leftaroundabout18 июн. 2016 г., 17:34
Я не могу воспроизвести вашу ошибку. Проблема, которая, вероятно, не связана с вашей, состоит в том, что уже существует стандартMonoid b => Monoid (a->b) экземпляр, который конфликтует с вашим. Пожалуйста, попробуйте это сnewtype обертка, так что у вас есть «чистый лист». (newtype Fun a b = Fun (a->b), это было бы.)
 leftaroundabout18 июн. 2016 г., 19:39
@lisyarus в принципе да, но это не совсем воспроизводит характеристики экземпляра, такие как оригинал, предложенный OP.

Ответы на вопрос(2)

Решение Вопроса

Это понадобится{-# 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.

 Ivan Kleshnin20 июн. 2016 г., 09:18
@ Dfeuer Боюсь, что ваш ответ неясен для случайного читателя (как я).
 dfeuer20 июн. 2016 г., 18:51
@IvanKleshnin, я расширил это в ответ.
 Ivan Kleshnin18 июн. 2016 г., 18:21
Благодарю. Я знал об Endo, но интересовался именно этой реализацией, потому что она работает во Фреге:github.com/Frege/frege/blob/... и я видел статьи, подразумевающие, что это должно работать и на Хаскеле.
 dfeuer18 июн. 2016 г., 19:14
Нет перекрытия! Нет! Кроме того, существующий экземпляр меня огорчает. Я бы предпочелinstance a ~ b => Monoid (a -> b), который точно соответствуетinstance Category (->),on версия должна иметь оболочку нового типа.

Хаскелл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)

Ваш ответ на вопрос