Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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".

like image 902
makelc Avatar asked Mar 15 '11 10:03

makelc


People also ask

What is the use of monad?

A monad is an algebraic structure in category theory, and in Haskell it is used to describe computations as sequences of steps, and to handle side effects such as state and IO. Monads are abstract, and they have many useful concrete instances. Monads provide a way to structure a program.

What problem do monads solve?

Conclusion. Monad is a simple and powerful design pattern for function composition that helps us to solve very common IT problems such as input/output, exception handling, parsing, concurrency and other.

Is a monad a data structure?

In functional programming, a monad is a software design pattern with a structure that combines program fragments (functions) and wraps their return values in a type with additional computation.

What do you know about the functor and monad?

A functor takes a pure function (and a functorial value) whereas a monad takes a Kleisli arrow, i.e. a function that returns a monad (and a monadic value). Hence you can chain two monads and the second monad can depend on the result of the previous one. You cannot do this with functors.


2 Answers

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.

like image 174
Cactus Avatar answered Oct 05 '22 00:10

Cactus


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.

like image 25
Edward Kmett Avatar answered Oct 05 '22 02:10

Edward Kmett