How to use (->) instances of Monad and confusion about (->)

At different questions I've found hints in comments concerning using the (->) instance of Monads e.g. for realizing point-free style.

As for me, this is a little too abstract. Ok, I've seen Arrow instances on (->) and it seems to me, that (->) can be used in instance notations but not in type declarations (that would alone be stuff for another question).

Has anyone examples using (->) as instance of Monad? Or a good link?

Sorry if this question may already have been discussed here, but searching for "(->) Monad instance" gives you many many hits as you can imagine ... since nearly every question about Haskell somewhere involves (->) or "Monad".

Solution 1:

For a given type r, the function of type r -> a can be thought of as a computation delivering an a using an environment typed r. Given two functions r -> a and a -> (r -> b), it's easy to imagine that one can compose these when given an environment (again, of type r).

But wait! That's exactly what monads are about!

So we can create an instance of Monad for (->) r that implements f >>= g by passing the r to both f and g. This is what the Monad instance for (->) r does.

To actually access the environment, you can use id :: r -> r, which you can now think of as a computation running in an environment r and delivering an r. To create local sub-environments, you can use the following:

inLocalEnvironment :: (r -> r) -> (r -> a) -> (r -> a)
inLocalEnvironment xform f = \env -> f (xform env)

This pattern of having an environment passed to computations that can then query it and modify it locally is useful for not just the (->) r monad, which is why it is abstracted into the MonadReader class, using much more sensible names than what I've used here:

http://hackage.haskell.org/packages/archive/mtl/2.0.1.0/doc/html/Control-Monad-Reader-Class.html

Basically, it has two instances: (->) r that we've seen here, and ReaderT r m, which is just a newtype wrapper around r -> m a, so it's the same thing as the (->) r monad I've described here, except it delivers computations in some other, transformed monad.

Solution 2:

To define a monad for (->) r, we need two operations, return and (>>=), subject to three laws:

instance Monad ((->) r) where

If we look at the signature of return for (->) r

    return :: a -> r -> a

we can see its just the constant function, which ignores its second argument.

    return a r = a

Or alternately,

    return = const

To build (>>=), if we specialize its type signature with the monad (->) r,

    (>>=) :: (r -> a) -> (a -> r -> b) -> r -> b

there is really only one possible definition.

    (>>=) x y z = y (x z) z

Using this monad is like passing along an extra argument r to every function. You might use this for configuration, or to pass options way down deep into the bowels of your program.

We can check that it is a monad, by verifying the three monad laws:

1. return a >>= f = f a 

return a >>= f 
= (\b -> a) >>= f -- by definition of return
= (\x y z -> y (x z) z) (\b -> a) f -- by definition of (>>=)
= (\y z -> y ((\b -> a) z) z) f -- beta reduction
= (\z -> f ((\b -> a) z) z) -- beta reduction
= (\z -> f a z) -- beta reduction
= f a -- eta reduction

2. m >>= return = m

m >>= return
= (\x y z -> y (x z) z) m return -- definition of (>>=)
= (\y z -> y (m z) z) return -- beta reduction
= (\z -> return (m z) z) -- beta reduction
= (\z -> const (m z) z) -- definition of return
= (\z -> m z) -- definition of const
= m -- eta reduction

The final monad law:

3. (m >>= f) >>= g  ≡  m >>= (\x -> f x >>= g)

follows by similar, easy equational reasoning.

We can define a number of other classes for ((->) r) as well, such as Functor,

instance Functor ((->) r) where

and if we look at the signature of

   -- fmap :: (a -> b) -> (r -> a) -> r -> b

we can see that its just composition!

   fmap = (.)

Similarly we can make an instance of Applicative

instance Applicative ((->) r) where
   -- pure :: a -> r -> a
   pure = const

   -- (<*>) :: (r -> a -> b) -> (r -> a) -> r -> b
   (<*>) g f r = g r (f r)

What is nice about having these instances is they let you employ all of the Monad and Applicative combinators when manipulating functions.

There are plenty of instances of classes involving (->), for instance, you could hand-write the instance of Monoid for (b -> a), given a Monoid on a as:

enter code here
instance Monoid a => Monoid (b -> a) where
    -- mempty :: Monoid a => b -> a
    mempty _ = mempty
    -- mappend :: Monoid a => (b -> a) -> (b -> a) -> b -> a
    mappend f g b = f b `mappend` g b

but given the Monad/Applicative instance, you can also define this instance with

instance Monoid a => Monoid (r -> a) where
    mempty = pure mempty
    mappend = liftA2 mappend

using the Applicative instance for (->) r or with

instance Monoid a => Monoid (r -> a) where
    mempty = return mempty
    mappend = liftM2 mappend

using the Monad instance for (->) r.

Here the savings are minimal, but, for instance the @pl tool for generating point-free code, which is provided by lambdabot on the #haskell IRC channel abuses these instances quite a bit.