Monads And Abstraction

Question

I am a newcomer to haskell, functional language and monads.
I have been messing around with this for around a month; I've read learn you a haskell and was playing around with snap trying to make my haskell web site .

But there is something that bothers me: the monads abstraction. If I understand correctly, monads are "containers of data" that can be sequenced. I can "unpack" it with ">>=" for example and more work will be done "behind the scenes" for me, so that if I don't have the monad definition I have to guess how it will be unpacked.

For example:

We have the list monad that unpacking it will sequence its element

[1,2,3] >>= return . (+1) -- gives back [2,3,4]

Or a more complex monad like the writer in those examples: Log Writer Monad

Or I might have a webWriter monad that for each 'unpacking' of its values, it will send a request to some remote server (I'm not sure about this one but I'm trying to give an extreme case)

My question is: Can I tell what the apply function ('>>=' , 'applyLog') is doing behind the scenes only by looking at the monad user interface (which I guess is the type definition)?

Hope I explained myself well.

Thanks, Oren.

Answer 1

While you can't know what (>>=) does for a particular monad just by looking at the interface, there are laws that every monad must respect in order to constitute a "proper" monad. And that constrains the possible implementations of return and (>>=). The monad laws are the following:

• Left identity: return a >>= f equal to f a
• Right identity: m >>= return equal to m
• Associativity: (m >>= f) >>= g equal to m >>= (\x -> f x >>= g)

For example, if return for the List monad were defined as \x -> [x,x] instead of \x -> [x], that would break the Left identity law. return 5 >>= \x -> [x+1] would be different from (\x -> [x+1]) 5.

Also, not all monads can be intuitively understood as 'containers' of some kind. The container analogy works for List and Maybe, but what about Reader, for example? A Reader value doesn't really 'contain' anything. Instead, it's a description of a computation that depends on an external unchanging environment.

Monad is anything that implements the monad interface and respects the monad laws.

Edit: As an example of how to intuit what the monad instance does for a given type, consider Data.Stream.Infinite.Stream from the streams package. Streams are like lists, only they are always infinite.

Stream has a Monad instance. What will return and (>>=) do in this case?

return has the type a -> Stream a. The only possible function with this type is the one that returns infinite repetitions of the value passed as a parameter.

(>>=) is more tricky. It has type Stream a -> (a -> Stream b) -> Stream b. One possible function with this type is the one that takes the head of the first argument and applies it to the second argument, returning the resulting stream. s >>= f = f $ head s.

Another possible implementation of (>>=) would be to apply the function of type a -> Stream b to every element of the original stream, getting an intermediate result of type Stream (Stream b), and then somehow collapse the stream of streams into a single Stream b value. How to do that? You can simply take the diagonal of the infinite square!

Which version of (>>=) is compatible with the monad laws? The first one certainly doesn't, because it breaks the right identiy. The result of 1,2,3,4... >>= return would be 1,1,1,1.... The second implementation respects the right identity (can you see why?) and that gives us more assurance that it may be the correct way to implement (>>=) for streams. Of course, you would need actual proof of all the laws to be sure!

Answer 2

I describe four sources of information you can use to learn about the behavior of >>= for specific monads.

The type of >>=

The type of >>= is always the same. It is specified in the Monad type class. See documentation. The type is:

(>>=) :: forall a b. m a -> (a -> m b) -> m b

Where m is a placeholder for the specific monad you are interested in. For example, for the list monad, the type of >>= is:

(>>=) :: forall a b. [a] -> (a -> [b]) -> [b]

Note that I just replaced m ... by [...].

The monad laws

The implementation of >>= is different for every monad, but all monads are supposed to keep to the monad laws. These laws are specified in the documentation of the Monad type class. See documentation again. The laws are:

1. return a >>= k == k a
2. m >>= return == m
3. m >>= (\x -> k x >>= h) == (m >>= k) >>= h

So whatever the implementation of some specific monad might be, you can use these laws to reason about your code. For example, if your code contains code like on the left-hand side of a law, you can replace that code by the corresponding right-hand side of the law, and the behavior should not change.

Here is an example for how to use a monad law. Assume I wrote this code:

foo = do
  x <- bar
  return x

We don't even know what monad is used here, but we know there's some monad, because we see the do notation. To apply the monad law, we have to desugar the do notation to calls of >>=:

foo = bar >>= (\x -> return x)

