Unlike a Functor, a Monad can change shape?

Question

I've always enjoyed the following intuitive explanation of a monad's power relative to a functor: a monad can change shape; a functor cannot.

For example: length $ fmap f [1,2,3] always equals 3.

With a monad, however, length $ [1,2,3] >>= g will often not equal 3. For example, if g is defined as:

g :: (Num a) => a -> [a]
g x = if x==2 then [] else [x]

then [1,2,3] >>= g is equal to [1,3].

The thing that troubles me slightly, is the type signature of g. It seems impossible to define a function which changes the shape of the input, with a generic monadic type such as:

h :: (Monad m, Num a) => a -> m a

The MonadPlus or MonadZero type classes have relevant zero elements, to use instead of [], but now we have something more than a monad.

Am I correct? If so, is there a way to express this subtlety to a newcomer to Haskell. I'd like to make my beloved "monads can change shape" phrase, just a touch more honest; if need be.

Answer 1

I've always enjoyed the following intuitive explanation of a monad's power relative to a functor: a monad can change shape; a functor cannot.

You're missing a bit of subtlety here, by the way. For the sake of terminology, I'll divide a Functor in the Haskell sense into three parts: The parametric component determined by the type parameter and operated on by fmap, the unchanging parts such as the tuple constructor in State, and the "shape" as anything else, such as choices between constructors (e.g., Nothing vs. Just) or parts involving other type parameters (e.g., the environment in Reader).

A Functor alone is limited to mapping functions over the parametric portion, of course.

A Monad can create new "shapes" based on the values of the parametric portion, which allows much more than just changing shapes. Duplicating every element in a list or dropping the first five elements would change the shape, but filtering a list requires inspecting the elements.

This is essentially how Applicative fits between them--it allows you to combine the shapes and parametric values of two Functors independently, without letting the latter influence the former.

Am I correct? If so, is there a way to express this subtlety to a newcomer to Haskell. I'd like to make my beloved "monads can change shape" phrase, just a touch more honest; if need be.

Perhaps the subtlety you're looking for here is that you're not really "changing" anything. Nothing in a Monad lets you explicitly mess with the shape. What it lets you do is create new shapes based on each parametric value, and have those new shapes recombined into a new composite shape.

Thus, you'll always be limited by the available ways to create shapes. With a completely generic Monad all you have is return, which by definition creates whatever shape is necessary such that (>>= return) is the identity function. The definition of a Monad tells you what you can do, given certain kinds of functions; it doesn't provide those functions for you.

• Rotsor: But you can do things like sequence, right? I'd say that's definitely "changing" the structure.
• C. A. McCann: @Rotsor: Not really. sequence just combines existing structures the same way (>>=) does, but does it by mashing together a whole list of things. It can't do anything that isn't in the list you apply it to.
• Rotsor: Well, yes, it changes the structure in a limited way -- by combining the existing shapes, but it satisfies the requirement: it has a generic type and does change the shapes. I've posted another example as my own answer.

Answer 2

Monad's operations can "change the shape" of values to the extent that the >>= function replaces leaf nodes in the "tree" that is the original value with a new substructure derived from the node's value (for a suitably general notion of "tree" - in the list case, the "tree" is associative).

In your list example what is happening is that each number (leaf) is being replaced by the new list that results when g is applied to that number. The overall structure of the original list still can be seen if you know what you're looking for; the results of g are still there in order, they've just been smashed together so you can't tell where one ends and the next begins unless you already know.

A more enlightening point of view may be to consider fmap and join instead of >>=. Together with return, either way gives an equivalent definition of a monad. In the fmap/join view, though, what is happening here is more clear. Continuing with your list example, first g is fmapped over the list yielding [[1],[],[3]]. Then that list is joined, which for list is just concat.

• mokus: If you're curious, the equivalence is shown by: join = (>>= id), fmap f = (>>= return . f), and f >>= x = join (fmap f x)
• user2023370: Yes indeed, I am strongly in favour of defining monads using join instead of (>>=).
• Erik Kaplun: @mokus: great answer! but I'm pretty sure you meant x >>= f = join (fmap f x).

Answer 3

Just because the monad pattern includes some particular instances that allow shape changes doesn't mean every instance can have shape changes. For example, there is only one "shape" available in the Identity monad:

newtype Identity a = Identity a
instance Monad Identity where
 return = Identity
 Identity a >>= f = f a

