How to add imperative programming to a pure functional language

Or, charming the Python


Many people bemoan languages such as Haskell for not supporting imperative programming; they decry the need for math in their computer science.

Math? In my computer? Yeah right.
Math? In my computer? Yeah right.

I'm here to tell you that not only does Haskell make imperative programming a cinch, but safe and correct as well. Follow along! This post is written in Literate Haskell, so its source code can be compiled and run as a program. The source is here.

1 Part the First: The boilerplate

Surprisingly, you won't need much boilerplate for this exercise:

{-# LANGUAGE DeriveFunctor #-}
{-# LANGUAGE StandaloneDeriving #-}
import Control.Monad.Free

Haskell already has built in notions of Functors, Monads, and other mathematical substrate that we'll need as typeclasses.

I'm going to assume you've at least seen the words Functor and Monad before, and if you haven't, you should Google around for any one of the thousands of existing explanations.

Importing Control.Monad.Free brings in what has been my favorite feature of late: the Free monad.

The Free monad is what it sounds like: it is a generic instance of the Monad typeclass. All you have to do is supply a Functor type and the Free type constructor spits out a Monad.

2 Part the Second: SHOW ME ALREADY


newtype Then k = Then k
deriving instance Functor Then
type Imperative = Free Then

That's it. Imperative is now a monad. But what does it do? Good question - that's the part we must fill in. In our case we wish to be able to write imperative, this-then-this-then-this style programs.

3 Part the Third: Give my creation ... LIFE!

Dr Frankenstein has been a very naughty boy
Dr Frankenstein has been a very naughty boy

So now we should specify the behavior of our newly minted monad. We will define a function that evaluates programs in our little monad.

imperative :: Imperative a -> a
imperative (Free (Then next)) = imperative next
imperative (Pure v)           = v

We did it. Really. This code says that if we get a value of Free we should unpack the value inside of it and loop; otherwise, we have broken the program down as far as we can and should evaluate the expression we have uncovered.

4 Part the Fourth: Examples

We'll write some simple arithmetic functions, including the types for pedagogical thoroughness:

mySquare :: Int -> Imperative Int
mySquare n = return $ n * n
myAdd1 :: Int -> Imperative Int
myAdd1 n = return $ n + 1

And for legibility later, I'll define this stupid thing:

set :: a -> Imperative a
set = return

You get the idea. And now for an example usage. Remember, in Haskell you get fancy "do-notation" when you're doing work inside a monad.

ex1 :: Int
ex1 = imperative $ do
    a <- set 5
    b <- mySquare a
    c <- myAdd1 b
    return c
main :: IO ()
main = let v = ex1 in putStrLn . show $ v

Running this, I get 26 in my terminal as expected.

Obviously, the mere existence of such notation indicates the folks who make Haskell are keenly aware of what I'm saying; the whole reason we're talking about monads right now is because Philip Wadler thought of this first.

But I hope I showed you how easy this is. Monads are programmable semicolons. (NB: Python has semicolons, too, but you probably never use them.) The Free monad makes it ridiculously easy to create monads. I've defined arguably the most trivial monad one can define, in like 15 lines of real code, and already this code is as easy to write as something like Python but with static type safety.

Not that I don't like Python - I feed myself writing it these days - but complexity does not have to be daunting or impossible. Often, a good amount of upfront complexity enables extreme simplicity later.