Endofunction als Monoid

Question

Ich versuche, diese (zu Lernzwecken):

{-# LANGUAGE FlexibleInstances #-} 

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

id <> id gleich id . id

jedoch zu erwarten, mit (id <> id) 1 erhalte ich diesen Fehler:

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

Was sollte ich ändern, um es auszuführen?

Es ist einfach, Monoide und Haskell typeclasses besser zu verstehen, nicht für irgendeine praktische Verwendung.

Answer 1

Dies muss {-# OVERLAPPING #-} Pragma seit GHC.Base eine Instanz für Monoid (a -> b) hat, wenn b ein Monoid ist:

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

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

dann wird über Instanz für a -> a geltend gemacht werden, auch wenn a ein Monoid ist:

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

während bei Monoid b => a -> b die Instanz von GHC.Base wird aufgerufen werden:

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

Beachten Sie, dass Data.Monoidan exact same instance as yours for a -> a bereitstellt, aber die Überlappung wird unter Verwendung von newtype Endo a umgangen.

Answer 2

Die Haskell Category Klasse bietet Methoden, mit Kategorien zu arbeiten, deren Objekte genau die Haskell-Typen irgendeiner Art sind. Speziell

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

Die Namen der Methoden sollten sehr vertraut aussehen. Bemerkenswert ist,

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

Sie wissen wahrscheinlich, dass Monoide sind Halbgruppen mit Identitäten, ausgedrückt in Haskell mit

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

Aber einem anderen mathematischen Perspektive ist, dass sie Kategorien mit genau einem Objekt sind. Wenn wir ein Monoid haben, können wir leicht in eine Kategorie drehen:

-- 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) 

gehen in die andere Richtung ein wenig heikler ist. Eine Möglichkeit ist es, eine Art mit genau einem Typ auszuwählen und Kategorien anzusehen, deren einziges Objekt dieser Typ ist (bereiten Sie auf yucky-Code vor, den Sie überspringen können, wenn Sie möchten; das darunter liegende Bit ist weniger gruselig). Dies zeigt, dass wir zwischen einem Category, dessen Objekt vom Typ '() in der Art () ist, und einem Monoid frei umwandeln können. Die Pfeile der Kategorie werden die Elemente des 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) 

Aber das ist yucky! Ew! Und Dinge so fest zu verankern, führt normalerweise nicht dazu, etwas aus einer Perspektive zu machen. Aber wir können die Funktionalität ohne so viel Chaos bekommen, indem wir einen kleinen Trick spielen!

{-# 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) 

Statt sie auf ein Category die Begrenzung, die wirklich nur ein Objekt hat, wir sich einfach an ein Objekt zu einer Zeit, zu suchen beschränken.

Die vorhandene Monoid Instanz für Funktionen macht mich traurig. Ich denke, es wäre viel mehr natürliche eine Monoid Instanz für Funktionen auf ihre Category Instanz basiert zu verwenden, die Cat' Ansatz:

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

Da es bereits Monoid Instanz und überlappende Instanzen sind böse, wir haben mit einem newtype auskommen. Wir konnten nur

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

verwenden und dann schreiben

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

und für einige Zwecke vielleicht dies ist der Weg zu gehen, aber da wir ein newtype bereits verwenden wir könnten in der Regel auch die nicht fallen -Standard Gleichheit Kontext und Verwendung Data.Monoid.Endo, die diese Gleichheit in den Typ baut:

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

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