In fact, it's not clear to me that very many monads have meaningful "shape"s: for example, what does shape mean in the State, Reader, Writer, ST, STM, or IO monads?

• user2023370: True, and understood, but I personally find this concept of shape, and "monads as containers", very useful; and can even help inform laypersons. The generic details can be addressed later.
• C. A. McCann: The term "shape" here is basically synonymous with "state" or "effects"--the parts of the Functor that are neither parametric nor constant. The idea is meaningful but the terms used are less than ideal.
• Matt Fenwick: @user643722 it sounds like you've fallen prey to the monad burrito fallacy. It's great that it helps you understand monads, but may actually make it harder for others to understand them.

Answer 4

The key combinator for monads is (>>=). Knowing that it composes two monadic values and reading its type signature, the power of monads becomes more apparent:

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

The future action can depend entirely on the outcome of the first action, because it is a function of its result. This power comes at a price though: Functions in Haskell are entirely opaque, so there is no way for you to get any information about a composed action without actually running it. As a side note, this is where arrows come in.

• Zhen: I see a tricky question, because we get [a] types everywhere, but there are different types, I mean: g could be expressed as g :: (Num a, Num b) => a -> [b] and then you have (>>= g) :: (Num a, Num b) => [a] -> [b]

Answer 5

A function with a signature like h indeed cannot do many interesting things beyond performing some arithmetic on its argument. So, you have the correct intuition there.

However, it might help to look at commonly used libraries for functions with similar signatures. You'll find that the most generic ones, as you'd expect, perform generic monad operations like return, liftM, or join. Also, when you use liftM or fmap to lift an ordinary function into a monadic function, you typically wind up with a similarly generic signature, and this is quite convenient for integrating pure functions with monadic code.

In order to use the structure that a particular monad offers, you inevitably need to use some knowledge about the specific monad you're in to build new and interesting computations in that monad. Consider the state monad, (s -> (a, s)). Without knowing that type, we can't write get = \s -> (s, s), but without being able to access the state, there's not much point to being in the monad.

Answer 6

The simplest type of a function satisfying the requirement I can imagine is this:

enigma :: Monad m => m () -> m ()

One can implement it in one of the following ways:

enigma1 m = m -- not changing the shape
enigma2 _ = return () -- changing the shape

This was a very simple change -- enigma2 just discards the shape and replaces it with the trivial one. Another kind of generic change is combining two shapes together:

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

The result of foo can have shape different from both a and b.

A third obvious change of shape, requiring the full power of the monad, is a

join :: Monad m => m (m a) -> m a
join x = x >>= id

The shape of join x is usually not the same as of x itself.

Combining those primitive changes of shape, one can derive non-trivial things like sequence, foldM and alike.

• user2023370: I don't see it. With join, we're restricted to monads of monads. Similarly, your enigma variations seem to expect a monad parameterised by the unit type - and produce the same.
• Rotsor: user643722, do you mean the functions are not as general as you like? They abstract over m, so they work for any monad. Isn't that enough?
• Erik Kaplun: @Rotsor: did you not mean foo :: Monad m => m a -> m a -> m a?

Answer 7

Does

h :: (Monad m, Num a) => a -> m a
h 0 = fail "Failed."
h a = return a

suit your needs? For example,

> [0,1,2,3] >>= h
[1,2,3]

• user2023370: Interesting, but I'd class fail along with mzero: outside of the formal definition of a monad.
• augustss: Yes, fail does not belong in Monad.

Answer 8

This isn't a full answer, but I have a few things to say about your question that don't really fit into a comment.

Firstly, Monad and Functor are typeclasses; they classify types. So it is odd to say that "a monad can change shape; a functor cannot." I believe what you are trying to talk about is a "Monadic value" or perhaps a "monadic action": a value whose type is m a for some Monad m of kind * -> * and some other type of kind *. I'm not entirely sure what to call Functor f :: f a, I suppose I'd call it a "value in a functor", though that's not the best description of, say, IO String (IO is a functor).

Secondly, note that all Monads are necessarily Functors (fmap = liftM), so I'd say the difference you observe is between fmap and >>=, or even between f and g, rather than between Monad and Functor.

• user2023370: I am aware of the points you raise. I tried to keep the language of the question informal, though I may have overstepped the mark. As mentioned by others, neither does any thing change shape; after all we are using Haskell :)