# Monads and Functors

The Monad class defines the basic operations over a monad, a concept from a branch of mathematics known as category theory. From the perspective of a Haskell programmer, however, it is best to think of a monad as an abstract datatype of actions. Haskell's do expressions provide a convenient syntax for writing monadic expressions.

## Monadic Classes

```haskell
class Functor f where
  fmap :: (a -> b) -> f a -> f b

class Monad m where
  (>>=)  :: m a -> (a -> m b) -> m b
  (>>)   :: m a -> m b -> m b
  return :: a -> m a
  fail   :: String -> m a
```

- `(>>=)` Sequentially compose two actions, passing any value produced by the first as an argument to the second.
- `(>>)` Sequentially compose two actions, discarding any value produced by the first, like sequencing operators (such as the semicolon) in imperative languages
- `(return)` Inject a value into the monadic type
- `(fail)` Fail with a message. This operation is not part of the mathematical definition of a monad, but is invoked on pattern-match failure in a do expression.

A minimal complete definition of the Monad class requires implementing `>>=` and `return`, since

```haskell
m >> k = m >>= \_ -> k
fail s = error s
```

## Monadic Laws

Instances of Functor should satisfy the following laws.

```haskell
fmap id  ==  id
fmap (f . g)  ==  fmap f . fmap g
```

Instances of Monad should satisfy the following laws.

```haskell
return a >>= k  ==  k a
m >>= return  ==  m
m >>= (\x -> k x >>= h)  ==  (m >>= k) >>= h
```

Instances of both 'Monad' and 'Functor' should additionally satisfy the law:

```haskell
fmap f xs  ==  xs >>= return . f
```

## Monad Instances

### Maybe

The `Maybe` type encapsulates an optional value. The `Maybe` type is a
simple kind of error monad where all of the errors are represented by
`Nothing`.

```haskell
data Maybe a = Nothing | Just a

maybe :: b -> (a -> b) -> Maybe a -> b
maybe n f Nothing  = n
maybe n f (Just x) = f x

instance Functor Maybe where
  fmap f Nothing  = Nothing
  fmap f (Just x) = Just (f x)

instance Monad Maybe where
  (Just x) >>= k = k x
  Nothing  >>= k = Nothing
  return         = Just
  fail s         = Nothing
```

### Lists

```haskell
-- not valid Haskell; for illustration only
data [a] = [] | a : [a]

instance Functor [] where
  fmap = map

instance Monad [] where
  m >>= k = concat (map k m)
  return x = [x]
  fail s = []
```

### IO

A value of type `IO a` is a computation which, when performed, does some
I/O before returning a value of type `a`.

The only way to perform an I/O action is to bind it to `Main.main` in
your program. It isn't possible to perform I/O from an arbitrary
function, unless that function is itself in the `IO` monad and called
directly or indirectly from `Main.main`.

```haskell
-- abstract
data IO a = ...

instance Functor IO where
  fmap f x = x >>= (return . f)

instance Monad IO where
  (>>=)  = ...
  return = ...
  fail s = ioError (userError s)

-- related functions
userError :: String  -> IOError
ioError   :: IOError -> IO a
catch     :: IO a    -> (IOError -> IO a) -> IO a
```

The two monadic binding functions, methods in the Monad class, are used
to compose a series of I/O operations. The `>>` function is used where
the result of the first operation is uninteresting, for example when it
is `()`. The `>>=` operation passes the result of the first operation as
an argument to the second operation.

As an example of IO usage, the following program reads in an input file, filters out
everything that isn't ascii, writes it to an output file, and prints a
message that it was successful.

```haskell
main = readFile "input-file"                      >>= \s ->
       writeFile "output-file" (filter isAscii s) >>
       putStrLn "Filtering successful"
```

In do notation, this reads

```haskell
main = do
        s <- readFile "input-file"
        writeFile "output-file" (filter isAscii s)
        putStrLn "Filtering successful"
```

## `do` notation

A *do expression* provides a more conventional syntax for monadic
programming. It allows an expression such as

```haskell
putStr "x: "     >>
getLine          >>= \l ->
return (words l)
```

to be written in a more traditional way as:

```haskell
do putStr "x: "
  l <- getLine
  return (words l)
```

It can also be written using semicolons as follows

```haskell
do { putStr "x: "; l <- getLine; return (words l) }
```

## Basic Monad Functions

`mapM f` is equivalent to `sequence . map f`
```haskell
mapM      :: Monad m => (a -> m b) -> [a] -> m [b]
```

`mapM_ f` is equivalent to `sequence_ . map f`
```haskell
mapM_     :: Monad m => (a -> m b) -> [a] -> m ()
```

`forM` is `mapM` with its arguments flipped
```haskell
forM      :: Monad m => [a] -> (a -> m b) -> m [b]
```

`forM_` is `mapM_` with its arguments flipped
```haskell
forM_     :: Monad m => [a] -> (a -> m b) -> m ()
```

Evaluate each action in the sequence from left to right, and collect the
results
```haskell
sequence  :: Monad m => [m a] -> m [a]
```

Evaluate each action in the sequence from left to right, and ignore the
results
```haskell
sequence_ :: Monad m => [m a] -> m ()
```

Same as `>>=`, but with the arguments interchanged
```haskell
(=<<)     :: Monad m => (a -> m b) -> m a -> m b
```

Left-to-right Kleisli composition of monads
```haskell
(>=>)     :: Monad m => (a -> m b) -> (b -> m c) -> a -> m c
```

Right-to-left Kleisli composition of monads. `(>=>)` with the arguments
flipped
```haskell
(<=<)     :: Monad m => (b -> m c) -> (a -> m b) -> a -> m c
```

`forever act` repeats the action indefinitiely
```haskell
forever   :: Monad m => m a -> m b
```

`void value` discards or ignores the result of evaluation, such as the
return value of an `IO` action
```haskell
void      :: Functor f => f a -> f ()
```