Deriving :: IO

Posted on 2018-11-15

I’ve been really getting back into functional programming lately. In particular, with both Haskell and PureScript. When attempting to revamp/rewrite pieces of an internal web app, a colleague and myself decided it was time to start playing around with PureScript. This kick-started us getting back into discussions about FP, reading up on new material, writing all kinds of toy projects, and starting a Haskell study group at work. I thought I could attempt to prepare material for the study group by writing blog posts about the topics up front. Which explains the purpose of this post!

Preface1

This post is written as a literate Haskell program, so all code snippets should be executable and can be interpreted as a complete Haskell module.

We need to define our module, with some convenient language extensions. So let’s get that out of the way:

``````{-# LANGUAGE LambdaCase #-}
{-# LANGUAGE TupleSections #-}

module Effect where

import Prelude hiding (log)

Purity is king

Functions in Haskell are pure. For every input, there’s a single, well-defined output. This is called referential transparency. Here’s an example:

``````doublePure :: Int -> Int
doublePure x = x * 2``````
``````λ: doublePure 42
84
``````

There’s really no way for `doublePure` to perform any other action than doing valid operations with number of the `Int` type. But what if we want to keep a log of the calculations we’re performing?

Outbound side-effects

First let us define a `Log` type which is a list of `String`, to be able to provide multiple log statements in a computation:

``type Log = [String]``

If we want to introduce logging to our pure function, we can simply return the log along with our value:

``````doubleLog :: Int -> (Int, Log)
doubleLog x = (result, ["Doubling: " ++ show x ++ " => " ++ show result])
where result = doublePure x``````
``````λ: doubleLog 42
(84,["Doubling: 42 => 84"])
``````

This keeps the function just as pure, but forces the caller to handle the log in some way.

Inbound side-effects

Next, we’d like to add side-effect inputs to our functions, while keeping them pure. We have to provide an addition parameter containing the data we wish to read. This function must also return the unconsumed part of the input:

``````type Input = String
readLine :: Input -> (String, Input)
readLine xs = let first:rest = lines xs
in (first, unlines rest)``````
``````λ: readLine ""
("","")
("foo","bar\nbaz\n")
``````

We can see that the result of reading a line consumes the first line and returns it as the first tuple element, while the rest of the input is preserved in the second tuple element.

Hiding our effect internals

We have to combine these two concepts into one to be able to create a function which both reads input and produces a log. We also have to combine our `Input` data type with our `Log` type unless we want our tuple type to become unwieldy:

``````data Env = Env Input Log
instance Show Env where
show (Env input log) = unlines \$ "" : ("Input: " ++ input) : "Log:" : log``````

“Env” is short for “Environment”. What the environment is exactly should not be a concern for the programmer, but it can be thought of as the entire execution context in which an effectful program/computation is running. Some like to name this type “World”.

To simplify creating `Env`’s later, we’ll define an initial, or empty `Env`:

``````initEnv :: Env
initEnv = Env "" []``````

and an `Env` with some initial input:

``````inputEnv :: String -> Env
inputEnv input = Env input []``````

Environment transformers

Let’s define a function reading a line from the environment, logging the line and yielding it as a return value:

``````readLineEnv :: Env -> (String, Env)
in (line, Env rest (log' ++ ["Read line: " ++ line]))``````
``````λ: readLineEnv \$ inputEnv "foo\nbar\nbaz\n"
("foo",
Input: bar
baz

Log:
)
``````

We can see that `readLineEnv` is transforming the environment by accepting an initial `Env`, and returning a line (`String`) together with an updated `Env` with our input consumed and log message appended.

Let’s create a type alias for this transformation to simplify function signatures:

``````newtype Effect a = Effect { runEffect :: Env -> (a, Env) }

``````λ: runEffect readLineEff \$ inputEnv "foo\nbar\nbaz\n"
("foo",
Input: bar
baz

Log:
)
``````

We call the type `Effect` to signal that it has an effect on the environment.

Bring on the `Effect`!

We can now start defining effectful computations, using our `Effect` type.

To simplify logging, let’s create an effectful function for appending a log message to the environment:

``````appendLog :: String -> Effect ()
appendLog msg = Effect \$ \(Env input log') -> ((), Env input (log' ++ [msg]))``````
``````λ: runEffect (appendLog "Hello, World!") initEnv
((),
Input:
Log:
Hello, World!
)
``````

We can then create an effectful version of our `doubleLog`:

``````doubleEff :: Int -> Effect Int
doubleEff x = Effect \$ \env ->
let (_, env') = runEffect (appendLog message) env
in (result, env')
where result = x * 2
message = "Doubling: " ++ show x ++ " => " ++ show result``````
``````λ: runEffect (doubleEff 42) initEnv
(84,
Input:
Log:
Doubling: 42 => 84
)
``````

Then we can create an effectful function which reads a number from the input and doubles it using `doubleEff`:

``````readDoubleEff :: Effect (Maybe Int)
readDoubleEff = Effect \$ \env ->
let (line, env') = runEffect readLineEff env
Nothing  -> let (_, env'') = runEffect (appendLog ("Not a valid number: " ++ line)) env'
in (Nothing, env'')
Just num -> let (num', env'') = runEffect (doubleEff num) env'
in (Just num', env'')``````

Without a valid number on the input:

``````λ: runEffect readDoubleEff \$ inputEnv "foo\nbar"
(Nothing,
Input: bar

Log:
Not a valid number: foo
)
``````

With a valid number on the input:

``````λ: runEffect readDoubleEff \$ inputEnv "42\nfoo\nbar"
(Just 84,
Input: foo
bar

Log:
Doubling: 42 => 84
)
``````

Writing `readDoubleEff` we’re struck with the sudden realization that we can’t immediately compose our effectful functions. What if we had more of these. Do we have to write functions like `readDoubleEff` each time?

We can surely do better!

Composing effects

``composeEff :: Effect a -> (a -> Effect b) -> Effect b``

Note: Expanding the type of this type alias is quite intimidating:

``composeEff :: Effect (Env -> (a, Env)) -> (a -> Effect (Env -> (b, Env))) -> Effect (Env -> (b, Env))``
``````composeEff eff f = Effect \$ \env ->
let (x, env') = runEffect eff env
in runEffect (f x) env'``````

``````squareEff :: Double -> Effect Double
squareEff x = Effect \$ \env ->
let (_, env') = runEffect (appendLog message) env
in (result, env')
where result = x ^ (2 :: Int)
message = "Squaring: " ++ show x ++ " => " ++ show result``````
``````λ: runEffect (squareEff 42) initEnv
(1764.0,
Input:
Log:
Squaring: 42.0 => 1764.0
)
``````

There are a couple of pieces missing in order to compose our `doubleEff` and `squareEff`.

First we need a way to inject an initial value into our computation:

``````pureEff :: Show a => a -> Effect a
pureEff x = Effect \$ \env ->
let (_, env') = runEffect (appendLog message) env
in (x, env')
where message = "Injecting: " ++ show x``````
``````λ: runEffect (pureEff (42 :: Int)) initEnv
(42,
Input:
Log:
Injecting: 42
)
``````

Note: The `Show` constraint is purely because we want to display our value in the log, and without this logging the function is quite a bit simpler:

``````pureEff' :: a -> Effect a
pureEff' x = Effect (x,)``````

Then, because `squareEff` expects a `Double`, while `doubleEff` returns an `Int` (no pun intended), we have to be able to “lift” regular functions into our computation. This would allow us to use functions like `fromIntegral` to convert our `Int` to a `Double`.

``````liftEff :: Show a => Show b => (a -> b) -> a -> Effect b
liftEff f x = Effect \$ \env ->
let (_, env') = runEffect (appendLog message) env
in (result, env')
where result = f x
message = "Lifting: " ++ show x ++ " => " ++ show result``````
``````λ: runEffect (liftEff (*2) 42) initEnv
(84,
Input:
Log:
Lifting: 42 => 84
)
``````

The same goes for `liftEff` as with `pureEff` with regards to the `Show` constraints:

``````liftEff' :: (a -> b) -> a -> Effect b
liftEff' f x = Effect (f x,)``````

We can now compose our effectful functions into chained computations with effects!

``````squareDoubleEff :: Int -> Effect Double
squareDoubleEff x =
pureEff x `composeEff`
doubleEff `composeEff`
liftEff fromIntegral `composeEff`
squareEff``````
``````λ: runEffect (squareDoubleEff 42) initEnv
(84,
Input:
Log:
Lifting: 42 => 84
)
``````

Is this operator?

We see that using `composeEffects` infix is a bit clunky, so let’s improve this by defining a handy infix operator alias. We use an arrow-like function to signal the direction of composition:

``````infixl 1 ==>
(==>) :: Effect a -> (a -> Effect b) -> Effect b
(==>) = composeEff``````

Finally, now we’re Effin’ getting somewhere!

``````squareDoubleEffin :: Int -> Effect Double
squareDoubleEffin x = pureEff x ==> doubleEff ==> liftEff fromIntegral ==> squareEff``````
``````λ: runEffect (squareDoubleEffin 42) initEnv
(84,
Input:
Log:
Lifting: 42 => 84
)
``````

Lets’ combine this with our effectful reader:

``````readSquareDoubleEff :: Effect (Maybe Double)
Nothing  -> appendLog "Could not read a valid number" ==> \_ ->
pureEff Nothing
Just num -> squareDoubleEffin num ==>
liftEff Just``````

With invalid input:

``````λ: runEffect readSquareDoubleEff \$ inputEnv "foo\nbar"
(Nothing,
Input: bar

Log:
Lifting: "foo" => Nothing
Could not read a valid number
Injecting: Nothing
)
``````

With valid input:

``````λ: runEffect readSquareDoubleEff \$ inputEnv "42\nfoo\nbar"
(Just 7056.0,
Input: foo
bar

Log:
Lifting: "42" => Just 42
Injecting: 42
Doubling: 42 => 84
Lifting: 84 => 84.0
Squaring: 84.0 => 7056.0
Lifting: 7056.0 => Just 7056.0
)
``````

Do do do…

At this point we’re able to compose effectful computations to create programs which manages side-effects in a pure manner, without the programmer having to worry about managing these effects.

We have seen from our exploration with composition that we can’t quite hide the “gluing” of the composed pieces, namely the composition arrow `==>` and occasional lambda abstractions.

We’re in luck though!

Haskell provides syntactic sugar to improve the readability of these kinds of effectful computations, called `do` notation. Specifically, `do` notation works by using the `Monad` composition operator `>>=`, called “bind”, to sequence computations. The catch is that we’d have to implement the `Monad` instance for our `Effect` type. Turns out we have already made most of the tools we need in order to that.

`Monad` requires our type to also be an instance of `Functor` and `Applicative`. So first let’s define `Functor`:

``````instance Functor Effect where
fmap f eff = eff ==> liftEff' f``````

`fmap` takes a pure function and applies it to a value from2 an effectful computation. Our instance needs to extract a value from the left hand side computation, and apply `f` to it. We do that using our `composeEff` function.

Then for `Applicative`:

``````instance Applicative Effect where
pure = pureEff'
effFn <*> eff = effFn ==> \f -> eff ==> \x -> pure (f x)``````

`Applicative` requires us to provide means of injecting pure values into effectful contexts, as well as means of applying functions from effectful contexts to values from effecful context. The definition of `<*>` must therefore extract an `f` from the left hand side, then extract an `x` from the right hand side, apply `f` to `x`, and wrap up the result.

Finally, the grand finale: `Monad`! Perhaps without knowing we’ve already implemented the bind operator, namely our `composeEff` function:

``````instance Monad Effect where
(>>=) = composeEff``````

Wow! I’ve heard that monads are hard… What an anti-climax!

Let’s try to run our new, shiny `Monad Effect`!

``````readSquareDoubleEffMonad :: Effect (Maybe Double)
Nothing  -> do
appendLog "Could not read a valid number"
pure Nothing
Just num -> do
result <- squareDoubleEffin num
pure \$ Just result``````

With invalid input:

``````λ: runEffect readSquareDoubleEff \$ inputEnv "foo\nbar"
(Nothing,
Input: bar

Log:
Lifting: "foo" => Nothing
Could not read a valid number
Injecting: Nothing
)
``````

With valid input:

``````λ: runEffect readSquareDoubleEff \$ inputEnv "42\nfoo\nbar"
(Just 7056.0,
Input: foo
bar

Log:
Lifting: "42" => Just 42
Injecting: 42
Doubling: 42 => 84
Lifting: 84 => 84.0
Squaring: 84.0 => 7056.0
Lifting: 7056.0 => Just 7056.0
)
``````

From `Effect` to `IO`

Our `Effect` type is starting to become a pretty good approximation of Haskell’s `IO` type. One significant difference though is our type is actually not able to talk to the outside world. We have, however, succeeded in hiding all `Effect` details behind utility functions. What this gives us is an opaque type which we know nothing about, but which “carries” our side-effects around in our computation.

If we were to choose at this point to hide our data constructor `Effect` and `runEffect`, we would no longer be able to initiate nor evaluate effectful computation. Instead, we would have to rely on our entry-point to provide us with our initial `Env` and run our computation.

This is exactly what Haskell does with its `IO` type. Through `main :: IO ()` we are granted a way to compose effects into a sensible program, never really knowing what the runtime systems does in order to accommodate us in our requests.

To illustrate how close we are, here’s a function to turn effectful computations into `IO` ones.

``````effToIO :: Effect a -> IO a
effToIO eff = let (result, env) = runEffect eff initEnv
in do print env; pure result``````

and here’s the `IO` version of our `readSquareDoubleEffMonad`:

``````readSquareDoubleIO :: IO (Maybe Double)
line <- getLine
Nothing  -> do
effToIO \$ appendLog "Could not read a valid number"
pure Nothing
Just num -> do
result <- effToIO \$ squareDoubleEffin num
pure \$ Just result``````
``````λ: readSquareDoubleIO
42

Input:
Log:
Injecting: 42
Doubling: 42 => 84
Lifting: 84 => 84.0
Squaring: 84.0 => 7056.0

Just 7056.0
``````

And that concludes our playful derivation of the `IO` type in Haskell. Tada!

Footnotes

1. The material covered in this post is not revolutionary in any way, and there’s plenty of sources online which covers this from other angles. In particular, this post was inspired by a recent `YouTube` video: What is IO Monad?

2. I find that saying `Functor` applies a function to a value in a context doesn’t properly capture the cases where the context is an execution of sorts. This is because the value isn’t necessarily stored in a context, but it’s a context which yields a value.