Defining Modular Monads

This file has two sections. The first only makes more sense after reading the second. So, be sure to read this file twice.

We can now return to the original question we raised at the start of the Free folder: if we wanted to run a sequential computation (i.e. use a monad) that used multiple effects, could we stop fighting against the "bind returns the same monad type it receives" restriction and simply use just one monad? Yes. Similar to our previous examples, we can use Coproducts of two or more Free monads.

Getting Around The Non-Free-Monad Limitation

Unfortunately, this Coproduct + Free approach only works on Free monads; it does not work for other non-Free monads. As the paper says, the ListT and StateT monads are not free monads. Why? Let's consider the StateT monad. The issue at hand are its laws. If I call set 4 and then later call get, get should return 4. By using Free as we have so far, we cannot uphold that law.

So, how do we get around that limitation? We can define a type that has an instance for Functor and whose values represent terms in a language (similar to our Add, Multiply, Value language) that provides the operations we would expect from such a monad. The paper's example shows how one could create a State monad using this approach. Since it will follow much of what we have already covered before, we'll just show the Purescript version of their code.

data Add      theRestOfTheComputation = Add Int theRestOfTheComputation
data GetValue theRestOfTheComputation = GetValue (Int -> theRestOfTheComputation)

-- Why the `a` type is `Pure` will become clear
-- in the next section where we define the
-- `Exec` type class instances
add :: forall f. Int -> Free f Unit
add i = liftF $ Add i (Pure unit)

getValue :: forall f. Free f Int
getValue = liftF $ GetValue Pure

-- The `Free` monad's equivalent of `State StateType OutputType`
-- simulates "function(x) => {
--    var y = get(x);
--    set(x, x + 1);
--    return y;
-- }"
stateComputation :: Free (Coproduct Add1 GetValue) Int
stateComputation = do
  y <- getValue
  add 1
  pure y

-- Computes the pure description of machine instructions
-- that are stored via `Free f a` down into `b`
-- using the provided functions
foldFree :: Functor f => (a -> b) -> (f b -> b) -> Free f a -> b
foldFree pure _ (Pure x) = pure x
foldFree pure impure (Impure t) = impure (fmap (foldFree pure impure) t)

newtype Memory = Memory Int

class Functor f => Free f where
  runAlgebra :: f (Memory -> Tuple a Memory) -> (Memory -> Tuple a Memory)

instance Free Add where
  runAlgebra (Add amount restOfComputation) (Memory i) =
    restOfComputation (Memory (i + amount))
instance Free GetValue where
  runAlgebra (GetValue intToRestOfComputation) (Memory i) =
    (intToRestOfComputation i) (Memory i)

instance (Functor f, Functor g) => Free (Either f g) where
  runAlgebra (Left r) = runAlgebra r
  runAlgebra (Right r) = runAlgebra r

instance (Functor f, Functor g) => Free (Coproduct f g) where
  runAlgebra (Coproduct either) = runAlgebra either

run :: Functor f => Free f a -> Memory -> Tuple a Memory
run =
--          Pure               Impure     computation  initialState
  foldFree (\a b -> Tuple a b) runAlgebra