Note that \x -> return x is the same as just return (by η-reduction.

foo = bar >>= return

By the second monad law, this code means the exact same thing as just calling bar.

foo = bar

So it looks as if the >>= in the original foo function cannot do anything interesting at all, because the monad laws allow us to just leave it out. We figured that out without even knowing what specific monad supplies the >>= operator here.

The documentation of a specific monad

If you need to know more about the behavior of >>= for a specific monad, the documentation of the specific monad should tell you. You can use hoogle to search for the documentation. For example, the documentation of StateT tells you:

The return function leaves the state unchanged, while >>= uses the final state of the first computation as the initial state of the second.

The implementation of a specific monad

If you want to know more details about the implementation of a specific monad, you probably have to look at the actual implementation. Search for the instance Monad ... declaration. For example, look at the implementation of StateT. The implementation of the list monad is somewhere in this file, search for instance Monad [] or look at this except:

instance  Monad []  where
    m >>= k             = foldr ((++) . k) [] m
    m >> k              = foldr ((++) . (\ _ -> k)) [] m
    return x            = [x]
    fail _              = []

Maybe not the most obvious definition, but that's exactly what happens if you call >>= for the list monad.

Summary

All monads share the type signatures for >>= and return and the monad laws. Aparat from these constraints, every monad provides a different implementation of >>= and return, and if you want to know all the details, you'll have to study the source code of the instance Monad ... declaration. If you just want to learn how to use a specific monad, try finding some documentation about that.

Answer 3

A monad is not a "container of data". A monad is a higher order computation structure. The meaning of >>= can be better understood if instead you consider <=<.

f . g -- plain composition of functions

mf <=< mg -- composition of computations.

To my mind, this is more telling. However, <=< can be defined through >>=, so usually only >>= needs defining. You could also define >>= through <=<: m >>= f = (f <=< const m) ()

"m a" is not a data container. It only says that it implements "a"-like behaviour - so now we can compose only pieces of the right type together. (>>=) :: m a -> (a -> m b) -> m b tells us that because "m a" exposes "a"-like behaviour, we can join a function that uses "a"-like behaviour to turn into "b"-like behaviour.

How can it implement "a"-like behaviour for any type? Well, that's why we say it is a functor: it maps any function a->b into m a->m b - for every function a->b it finds (or builds) a function in such a way that if f and g compose, then m f and m g compose, too. This is a strong statement about preserving algebraic properties of the types a and b: if f adds 1, and g takes away 1, you get the same number; then m f composed with m g will also get you back to where you started - it may not have the number stored anywhere, but the behaviour will be "same number"-like.

Also, being a monad, means it concerns only with the higher-order structure, not the actual type: since "m a" can have any type a, it means the implementation cannot depend on the specifics of the type. The monad can only use the algebraic structure of the computation - in the broad meaning of "algebraic". For example, a list, [a], can have any elements, but the monad can only operate with the algebraic structure of the list - enumerate the elements, split the list, foldr, etc, but cannot, say, add up all elements - adding up is "a"-like. Other monads will have monad-specific functions, too; without them they may be quite useless - for example, ask, atomically, retry, etc.

Answer 4

Looking at just the type signature of a monad API is same as looking at the type signature of a function, like : a -> b -> c, which only tells you that given some things the function can give you something else. How the function does this is the implementation detail of the function.

Similarly the bind, return and other monad specific functions (like put,get in State monad) only gives you the idea what all mappings from one thing to another thing can be done using these functions. In case you need to understand the underlying logic of how the monad actually works, you either go through the documentation (if supplied) or the source code.

Answer 5

can i tell what the apply function ... is doing behind the scenes

There are lots of perfectly accurate answers to a question you didn't ask. Can you tell what a monad is doing from the context of its use? No, not in general.

You have to hope the name of the monad and its documentation (frequently very sparse I'm afraid) help, and that the surrounding code (frequently very terse) provides context for you.

Of course, if it's your code or a codebase you are familiar with then it's simple. However, most Haskell code does not seem to be optimised to be "skimmable".

Answer 6

That's an interesting question. I would say that you have a decent understanding of what monads can do. I would say that it is not possible to know the specific behavior of any function without reading the documentation. Each monad's bind and return are implemented specifically for the type's structure and purpose.

Answer 7

You can't tell exactly what return or >>= are going to do for a given monad by looking solely at their type signatures. That's because their type signatures will always be

return :: Monad m => a -> m a
(>>=)  :: Monad m => m a -> (a -> m b) -> m b

Très generic. Which is great at the type level, as it's an exact specification of what the functions do there.

At a finer resolution, you'll have to look at the monad instance declaration.