Day 2: [] — Seeing the rest of a program run

Here’s a list comprehension:

> [ x * y | x <- [1,2,3], y <- [10,100]]
[10,100,20,200,30,300]

This works in do notation too, with a bit of rearranging:

Prelude> do
Prelude|   x <- [1,2,3]
Prelude|   y <- [10,100]
Prelude|   return (x*y)
Prelude| 
[10,100,20,200,30,300]

In IO the are step individual steps are actions which do things to the real world. In this monad, though, they’re just lists (or functions that evaluate to lists) — for example [1,2,3] or (reverse “hello"). But in some way, it is nice to think about some action being done here with every step — and that action is to non-deterministically choose an element from a list.

We don’t have to “run” a computation in the list monad any futher than letting Haskell perform normal evalution of the whole monadic expression / do block / list comprehension.

We can desugar the above into a first bit and the rest, like in the previous post:

Prelude> let first_bit = [1,2,3]
Prelude| rest_of_program x = do
Prelude| y <- [10,100]
Prelude| return (x*y)
Prelude| 
Prelude> first_bit >>= rest_of_program
[10,100,20,200,30,300]

What’s happening in this evaluation? >>= means something like: pick each value from the first bit in turn, run the rest of the program with that value, and then stick all the results together. We can do this by hand:

> first_bit
[1,2,3]
> rest_of_program 1
[10,100]
> rest_of_program 2
[20,200]
> rest_of_program 3
[30,300]
> concat [rest_of_program 1, rest_of_program 2, rest_of_program 3]
[10,100,20,200,30,300]

That leads onto a different definition of monads, using fmap and join (map and concat are the []-specialised versions of these):

fmap :: Functor m => (a -> b) -> m a -> m b
join :: Monad m => m (m a) -> m a
-- m a is [a] here

We can take the first part of the program, and fmap the rest of the program over it:

> fmap rest_of_program first_bit
[[10,100],[20,200],[30,300]]

That gives us all the right values, but nested (reflecting the step-by-step structure of the program). We can use join to remove that nesting:

join [[10,100],[20,200],[30,300]]
[10,100,20,200,30,300]

So join (fmap rest_of_program first_bit)is the same as first_bit >>= rest_of_program — even though they look like quite different things. At first (at least to me) it felt like map/concat were data structure operations, and >>= was a control flow operation. But they end up doing the same thing.

For lists, fmap is regular list map and join is regular list concat but these should be available for our other monad, IO, too.

I realised when I came to write this post that I didn’t know quite what that would look like. I knew if you did the above join and fmap that the end result would be the same, but I didn’t know off the top of my head what the intermediate stages would look like.

main = first_thing >>= rest_of_program
first_thing :: IO String
first_thing = getLine
rest_of_program :: String -> IO ()
rest_of_program text = do
 putStr “Your name is: “
 putStrLn text

We can instead write main like this instead:

main = join (fmap rest_of_program first_thing)

What’s happening here?

first_thing is an IO action that (when run) returns a String (that it has read from the console).

fmap sticks on a pure function to be applied to that result. For example, this will give an IO action that reads a line and returns the length of the input:

-- fmap length first_thing :: IO Int
> fmap length first_thing
hello
5

So when we fmap the rest of the program, we get an IO action that, when you run it, reads a line and returns another IO action, x. And if we run that second action x the rest of the program runs, already knowing what name to output.

-- fmap rest_of_program first_thing :: IO (IO ())
> x <- fmap rest_of_program first_thing 
Ben
> :t x
x :: IO ()
> x
Your name is: Ben

So that is what join does: it runs an IO (IO ()) action, gets the resulting action, and runs that too.

Note that you can run the rest of the program,x, lots of times. It doesn’t ask for your name:

> x
Your name is: Ben
> x
Your name is: Ben
> x
Your name is: Ben

Also note that with [] we get different tooling to manipulate “actions” compared to IO — when an “action” is a list, we can use all sorts of functions like concatenation, filtering and sorting to decide what our next set of choices will be. Those come from [] as a list, not [] as a monad.