Function Types as Monoid Instances

Question

I have a function that looks like this

transition :: State -> ([State], [State])

Given the particular domain of my problem, I know how to chain together two successive transition function calls, something like this:

transition `chain` trainsition ... `chain` transition

However, I would like to express this as a Monoid and perform chaining with <> and mappend. Unfortunately, I cannot seem to get the following, or similar variants of, to work:

instance Monoid (State -> ([State], [State])) where
    mempty  = ...
    mappend = ...

The error returned is as follows:

• Illegal instance declaration for
    ‘Monoid (State -> ([State], [State]))’
    (All instance types must be of the form (T a1 ... an)
     where a1 ... an are *distinct type variables*,
     and each type variable appears at most once in the instance head.
     Use FlexibleInstances if you want to disable this.)
• In the instance declaration for
    ‘Monoid (State -> ([State], [State]))’

In general, how can functions be expressed as instances of Monoid?

Answer 1

Functions are already instances of monoids in a different way. How do you expect Haskell to decide to use that instance or your instance? The usual way of solving your problem is to declare a newtype wrapper such as

newtype Transition a = Transition { runTransition :: a -> ([a], [a]) }

Then, you can make your monoid instance just fine:

instance Monoid (Transition a) where
  mempty  = ...
  mappend = ...

After you are done this, you can may even find foldMap useful. Instead of writing something like

runTransition (Transition  transition `chain`
               Transition  transition `chain`
               ...
               Transition  transition)

You can use foldMap

runTransition (foldMap Transition [transition, transition, ... transition])