Deriving :: IO

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!

Preface¹

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)
import Text.Read (readMaybe)

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. In an impure language a function reading lines called readLine could potentially read input from anywhere: a global buffer, a file descriptor or socket, or just random data. If we want to maintain purity, we have to provide an additional parameter with the input we wish to read. This function must also return the unconsumed part of the input:

type Input = String
readLine :: Input -> (String, Input)
readLine "" = ("", "")
readLine xs = let first:rest = lines xs
              in (first, unlines rest)

λ: readLine ""
("","")
λ: readLine "foo\nbar\nbaz\n"
("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)
readLineEnv (Env input log') = let (line, rest) = readLine input
                               in (line, Env rest (log' ++ ["Read line: " ++ line]))

λ: readLineEnv $ inputEnv "foo\nbar\nbaz\n"
("foo",
Input: bar
baz

Log:
Read line: foo
)

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 new type for this transformation to simplify function signatures:

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

readLineEff :: Effect String
readLineEff = Effect readLineEnv

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

Log:
Read line: foo
)

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
  in case readMaybe line of
       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:
Read line: foo
Not a valid number: foo
)

With a valid number on the input:

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

Log:
Read line: 42
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

Let’s begin with the type signature of composeEff:

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))

The idea of composeEff is to start with an initial effect which yields an a. Then pass that a to another effectful computation expecting an a and yielding a b. Finally composeEff yields the b from the second effectful computation. This results in a new effectful computation which is the composition of the two effects:

composeEff eff f = Effect $ \env ->
  let (x, env') = runEffect eff env
  in runEffect (f x) env'

Let’s add another effectful computation:

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 =
  doubleEff x `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)
readSquareDoubleEff = readLineEff ==>
                      liftEff readMaybe ==> \case
                        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:
Read line: foo
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:
Read line: 42
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 from² 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)
readSquareDoubleEffMonad = do
  line <- readLineEff
  case readMaybe line of
    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:
Read line: foo
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:
Read line: 42
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)
readSquareDoubleIO = do
  line <- getLine
  case readMaybe line of
    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