Hangman: Imperative Functional Programming

In short, Haskell is the world's finest imperative programming language.

—Simon Peyton Jones, Tackling the Awkward Squad

In this post, we'll see how Haskell is perhaps the best way to write imperative programs. Now, Haskell is a purely functional programming language, which, according to Brent Yorgey's Introduction to Haskell, means three things:

• Everything is immutable.
• Nothing has side effects.
• Everything is referentially transparent.

In order to illustrate these ideas, let's take a look at a definition of the reverse function, which returns the elements of a list in reverse order:

reverse :: [a] -> [a]
reverse []     = []
reverse (x:xs) = reverse xs ++ [x]

We can apply reverse to "haskell", which is just a list of characters:

> reverse "haskell"
"lleksah"

When we reverse "haskell", we don't destroy it. Instead, we construct a new string or list of characters, namely, reverse "haskell" or "lleksah". In other words, everything is immutable.

Additionally, the type signature of reverse (that is, [a] -> [a]) means that it takes a list of elements of type a and returns a list of elements of type a, and that's it: no input, no output. When we apply reverse to "haskell", we can't print the result or update a database; if we reapply it, the result is always the same. In other words, nothing has side effects and everything is referentially transparent.

The fact that Haskell is a purely functional programming language is interesting and has a lot of benefits, especially when it comes to reasoning about our programs. However, if we couldn't tackle things like input and output, Haskell would be kind of useless.

Haskell allows us to do useful things like input and output by means of actions, which are like functions, except they have an IO tag somewhere in their type signature. This way, we know that a function (no IO tag) has no side effects and is referentially transparent, but an action (IO tag) may have side effects and may not be referentially transparent.

As an example of an action, we can print "haskell" in reverse order:

main :: IO ()
main = putStrLn (reverse "haskell")

Each time we run our program we get the same result:

> main
lleksah

In this case, the IO type in the type signature of main allows us to output the result of applying reverse to "haskell", which means that our program is referentially transparent, but has a side effect.

Of course, we can compose actions. For example, we can read a line and then print it in reverse order:

main :: IO ()
main = do
  line <- getLine
  putStrLn (reverse line)

Each time we run our program we may get a different result:

> main
haskell
lleksah
> main
lleksah
haskell

In this case, the IO type in the type signature of main allows us to read a line from the standard input device and output the result of applying reverse to the line, which means that our program is not referentially transparent and has a side effect.

We can think of the IO type as follows:

type IO a = World -> (a,World)

This means that an action of type IO a is a function that takes a world, gives a result of type a, and has permission to change the world. A nice way to see the difference between something of type a and something of type IO a is Brent Yorgey's cake example: if we have something of type Cake, we have a cake; but if we have something of type Recipe Cake, we don't have a cake, but a list of things we need to do in order to prepare a cake. In Haskell, IO a is somehow a recipe to get a value of type a, as opposed to just a value of type a.

There's no way to get a cake out of the actual recipe of a cake. We have to follow the instructions, which is what we do in Haskell when we list actions in the main function, which is like the main recipe of our program. In fact, the ability to distinguish between values and recipes of values is one of the greatest benefits of imperative functional programming in Haskell.

An excellent way to get a better understanding of imperative functional programming is to read chapter 10 of Richard Bird's Thinking Functionally with Haskell. More specifically, exercise J (write an interactive program to play hangman) is a great way to learn Haskell, and we plan to release a Haskell tutorial based on hangman soon.

In summary, Haskell's type system forces us to make a clear distinction between actions and functions, impure and pure code, as well as imperative and nonimperative programming. We have imperative programming where we want to, and only where we want to.

So, when programming in Haskell, we can enjoy the benefits of pure functional programming (basically, equational reasoning) and do imperative functional programming, which means fewer headaches. "In short, Haskell is the world's finest imperative programming language."