Skip to content

Instantly share code, notes, and snippets.

@hdgarrood
Last active November 10, 2015 20:48
  • Star 0 You must be signed in to star a gist
  • Fork 1 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save hdgarrood/c8a3ed3591b75e93e420 to your computer and use it in GitHub Desktop.

Monads in Haskell (followup to Haskell Workshop)

Posted on 27th October 2015 by Ingo Blechschmidt

Translated to English by @hdgarrood. There might be mistakes. Any remarks I've made are in square brackets.

This short article should briefly outline how monadic IO works in Haskell, as a follow up to the Haskell Workshop. TL;DR:

  • A value of type IO a is a description of an IO action, which could be performed by the runtime environment (and thereby cause some side effects and eventually produce a value of type a).

  • The meaning of a Haskell program is determined by setting main to a description of an IO action. This action is then performed by the runtime environment. Other actions are not performed.

  • Descriptions of IO actions can be combined with each other with >> and >>= or do-notation. The >> operator is like a line-ending semicolon in other languages.

  • If you only want mutable state, you don't need the IO monad. You can thread state through by hand — or use the convenient abstraction, the State monad.

The problem: incompatibility with referential transparency

In many programming languages there is a function like readFile :: FilePath -> String, which reads in a file and returns its contents. Such a function can not exist in Haskell, because in Haskell the principle of referential transparency holds: like in mathematics, functions must produce the same outputs given the same inputs. The return value of readFile "foo.txt", however, depends on the current contents of the file "foo.txt".

In Haskell the principle of referential transparency is held in high regard, because it enables us to understand code locally [not 100% sure about this bit] and to restructure it easily. Whenever you spot the same subexpression in two places in the code, you can replace them with a single variable, introduced via let ... in ... or where .... Without referential transparency this doesn't work:

# The following code ...
say foo();
say foo();

# ... will, in general, do something different to this:
my $x = foo();
say $x;
say $x;

because foo() could trigger side effects, which would then be performed just once as opposed to twice (for example, posting something on Twitter), or depend on mutable state (for example, the number of nanoseconds elapsed since the program start).

How, therefore, can we reconcile the wish for referential transparency with the necessity of performing IO?

The solution: monadic IO

In Haskell — after a few suboptimal solutions and missteps — the concept of monadic IO was come across, which comprehensively solves the problem. It has an elegant mathematical background, which you don't need to know to use it. Here is program which amicably greets the performing Lambdroid[?]:

main = do
    putStr "Hello! What is your name? "
    name <- getLine
    putStr "That's a nice name. Here it is backwards: "
    putStrLn $ reverse name

The types involved are getLine :: IO String and putStr :: String -> IO () [note: putStrLn is also String -> IO ()]. The constant main has the type main :: IO ().

What is happening here? It's still the case that Haskell functions can't cause side effects such as interaction with the terminal. Haskell functions can however theoretically describe[?] IO actions. The meaning of a Haskell program, in this sense, lies in the description of a particular IO action - the one named main. This one is then performed by the runtime system.

Just as a value of the type Tree a is a Tree, whose leaves are of the type a, a value of the type IO a is a description of an IO action, which in principle could be performed by the runtime system, and would thereby cause some side effects and eventually produce a value of the type a. Such descriptions are "first class values"; they can be manipulated and placed inside data structures, without immediately being performed during program execution. Indeed, only one description is performed: the one which carries the name main.

The following code example should emphasize this point.

main = seq (putStrLn "abc") (putStrLn "def")

The function seq forces the evaluation of its first argument — when seq x y is evaluted, first x is evaluated, and then y is returned. For example, seq (fib 10000) "Curry" is semantically fully identical to the constant "Curry", but slower in its execution.

In any case, during execution of this program, the following happens: first putStrLn "abc" is evaluated. This produces a description of an IO action, which, when evaluated, would produce abc in the terminal. This description is then, however, thrown away. putStrLn "def" produces a description, which would produce def. This description is ultimately the value of main, and this description is executed by the runtime system.

Construction of complex action descriptions