{- In the REPL
> run stateComputation (Memory 4)
(4, Memory 5)

Modular Effects via Languages

When we learned about the ReaderT design pattern, we saw that it simply "links" the capabilities we need to run a pure computation with its impure implementations (the type class' instances). As we will show later, this makes it much easier to test our "business logic."

Similarly, the Free monad is the thing which "links" some capability needed in a pure computation with its impure implementation. Whereas ReaderT used "capability type classes," Free using "languages" like the state manipulation language, Add/GetValue, demonstrated in the previous section. Thus, we can easily add new "effects" to our Free monad by adding more "languages."

Whereas the ReaderT design pattern would use type class instances to implement these capabilities, a Free monad will use an interpreter. An interpreter can be a few different hings:

  • the actual machine code layer that runs the computation in Effect/Aff
  • a pure computation (used for testing) that runs in Identity
  • something that pretty prints the instructions the computer would execute

Defining and Interpreting Languages for the Free Monad

When we look at how to define a language data type for the Free monad, it follows this pattern (written in meta-language):

data Language theRestOfTheComputation
  -- Statement that tells interpreter to do something but
  -- doesn't pass down any arguments into the interpreter
  -- or receive any values from the interpreter
  = Function_No_Arg theRestOfTheComputation

  -- Arg is known by Function and passed down to the interpreter
  | Function_1_Arg Arg_Passed_to_Interpreter theRestOfTheComputation
  | Function_2_Args Arg1 Arg2 theRestOfTheComputation

  -- `Value` is provided by the interpreter
  -- when it finishes interpreting the language
  | Get_1_Value (Value_Provided_By_Interpreter -> theRestOfTheComputation)
  | Get_2_Values (Value1 -> Value2 -> theRestOfTheComputation)

  -- Use both
  | Function_With_Getter Arg_Passed_to_Interpreter (Value_Provided_By_Interpreter -> theRestOfTheComputation)

So far, we've only defined a data type with one value and composed those data types together. However, what if we treated a data type as a "family" of operations where each value in that data type was an operation? Then our data types might look like this:

-- A "language" that supports the capabilities of reading from
-- a file and writing to a file
data FileSystem a
  = ReadFromFile FilePath (ContentsOfFile -> a)
  | WriteToFile FilePath NewContents a

-- A "language" that supports the capabilities of reading from
-- the console and writing to the console
data ConsoleIO a
  = ReadFromConsole (String -> a)
  | WriteToConsole String a
  -- This shouldn't be here, but it will show below how code is usually written
  -- via do notation when either one of these argument types is used
  | WriteThenRead String (String -> a)

Using these data structure, we can "interpret" these non-runnable pure programs into an equivalent runnable impure program (e.g. Effect). Assuming these functions exist...

consoleRead :: Effect String

consoleWrite :: String -> Effect Unit

readFromFile :: FilePath -> Effect String

writeToFile :: FilePath -> String -> Effect Unit

... we could take our pure "description" of computations (e.g. Free ConsoleIO a) and "interpret" it into an impure Effect monad:

class Functor f => Exec f where                                      {-
  execAlgebra :: f (Effect a) -> Effect a                            -}
  execAlgebra :: f  Effect    ~> Effect

instance Exec ConsoleIO where
  execAlgebra (ReadFromConsole reply) = do
    -- use the `bind` output from `consoleRead` and pass it into `reply`
    -- which will lift the result back into a `Free (Coproduct ...) a`
    -- which will be lifted into the Monadic type via `pure`.
    -- At a later time in the `fold` process,
    -- the `Free (Coproduct ...) a` will be evaluated again
    -- using `fold execAlgebra expression`,
    -- which will start this loop all over again
    -- until the final output is reached
    result <- consoleRead
    pure (reply result)
  execAlgebra (WriteToConsole msg remainingComputation) = do
    consoleWrite msg
    pure remainingComputation
  execAlgebra (WriteThenRead msg reply) = do
    consoleWrite msg
    input <- consoleRead
    pure (reply input)

{- our "run" function but using the `execAlgebra`
exec :: Exec f => Free f a -> Effect a                          -}
exec :: Exec f => Free f   ~> Effect
exec = foldFree pure execAlgebra

-- assuming we have smart constructors for each of our data types
writeToConsole :: forall f. String -> Free f Unit
writeToConsole msg = liftF $ WriteToConsole msg

-- we exclude FileSystem from this computation
consoleComputation :: Free ConsoleIO a
consoleComputation = do
  writeToConsole "What is your name?"
  name <- readFromConsole
  writeToConsole $ "You wrote" <> name
  writeToConsole "Now exiting."

If this could be run in the REPL, it might look like this:
> exec consoleComputation
What is your name?
[User inputs 'mike']
You wrote mike
Now exiting.


Thus, say we had a program that needed a number of capabilities:

  • read/write to the console
  • random number generation
  • gets current date/time

That program might look something like this:

type Message = String
type Prompt = String
type UserInput = String

-- first language family
data ConsoleIO a
  = WriteToConsole Message a
  | ReadFromConsole Prompt (UserInput -> a)

-- second language family
data RandomNumber a
  = GenerateRandomNumber (Int -> a)

-- Third language family
data DateTime a
  = GetCurrentDateTime (DateTime -> a)

-- We could compose these languages/capabilities together via Coproduct
type Language = Coproduct3 ConsoleIO RandomNumber DateTime
type Program = Free Language

-- We can then define a pure computation using our Free monad
        -- Free (Coproduct3 ConsoleIO RandomNumber DateTime) output
program :: Program output
program = do
  -- imagine we defined smart constructors for each language and term above
  dateTime <- getCurrentDateTime
  writeToConsole $ show dateTime <> ": Input your name:"
  name <- readFromConsole "My name: "
  random <- generateRandomNumber
  let encryptedName = encryptNameWith name random
  dateTime' <- getCurrentDateTime
  writeToConsole $ show dateTime' <> ": Your encrypted name is: " <> encryptedName
  pure encryptedName

-- which does not become "impure" until it's actually interpreted
runProgram :: Effect Unit
runProgram = foldFree go program

  -- pseudo-code below!
  go :: Language ~> Effect
  go =
      (\WriteToConsole msg next) -> do
        Console.log msg
        pure next
      (\ReadFromConsole prompt reply) -> do
        response <- prompt
        pure (reply response)
      -- etc.