Haskell: A First Step Into Monads

The biggest nightmare for most people learning Haskell is monads. Monads are the
key to how you can implement IO, state, parallelism, and sequencing (among numerous other things) in Haskell. The trick is wrapping your head around them.

On the most basic level, they're actually pretty easy to understand. Think about something like IO in purely functional terms. When you write a function that performs an IO action, what are you really
doing in terms of functions? For the moment, ignore all practical concerns, and just think in the
pure abstract: what happens when you do an output operation?

What happens is that you write some data to some entity accessible to the program. In purely
functional terms, you can think of taking a snapshot of the entire state of stuff accessible to the program both before and after the output action. Then the output operation is a function
from the state before to the state after. In pseudocode:

data StateOfEverything = ...

print :: String -> StateOfEverything -> StateOfEverything

Now, suppose you want to perform two IO actions in sequence - like printing "Hello world" by printing "Hello" and then printing "world". What's going on there?

What's going on is that you're chaining functions together, so that the state which
is the output of one function is the input to another.

printHelloWorld stateBefore =
    let stateAfter = print "Hello" stateBefore
    in print " World" stateAfter

Writing things that way - passing the state returned from one statement as a parameter to
the next one - is a pain. It's messy, hard to read, and generally unpleasant. So why not just
do an abstraction? Just write a combinator, for chaining together calls. (A
combinator is a function which takes other functions as parameters for the purpose of combining or modifying them in some way.)

chain :: (x -> x) -> (x -> x) -> x -> x
chain firstfun secondfun initstate =
    let nextState = firstfun initstate
    in secondfun nextstate

printHello stateBefore =
    print "Hello" stateBefore

printWorld stateBefore =
    print " World" stateBefore

printHelloWorld stateBefore =
    printHello `chain` printWorld

That's pretty much what a monad does. There's a bit more to it - the combinator needs to behave
in certain ways - but the central concept is that the monad is a kind of combinator that enables
sequential chaining with the transfer of an internal state object between steps. Haskell also
provides some nice syntax in the form of "do" expressions and a ton of flexibility in
terms of monad parameters - but the most basic thing going on in monad code is that basic chaining of
a state parameter from call to call in a sequence.

Now, let's look at doing what I just did with "chain", only do it using the Haskell IO monad:

>printHello ::  IO ()
>printHello  = print "Hello "
>
>printWorld ::  IO ()
>printWorld = print "World"
>
>printHelloWorld ::  IO ()
>printHelloWorld  = do
>                      printHello 
>                      printWorld

As you can see, there's a monad type IO, which is an object encapsulating
the IO state. You can't see inside of it - the IO state itself is completely hidden, and
inaccessible to any code outside of the implementation of the IO monad. But what it does is combine
functions so that the IO state returned by one operation is passed on to the next in sequence. It's really just like the chaining operator - but with a really nice syntax, and a lot more flexibility.

To see why it's more flexible, let's start by breaking down the "do" syntax, and see what's really going on. The do statement in the code example above is equivalent to the following:

>printHelloWorldWithoutDo :: IO ()
>printHelloWorldWithoutDo = printHello >>= (\ x -> printWorld)

One of the things that the "do" syntax does is expand each expression after the
first in the do so that the result value of each expression is passed as a parameter to the next. So
in addition to just passing the IO state internally, it also allows the programmer to pass their own
value from one element of the sequence to the next. To see just how flexible that is, let's take a
moment, and look at the actually type of ">>=".

*Main> :type (>>=)
(>>=) :: (Monad m) => m a -> (a -> m b) -> m b

Let's piece that apart. First, monads are type-parametric - meaning that, for example, "IO" isn't a type; "IO x" is a type - an instance value of the IO monad carrying a payload value of type x.