Pre-implemented functions like putStrLn :: String -> IO () or readFile :: FilePath -> IO String produce certain primitive descriptions of IO actions. The majority of programs will have to make use of several of these primitive actions. We must therefore have the capability to combine several action descriptions into one complex description — just as [approximately?] the constructor Fork combines two subtrees into one larger one.

For this purpose, in fact, we have several possibilities:

  • The operator (>>) :: IO a -> IO b -> IO b takes two action descriptions. If the resulting description m >> n is executed, then first m is executed (and its result of the type a discarded) and then n is executed.

  • In many cases we would like to make the second action dependent on the result of the first. To do this, there is the operator (>>=) :: IO a -> (a -> IO b) -> IO b. The action description m >>= f, when executed, does the following: first, m is executed. The value it produces, x, is given over to the function f, which generates a further action description, f x. This is then executed as the second action.

Additionally, there is one more trivial option to produce an action description: with the function return :: a -> IO a, which (watch out!) has nothing to do with the identically named keyword in many other languages (for early exiting of a subroutine). Instead, return x is an action description, which, when evaluated, causes no side effects and then produces the value x.

The expression return x >> m can be simplified to just m. Both expressions descripe exactly the same action. Also, return x >>= f is identical to f x.

Finally, the Functoriality of action descriptions should be mentioned. If m :: IO a is an action description, which produces a value x of the type a when evaluated, and if g :: a -> b is an arbitrary function, then fmap g m :: IO b describes the action, which executes the description m, whose result x it then feeds in to the function g and thereby produces the value g x :: b.

For historical reasons, you can write fmap g m instead of liftM g m. Both expressions describe exactly the same IO action.

Do-notation

Haskell facilitates dealing with action descriptions immensely with do-notation. It is pleasant syntactic sugar for the operators >> and >>=. The introductory example is written as follows without do-notation:

main =
    putStr "Hello! What is your name? " >>
        getLine >>=
            (\name ->
                putStr "That's a nice name. Here it is backwards: " >>
                    putStrLn (reverse name))

The translation rules therefore mean that:

  • Two consecutive instructions are implicitly joined with >>.

  • The binding of a production result of an IO action with <- is implemented with a λ-expression and >>= behind the scenes.

Such bindings distinguish themselves from variable definitions with let. A longer program could, for example, look like this:

main = do
    putStr "What is the radius of the circle? "
    answer <- getLine
    let radius        = read answer
        circumference = 2 * pi * radius
        n             = fib 42
    putStrLn $ "Then the circumference is: " ++ show circumference
    putStrLn $ "And the 42nd Fibonacci number is: " ++ show n

In let expressions in do-notation, the otherwise required keyword in can be omitted.

Referential transparency is preserved

The following code produces two outputs:

main = do
    putStrLn $ show $ fib 42
    putStrLn $ show $ fib 42

If we disregard compiler optimizations, the action description putStrLn $ show $ fib 42 will be computed twice. If desired, the code can be restructured as follows:

main = do
    let m = putStrLn $ show $ 42
    m
    m

-- Alternative without do-notation:
main = m >> m where m = putStrLn $ show $ 42

Here, the expression is only computed once, but nevertheless still executed twice.

Some control structures

Because action descriptions are first class values, we can easily define control structures. The module Control.Monad exports the following:

-- `forever m` describes an infinite repetition of `m`.
forever :: IO a -> IO ()
forever m = m >> forever m

-- `replicateM i m` describes an action which, when executed,
-- executes the given action `m` `i` times, and collects the
-- produced results in a list.
replicateM :: Int -> IO a -> IO [a]
replicateM 0 _ = return []
replicateM i m = do
    x  <- m
    xs <- replicate (i-1) m
    return (x:xs)

-- What does this function do?
forM :: [a] -> (a -> IO b) -> IO [b]
forM []     _ = return []
forM (x:xs) f = ...

A pitfall with return

The following code contains a type error:

main = do
    eman <- reverser
    putStrLn eman

reverser = do
    name <- getLine
    reverse name

