Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Monads And Abstraction

Tags:

haskell

monads

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.

like image 713
CountOren Avatar asked Sep 10 '13 03:09

CountOren


2 Answers

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!

like image 87
danidiaz Avatar answered Oct 06 '22 04:10

danidiaz


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.

like image 30
Toxaris Avatar answered Oct 06 '22 03:10

Toxaris