Reading the documentation on F#'s Option
type, it looks like it does behave pretty much exactly like the Maybe
type in Haskell, in that it can model either 'nothing' (None
in F#, Nothing
in Haskell), or a value of its argument type (Some
in F#, Just
in Haskell).
In Haskell, however, Maybe
is also a monad, and the plumbing is such that it allows for calculations on Maybe
values, early-returning Nothing
if any of the variables in the calculation is Nothing
. Used this way, Maybe
is a simple error handler (or rather, error-ignoring device), and the fact that it is a monad allows moving the boilerplate out of the way. Look at this wikipedia article for a nice concise example. I don't think Option
supports this kind of monadic usage (in fact, I'm wondering whether there is any explicit concept of a monad in F# at all). If you want this behavior in .NET, I guess you'd use Option.Value
for all your arguments, and wrap the whole calculation in a try / catch on NullReferenceException
.
So, while Option
is similar to the Maybe
type, it is not an equivalent to the Maybe
monad.
Views #1 and #2 are incorrect in general.
- Any data-type of kind
* -> *
can work as a label, monads are much more than that.
- (With the exception of the
IO
monad) computations within a monad are not impure. They simply represent computations that we perceive as having side effects, but they're pure.
Both these misunderstandings come from focusing on the IO
monad, which is actually a bit special.
I'll try to elaborate on #3 a bit, without getting into category theory if possible.
Standard computations
All computations in a functional programming language can be viewed as functions with a source type and a target type: f :: a -> b
. If a function has more than one argument, we can convert it to an one-argument function by currying (see also Haskell wiki). And if we have just a value x :: a
(a function with 0 arguments), we can convert it into a function that takes an argument of the unit type: (\_ -> x) :: () -> a
.
We can build more complex programs form simpler ones by composing such functions using the .
operator. For example, if we have f :: a -> b
and g :: b -> c
we get g . f :: a -> c
. Note that this works for our converted values too: If we have x :: a
and convert it into our representation, we get f . ((\_ -> x) :: () -> a) :: () -> b
.
This representation has some very important properties, namely:
- We have a very special function - the identity function
id :: a -> a
for each type a
. It is an identity element with respect to .
: f
is equal both to f . id
and to id . f
.
- The function composition operator
.
is associative.
Monadic computations
Suppose we want to select and work with some special category of computations, whose result contains something more than just the single return value. We don't want to specify what "something more" means, we want to keep things as general as possible. The most general way to represent "something more" is representing it as a type function - a type m
of kind * -> *
(i.e. it converts one type to another). So for each category of computations we want to work with, we'll have some type function m :: * -> *
. (In Haskell, m
is []
, IO
, Maybe
, etc.) And the category will contains all functions of types a -> m b
.
Now we would like to work with the functions in such a category in the same way as in the basic case. We want to be able to compose these functions, we want the composition to be associative, and we want to have an identity. We need:
- To have an operator (let's call it
<=<
) that composes functions f :: a -> m b
and g :: b -> m c
into something as g <=< f :: a -> m c
. And, it must be associative.
- To have some identity function for each type, let's call it
return
. We also want that f <=< return
is the same as f
and the same as return <=< f
.
Any m :: * -> *
for which we have such functions return
and <=<
is called a monad. It allows us to create complex computations from simpler ones, just as in the basic case, but now the types of return values are tranformed by m
.
(Actually, I slightly abused the term category here. In the category-theory sense we can call our construction a category only after we know it obeys these laws.)
Monads in Haskell
In Haskell (and other functional languages) we mostly work with values, not with functions of types () -> a
. So instead of defining <=<
for each monad, we define a function (>>=) :: m a -> (a -> m b) -> m b
. Such an alternative definition is equivalent, we can express >>=
using <=<
and vice versa (try as an exercise, or see the sources). The principle is less obvious now, but it remains the same: Our results are always of types m a
and we compose functions of types a -> m b
.
For each monad we create, we must not forget to check that return
and <=<
have the properties we required: associativity and left/right identity. Expressed using return
and >>=
they are called the monad laws.
An example - lists
If we choose m
to be []
, we get a category of functions of types a -> [b]
. Such functions represent non-deterministic computations, whose results could be one or more values, but also no values. This gives rise to the so-called list monad. The composition of f :: a -> [b]
and g :: b -> [c]
works as follows: g <=< f :: a -> [c]
means to compute all possible results of type [b]
, apply g
to each of them, and collect all the results in a single list. Expressed in Haskell
return :: a -> [a]
return x = [x]
(<=<) :: (b -> [c]) -> (a -> [b]) -> (a -> [c])
g (<=<) f = concat . map g . f
or using >>=
(>>=) :: [a] -> (a -> [b]) -> [b]
x >>= f = concat (map f x)
Note that in this example the return types were [a]
so it was possible that they didn't contain any value of type a
. Indeed, there is no such requirement for a monad that the return type should have such values. Some monads always have (like IO
or State
), but some don't, like []
or Maybe
.
The IO monad
As I mentioned, the IO
monad is somewhat special. A value of type IO a
means a value of type a
constructed by interacting with the program's environment. So (unlike all the other monads), we cannot describe a value of type IO a
using some pure construction. Here IO
is simply a tag or a label that distinguishes computations that interact with the environment. This is (the only case) where the views #1 and #2 are correct.
For the IO
monad:
- Composition of
f :: a -> IO b
and g :: b -> IO c
means: Compute f
that interacts with the environment, and then compute g
that uses the value and computes the result interacting with the environment.
return
just adds the IO
"tag" to the value (we simply "compute" the result by keeping the environment intact).
- The monad laws (associativity, identity) are guaranteed by the compiler.
Some notes:
- Since monadic computations always have the result type of
m a
, there is no way how to "escape" from the IO
monad. The meaning is: Once a computation interacts with the environment, you cannot construct a computation from it that doesn't.
- When a functional programmer doesn't know how to make something in a pure way, (s)he can (as the last resort) program the task by some stateful computation within the
IO
monad. This is why IO
is often called a programmer's sin bin.
- Notice that in an impure world (in the sense of functional programming) reading a value can change the environment too (like consume user's input). That's why functions like
getChar
must have a result type of IO something
.
Best Answer
Monads
A monad consists of
An endofunctor. In our software engineering world, we can say this corresponds to a datatype with a single, unrestricted type parameter. In C#, this would be something of the form:
Two operations defined over that datatype:
return
/pure
takes a "pure" value (i.e., aT
value) and "wraps" it into the monad (i.e., it produces anM<T>
value). Sincereturn
is a reserved keyword in C#, I'll usepure
to refer to this operation from now on. In C#,pure
would be a method with a signature like:bind
/flatmap
takes a monadic value (M<A>
) and a functionf
.f
takes a pure value and returns a monadic value (M<B>
). From these,bind
produces a new monadic value (M<B>
).bind
has the following C# signature:Also, to be a monad,
pure
andbind
are required to obey the three monad laws.Now, one way to model monads in C# would be to construct an interface:
(Note: In order to keep things brief and expressive, I'll be taking some liberties with the code throughout this answer.)
Now we can implement monads for concrete datagypes by implementing concrete implementations of
Monad<M>
. For instance, we might implement the following monad forIEnumerable
:(I'm purposefully using the LINQ syntax to call out the relationship between LINQ syntax and monads. But note we could replace the LINQ query with a call to
SelectMany
.)Now, can we define a monad for
IObservable
? It would seem so:To be sure we have a monad, we need to prove the monad laws. This can be non-trivial (and I'm not familiar enough with Rx.NET to know whether they can even be proved from the specification alone), but it's a promising start. To facilitate the remainder of this discussion, let's just assume the monad laws hold in this case.
Free Monads
There is no singular "free monad". Rather, free monads are a class of monads that are constructed from functors. That is, given a functor
F
, we can automatically derive a monad forF
(i.e., the free monad ofF
).Functors
Like monads, functors can be defined by the following three items:
Two operations:
pure
wraps a pure value into the functor. This is analogous topure
for a monad. In fact, for functors that are also a monads, the two should be identical.fmap
maps values in the input to new values in the output via a given function. It's signature is:Like monads, functors are required to obey the functor laws.
Similar to monads, we can model functors via the following interface:
Now, since monads are a sub-class of functors, we could also refactor
Monad
a bit:Here I've added an additional method,
join
, and provided default implementations of bothjoin
andbind
. Note, however, that these are circular definitions. So you'd have to override at least one or the other. Also, note thatpure
is now inherited fromFunctor
.IObservable
and Free MonadsNow, since we have defined a monad for
IObservable
and since monads are a sub-class of functors, it follows that we must be able to define a functor instance forIObservable
. Here's one definition:Now that we have a functor defined for
IObservable
, we can construct a free monad from that functor. And that is precisely howIObservable
relates to free monads — namely, that we can construct a free monad fromIObservable
.