The monadic sequencing parameter takes two parameters. The first is a monad value with a payload of type "a". The second is a function which can be chained with the first - so it needs to take a parameter value who type is the type of the payload carried over from the first - so it's a function from a value of type "a" to another monad value - but it doesn't need to return the
same type as the first - it doesn't need to return an instance of IO a. It can return whatever type of payload it wants - so the type of the second parameter is a function from a value of type a, to a monad carrying a value of type b.

What this means is that there's a huge amount of flexibility in how we can pass values
between steps of a monad! My naive chain operator required everything in a sequence to take and return values of exactly the same type; the actual monadic chaining operator allows each step of a monadic chain to take different types as input, and return different types as output - so long as the value returned by one step matches the parameter type accepted by the next.

Let's take a look at how this value-carrying stuff can actually be really useful - and at the same time, get a look at the other really wonderful thing about Haskell's do syntax.
Suppose we want to write the usual follow-on to a hello world program - that is, a program that
asks for the users name, and then prints out a hello message using it. Here's the
program as a Python function:

def FancyHello():
   print "What is your name?"
   x = sys.stdin.readLine()
   print "Hello ", x

How do we do that in Haskell?

>fancyHello :: IO ()
>fancyHello =
>    do
>       print "What is your name?"
>       x <- getLine
>       print (concat ["Hello ", x])

In addition to the simple chaining, Haskell do statements allow us to bind
the payload returned by a step in a monadic sequence to a pattern, and then use the names defined by that pattern throughout the rest of the do statement. So, since "getLine" has type "IO String", in the body of a "do" statement, "getLine" can be treated as a function that returns a string - and the result of it can be bound to a variable using the "<-" operator.

There are a couple of tricks to using monads. Suppose in our fancyHello function,
we wanted to return the hello string with the users name, instead of printing it. You might think that we could do something easy like:

fancyHW :: String
fancyHW =
   do
      print "What is your name?"
      x <- getLine
      concat ["Hello ", x]

But if you try to put that through a Haskell compiler, you'll get a type error. You see, there's no way out of a monad. Once you're inside a monad, there's no way out. It's a closed world. You can't get out of it. So you can't return an input string from the IO monad without the IO state associated with it by the monad. So fancyHW can't return "String"; it must return "IO String". Based on that, you might think that
the fix would be to just change the declaration in the code above to:

fancyHW :: IO String
fancyHW =
   do
      print "What is your name?"
      x <- getLine
      concat ["Hello ", x]

Again, it doesn't work. concat returns a value of type String, not
a value of type IO String. How do we generate a value of type IO String? There's a function return, with type (Monad m) => a -> m a. What return does is wrap a non-monadic value into the appropriate monad type, so that it can be used as an element in a monadic sequence. So let's look at the correct version of
"fancyHW":

>fancyHW :: IO (String)
>fancyHW =
>   do
>      print "What is your name?"
>      x <- getLine
>      return (concat ["Hello ", x])

This works, but it's actually a bit deceptive. In fact, return is a bit deceptive -
it makes monadic code read more clearly in some cases, but it can also be very misleading, because it
does not return a value from the "do" statement; it just wraps a non-monadic
call, so that it can be enclosed in a monadic sequence. Let's look at a variation of the above
to see why it can be confusing. This is a bit artificial to make it short, but it illustrates the point.

>generateHelloMessage :: String -> String
>generateHelloMessage name = concat ["Hello there ", name, ", how are you?"]
>
>fancyTwo :: IO ()
>fancyTwo = do
>              print "What is your  name?"
>              x <- getLine
>              msg <- return (generateHelloMessage x)
>              print msg

See, the return call isn't returning a value from the do statement, it's just wrapping a non-monadic call so that it can be a participant in a
monadic sequence.

This isn't all there is to know about monads; this is just barely scratching the surface. We'll go farther with it in the next few posts. We'll go through some more details of the IO monad,
show a couple of other monad types, how to define your own monad types, and show a wonderful example of monads as glue: you can write YACC-like parser code in Haskell without a parser generator,
using a parser monad!