3

I'm trying this (for learning purposes):

{-# LANGUAGE FlexibleInstances #-}

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

expecting id <> id to be equal to id . id

However, with (id <> id) 1 I receive this error:

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

What should I change to run it?

It's just to understand monoids and Haskell typeclasses better, not for any practical usage.

3
  • I can't reproduce your error. A problem that's probably unrelated to yours is that there is already a standard Monoid b => Monoid (a->b) instance, which conflicts with yours. Please try it with a newtype wrapper, so you have a “clean slate”. (newtype Fun a b = Fun (a->b), that would be.) Jun 18, 2016 at 15:34
  • 1
    @leftaroundabout Probably better newtype Endo a = Endo (a -> a), like in Data.Monoid.
    – lisyarus
    Jun 18, 2016 at 16:14
  • @lisyarus in principle yes, but that would not quite reproduce the characteristics of an instance such as the OP's original proposed one. Jun 18, 2016 at 17:39

2 Answers 2

4

This will need {-# OVERLAPPING #-} pragma since GHC.Base has an instance for Monoid (a -> b) when b is a Monoid:

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

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

then, above instance will be invoked for a -> a, even if a is a Monoid:

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

whereas with Monoid b => a -> b the instance from GHC.Base will be invoked:

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

Note that Data.Monoid provides an exact same instance as yours for a -> a but there the overlap is bypassed using newtype Endo a.

4
  • Thanks. I was aware of Endo but was interested in that particular implementation because it works in Frege: github.com/Frege/frege/blob/… and I saw articles implying it should work in Haskell as well. Jun 18, 2016 at 16:21
  • 2
    No overlapping! No! Also, the existing instance makes me sad. I'd much rather have instance a ~ b => Monoid (a -> b), which precisely matches instance Category (->). The on version should clearly have a newtype wrapper.
    – dfeuer
    Jun 18, 2016 at 17:14
  • 1
    @dfeuer I'm afraid your response is obscure for casual reader (like me). Jun 20, 2016 at 7:18
  • @IvanKleshnin, I've expanded it into an answer.
    – dfeuer
    Jun 20, 2016 at 16:51
4

The Haskell Category class offers methods to work with categories whose objects are precisely the Haskell types of some kind. Specifically,

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

The names of the methods should look very familiar. Notably,

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

You probably know that monoids are semigroups with identities, expressed in Haskell using

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

But another mathematical perspective is that they're categories with exactly one object. If we have a monoid, we can easily turn it into a category:

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

Going the other way is a little bit trickier. One way to do it is to choose a kind with exactly one type, and look at categories whose sole object is that type (prepare for yucky code, which you can skip if you like; the bit below is less scary). This shows that we can freely convert between a Category whose object is the type '() in the () kind and a Monoid. The arrows of the category become the elements of the 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)

But this is yucky! Ew! And pinning things down so tightly doesn't usually accomplish anything from a practical perspective. But we can get the functionality without so much mess, by playing a little trick!

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

Instead of confining ourselves to a Category that really only has one object, we simply confine ourselves to looking at one object at a time.

The existing Monoid instance for functions makes me sad. I think it would be much more natural to use a Monoid instance for functions based on their Category instance, using the Cat' approach:

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

Since there's already a Monoid instance, and overlapping instances are evil, we have to make do with a newtype. We could just use

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

and then write

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

and for some purposes maybe this is the way to go, but since we're using a newtype already we usually might as well drop the non-standard equality context and use Data.Monoid.Endo, which builds that equality into the type:

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.