The problem is in the line reverse name. When do-notation is used, each line (excluding pure parts using let) must be an action description, as these lines will eventually be combined into one large description behind the scenes with >> or >>=. The expression reverse name is however a simple list, not an action description. The remedy is to use return:

main = do
    eman <- reverser
    putStrLn eman

reverser = do
    name <- getLine
    return $ reverse name

More idiomatically, we could write the program as follows, by the way:

main     = reverser >>= putStrLn
reverser = fmap reverse getLine

The State monad

In Haskell there are no mutable variables. They must be emulated: a function, which wants to modify a particular variable, can simply return the new value to the caller. Then, in subsequent function calls, the new value must be used. Concretely, an example could look like this:

f1 :: S -> (A,S)
f2 :: S -> A -> (B,S)
f3 :: S -> B -> (C,S)

f :: S -> (C,S)
f s =
    let (x,s')   = f1 s
        (y,s'')  = f2 s'  x
        (z,s''') = f3 s'' y
    in  (z,s''')

Through this manual threading-through of state, mutable variables can be recreated. However this is not nice! And, moreover, it is error-prone. In particular, the compiler can't protect us if we switch the intermediate states; for example, if we wrote f3 s' y instead of f3 s'' y.

The State monad is the remedy. The following code is much more comprehensible:

f1 :: State S A
f2 :: A -> State S B
f3 :: B -> State S C

f :: State S C
f = do
    x <- f1
    y <- f2 x
    z <- f3 y
    return z
-- or shorter: f = f1 >>= f2 >>= f3

A value of the type State s a can be imagined as the description of an action, analogously to IO: one, which via access and potential modification of a state of type s, produces a value of type a.

Primitive state action descriptions are put :: s -> State s () to set the state, and get :: State s s to read it.

Such a description can be executed with the function runState :: State s a -> s -> (a,s), when we specify an initial value for the state. This is different to the IO monad: only the runtime system is capable of executing an IO action. State actions, by contrast, can be executed inside Haskell.

Incidentally, it's not particularly common to need mutable variables in day-to-day Haskell use. An alternative solution without mutable variables is almost always more elegant and maintainable. If you're inclined to programming imperatively, it pays off to invest some effort in finding stateless implementations.

More monads

Necessity is the mother of invention: after the usefulness of the monadic approach for IO was recognised, many more useful monads were discovered and designed.

  • State (mutable state)
  • Parser (Parsing of text, example: S-expressions)
  • Maybe (Handling of failure cases, avoidance of "or else"-cascades)
  • Reader (providing an environment, global configuration values)
  • Writer (logging)
  • Listen (Nondeterminism and logic programming, example: magic square)
  • Cont (Continuations, influencing the flow of control)

Monads distinguish themselves with the operators >>= and return, in addition to fmap. There is a Monad type class, which all monads belong to. Its definition:

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

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

Occasionally we can even program polymorphically with monads. That is, the previously mentioned control structures forever, replicateM, and forM make sense not only in the special case of the IO monad, but also for every other monad.

What next?

First there are our exercises from the workshop. Next, there are numerous introductions into the world of monads. Additionally, there is the article about the Monad Tutorial Fallacy. As soon as someone has understood monads, they instantly lose the ability to explain them clearly.

For those who are more advanced, and would like to understand what monads have to do with monoids, the Foliensatz [Foil Theorem?] from one of the Curry Club meetings is recommended. In any case, the magnificent article by Dan "sigfpe" Piponi is worth reading for everyone: You could have invented monads (And maybe you already have.)

@iblech
Copy link

iblech commented Nov 6, 2015

Original author here. Wow, I am humbled; thank you for translating! In the evening I'll fix the unclear passages for you.

@iblech
Copy link

iblech commented Nov 10, 2015

Sorry for not returning to you sooner. I improved the wording in a very small number of places (and in that process also changed the German original a bit): See the fork at https://gist.github.com/iblech/429652a31b05e408262b. Feel free to incorporate the changes (unfortunately there are not pull requests with gists) and/or remove the "secret" flag of the gist. Cheers and thanks again!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment