What kind of data structure is a monad?

Question

I have a half-competent understanding of what a monad is (a parameterized type that provides a context for useful computation building), why it exists (so you can do things that require context, like IO), how to use it (bind returned variables with >>=), and a very rough understanding of where it fits in in category theory (a category that guarantees homogeneity of contexts of functions)**.

What, however, is a monad in terms of the underlying data structure? Since it is related to an applicative functor (which seems like a list), my guess is that GHC takes the monad's contents and puts them into a linked list of some sort, and passes them around throughout the computation.

What is really going on underneath the hood?

** feel free to correct any of this if you know better.

• Will Ness: "contents" does not necessarily imply a box, it can be a transmission carrying a signal. Not just burritos, rum-soaked cakes are monads too. and holograms.
• dfeuer: @WillNess, where do you live and can you teach me to make rum-soaked cakes?

Answer 1

Monad is not a data structure — it's a property.

You can define a class of data types that have some default values (like [] for lists, 0 for Int, False for Bool and so on). Let's call this class Defaultable. Then you postulate that the default integer is 0 and thus prove that the type of integers is Defaultable. Bool is Defaultable in the same way.

Another example is the ToStringable class (Show in Haskell): A type is ToStringable if there is a function from it to String. Int and Bool are ToStringable, because you can write functions

intToString :: Int -> String
boolToString :: Bool -> String

(and lists of type [a] are meaningfully ToStringable if a is ToStringable)

Likewise, the type of lists is a monad: you can define two operations (that obey certain laws) return and (>>=) and thus prove that the type of lists forms a monad. And that is: if you can define two operations

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

for some concrete m, then this m is a monad. So Monad is a class and classes very much remind interfaces in OOP.

Internally it's just dictionaries passing.

Answer 2

A monad may or may not be a data structure. To get some data-structural intuition into monads, you should definitely read Dan Piponi's blog post Monads are Trees with Grafting.

The most boring data structural monad is the free monad over a functor,

data Free f a = Pure a
 | Free (f (Free a))
instance Functor f => Monad (Free f) where ...

Since you mention lists, you should probably look into the operational monad and perhaps the codensity monad.