Monads: Determining if an arbitrary transformation is possible

Question

There are quite a few of questions here about whether or not certain transformations of types that involve Monads are possible.

For instance, it's possible to make a function of type f :: Monad m => [m a] -> m [a], but impossible to make a function of type g :: Monad m => m [a] -> [m a] as a proper antifunction to the former. (IE: f . g = id)

I want to understand what rules one can use to determine if a function of that type can or cannot be constructed, and why these types cannot be constructed if they disobey these rules.

Answer 1

The way that I've always thought about monads is that a value of type Monad m => m a is some program of type m that executes and produces an a. The monad laws reinforce this notion by thinking of composition of these programs as "do thing one then do thing two", and produce some sort of combination of the results.

• Right unit Taking a program and just returning its value should be the same as just running the original program.

  m >>= return = m

• Left unit If you create a simple program that just returns a value, and then pass that value to a function that creates a new program, then the resulting program should just be as if you called the function on the value.

  return x >>= f = f x

• Associativity If you execute a program m, feed its result into a function f that produces another program, and then feed that result into a third function g that also produces a program, then this is identical to creating a new function that returns a program based on feeding the result of f into g, and feeding the result of m into it.

  (m >>= f) >>= g  =  m >>= (\x -> f x >>= g)

Using this intuition about a "program that creates a value" can come to some conclusions about what it means for the functions that you've provided in your examples.

1. Monad m => [m a] -> m [a] Deviating from the intuitive definition of what this function should do is hard: Execute each program in sequence and collect the results. This produces another program that produces a list of results.
2. Monad m => m [a] -> [m a] This doesn't really have a clear intuitive definition, since it's a program that produces a list. You can't create a list without getting access to the resulting values which in this case means executing a program. Certain monads, that have a clear way to extract a value from a program, and provide some variant of m a -> a, like the State monad, can have sane implementations of some function like this. It would have to be application specific though. Other monads, like IO, you cannot escape from.
3. Monad m => (a -> m b) -> m (a -> b) This also doesn't really have a clear intuitive definition. Here you have a function f that produces a program of type m b, but you're trying to return a function of type m (a -> b). Based on the a, f creates completely different programs with different executing semantics. You cannot encompass these variations in a single program of type m (a -> b), even if you can provide a proper mapping of a -> b in the programs resulting value.

This intuition doesn't really encompass the idea behind monads completely. For example, the monadic context of a list doesn't really behave like a program.

Answer 2

Something easy to remember is : "you can't escape from a Monad" (it's kind of design for it). Transforming m [a] to [m a] is a form of escape, so you can't.

On the other hand you can easily create a Monad from something (using return) so traversing ([m a] -> m [a]) is usually possible.