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.

Answer 3

If you take a look at "Monad laws", monad only constrain you to define a composition function but not reverse function.

In the first example you can compose the list elements. In the second one Monad m => m [a] -> [m a], you cannot split an action into multiple actions ( action composition is not reversible).

Example:

Let's say you have to read 2 values.

s1 <- action
s2 <- action

Doing so, action result s2 depends by the side effect made by s1. You can bind these 2 actions in 1 action to be executed in the same order, but you cannot split them and execute action from s2 without s1 made the side effect needed by the second one.

Answer 4

Not really an answer, and much too informal for my linking, but nevertheless I have a few interesting observations that won't fit into a comment. First, let's consider this function you refer to:

f :: Monad m => [m a] -> m [a]

This signature is in fact stronger than it needs to be. The current generalization of this is the sequenceA function from Data.Traversable:

sequenceA :: (Traversable t, Applicative f) -> t (f a) -> f (t a)

...which doesn't need the full power of Monad, and can work with any Traversable and not just lists.

Second: the fact that Traversable only requires Applicative is I think really significant to this question, because applicative computations have a "list-like" structure. Every applicative computation can be rewritten to have the form f <$> a1 <*> ... <*> an for some f. Or, informally, every applicative computation can be seen as a list of actions a1, ... an (heterogeneous on the result type, homogeneous in the functor type), plus an n-place function to combine their results.

If we look at sequenceA through this lens, all it does is choose an f built out of the appropriate nested number of list constructors:

sequenceA [a1, ..., an] == f <$> a1 <*> ... <*> an
    where f v1 ... vn = v1 : ... : vn : []

Now, I haven't had the chance to try and prove this yet, but my conjectures would be the following:

1. Mathematically speaking at least, sequenceA has a left inverse in free applicative functors. If you have a Functor f => [FreeA f a] and you sequenceA it, what you get is a list-like structure that contains those computations and a combining function that makes a list out of their results. I suspect however that it's not possible to write such a function in Haskell (unSequenceFreeA :: (Traversable t, Functor f) => FreeA f (t a) -> Maybe (t (Free f a))), because you can't pattern match on the structure of the combining function in the FreeA to tell that it's of the form f v1 ... vn = v1 : ... : vn : [].
2. sequenceA doesn't have a right inverse in a free applicative, however, because the combining function that produces a list out of the results from the a1, ... an actions may do anything; for example, return a constant list of arbitrary length (unrelated to the computations that the free applicative value performs).
3. Once you move to non-free applicative functors, there will no longer be a left inverse for sequenceA, because the non-free applicative functor's equations translate into cases where you can no longer tell apart which of two t (f a) "action lists" was the source for a given f (t a) "list-producing action."