Monads want to be Free!

(This post is also available as a YouTube video)!

In last week's article I showed how we can use monad classes to allow limited IO effects in our functions. That is, we can get true IO functionality for something small (like printing to the terminal), without allowing a function to run any old IO action (like reading from the file system). In this way monad classes are the building blocks of Haskell's effect structures.

But there's another idea out there called "free monads". Under this paradigm, we can represent our effects with a data type, rather than a typeclass, and this can be a nicer way to conceptualize the problem. In this article I'll show how to use free monads instead of monad classes in the same Nim game example we used last time.

The "starter" code for this article is on the monad-class branch here.

The "ending" code is on the eff branch.

And here is a pull request showing all the edits we'll make!

Intro to Free Monads

Free monads are kind of like Haskell Lenses in that there are multiple implementations out there for the same abstract concept. I'm going to use the Freer Effects library. If you use a different implementation, the syntax details might be a bit different, but the core ideas should still be the same.

The first thing to understand about using free monads, at least with this library, is that there's only a single monad, which we call the Eff monad. And to customize the behavior of this monad, it's parameterized by a type level list containing different effects. Now, we can treat any monad like an effect. So we can construct an instance of this Eff monad that contains the State monad over our game state, as well as the IO monad.

playGame :: Eff '[State (Player, Int), IO ] Player

Now in order to use monadic functionality within our Eff monad, we have the use the send function. So let's write a couple helpers for the state monad to demonstrate this.

getState :: (Member (State (Player, Int)) r) => Eff r (Player, Int)
getState = send (get :: State (Player, Int) (Player, Int))

putState :: (Member (State (Player, Int)) r) => (Player, Int) -> Eff r ()
putState = send . (put :: (Player, Int) -> State (Player, Int) ())

Whereas a typical monad class function won't specify the complete monad m, in this case, we won't specify the complete effect list. We'll just call it r. But then we'll place what is called a Member constraint on this function. We'll say that State (Player, Int) must be a "member" of the effect list r. Then we can just use send in conjunction with the normal monadic functions. We can also add in some type specifiers to make things more clear for the compiler.

Creating an Effect Type

But now let's think about our MonadTerminal class from last time. This doesn't correspond to a concrete monad, so how would we use it? The answer is that instead of using a typeclass, we're going to make a data type representing this effect, called Terminal. This will be a generalized algebraic data type, or GADT. So its definition actually kind of does look like a typeclass. Notice this seemingly extra a parameter as part of the definition.

data Terminal a where
  LogMessage :: String -> Terminal ()
  GetInputLine :: Terminal String

Now we capitalized our function names to make these data constructors. So let's write functions now under the original lowercase names that will allow us to call these constructors. These functions will look a lot like our state functions. We'll say that Terminal must be a member of the type list r. And then we'll just use send except we'll use it with the appropriate constructor for our effect type.

logMessage :: (Member Terminal r) => String -> Eff r ()
logMessage = send . LogMessage

getInputLine :: (Member Terminal r) => Eff r String
getInputLine = send GetInputLine

Interpretations

At this point, you're probably wondering "hmmmm...when do we make these functions concrete"? After all, we haven't used putStrLn yet or anything like that. The answer is that we write an interpretation of the effect type, using a particular monad. This function will assume that our Terminal effect is on top of the effect stack, and it will "peel" that layer off, returning an action that no longer has the effect on the stack.

We call this function runTerminalIO because for this interpretation, we'll assume we are using the IO monad. And hence we will add a constraint that the IO monad is on the remaining stack r.

runTerminalIO :: (Member IO r) => Eff (Terminal ': r) a -> Eff r a
runTerminalIO = ...

To fill in this function, we create a natural transformation between a Terminal action and an IO action. For the LogMessage constructor of course we'll use putStrLn, and for GetInputLine we'll use getLine.

runTerminalIO :: (Member IO r) => Eff (Terminal ': r) a -> Eff r a
runTerminalIO = ...
  where
    terminalToIO :: Terminal a -> IO a
    terminalToIO (LogMessage msg) = putStrLn msg
    terminalToIO GetInputLine = getLine

Then to complete the function, we use runNat, a library function, together with this transformation.

runTerminalIO :: (Member IO r) => Eff (Terminal ': r) a -> Eff r a
runTerminalIO = runNat terminalToIO
  where
    terminalToIO :: Terminal a -> IO a
    terminalToIO (LogMessage msg) = putStrLn msg
    terminalToIO GetInputLine = getLine

Interpreting the Full Stack

Now our complete effect stack will include this Terminal effect, the State effect, and the IO monad. This final stack is like our GameMonad. We'll need to write a concrete function to turn this in to a normal IO action.

transformGame :: Eff '[ Terminal, State (Player, Int), IO ] a -> IO a
transformGame = runM . (runNatS (Player1, 0) stateToIO) . runTerminalIO
  where
    stateToIO :: (Player, Int) -> State (Player, Int) a -> IO ((Player, Int), a)
    stateToIO prev act = let (a', nextState) = runState act prev in return (nextState, a')

This function is a bit like our other interpretation function in that it includes a transformation of the state layer. We combine this with our existing runTerminalIO function to get the final interpretation. Instead of runNat, we use runNatS to assign an initial state and allow that state to pass through to other calls.

Final Tweaks

And now there are just a few more edits we need to make. Most importantly, we can change the type signatures of our different functions. They should be in the Eff monad, and for every monad class constraint we used before, we'll now include a Member constraint.

playGame :: Eff '[ Terminal, State (Player, Int), IO ] Player

validateMove :: (Member Terminal r, Member (State (Player, Int)) r) => String -> Eff r (Maybe Int)

promptPlayer :: (Member Terminal r, Member (State (Player, Int)) r) => Eff r ()

readInput :: (Member Terminal r) => Eff r String

That's most all of what we need to do! We also have to change the direct get and put calls to use getState and putState, but that's basically it! We can rebuild and play our game again now!

Conclusion: Effectful Haskell!

Now I know this overview was super quick so I could barely scratch the surface of how free monads work and what their benefits are. If you think these sound really cool though, and you want to learn this concept more in depth and get some hands on experience, you should sign up for our Effectful Haskell Course!

This course will teach you all the ins and outs of how Haskell allows you to structure effects, including how to do it with free monads. You'll get to see how these ideas work in the context of a decently-sized project. Even better is that you can get a 20% discount on it by subscribing to Monday Morning Haskell. So don't miss out, follow that link and get learning today!

Using IO without the IO Monad!

(This post is also available as a YouTube video!)

In last week's article, I explained what effects really are in the context of Haskell and why Haskell's structures for dealing with effects are really cool and distinguish it from other programming languages.

Essentially, Haskell's type system allows us to set apart areas of our code that might require a certain effect from those that don't. A function within a particular monad can typically use a certain effect. Otherwise, it can't. And we can validate this at compile time.

But there seems to be a problem with this. So many of Haskell's effects all sort of fall under the umbrella of the IO monad. Whether that's printing to the terminal, or reading from the file system, using threads and concurrency, connecting over the network, or even creating a new random number generator.

putStrLn :: String -> IO ()
readFile :: FilePath -> IO String
readMVar :: MVar a -> IO a
httpJSON :: (MonadIO m, FromJSON a) => Request -> m (Response a)
getStdGen :: MonadIO m => m StdGen

Now I'm not going to tell you "oh just re-write your program so you don't need as much IO." These activities are essential to many programs. And often, they have to be spread throughout your code.

But the IO monad is essentially limitless in its abilities. If your whole program uses the IO monad, you essentially don't have any of the guarantees that we'd like to have about limiting side effects. If you need any kind of IO, it seems like you have to allow all sorts of IO.

But this doesn't have to be the case. In this article we're going to demonstrate how we can get limited IO effects within our function. That is, we'll write our type signature to allow a couple specific IO actions, without opening the door to all kinds of craziness. Let's see how this works.

An Example Game

Throughout this video we're going to be using this Nim game example I made. You can see all the code in Game.hs.

Our starting point for this article is the instances branch.

The ending point is the monad-class branch.

You can take a look at this pull request to see all the changes we're going to make in this article!

This program is a simple command line game where players are adding numbers to a sum and want to be the one to get to exactly 100. But there are some restrictions. You can't add more than 10, or add a negative number, or add too much to put it over 100. So if we try to do that we get some of these helpful error messages. And then when someone wins, we see who that is.

Our Monad

Now there's not a whole lot of code to this game. There are just a handful of functions, and they mostly live in this GameMonad we created. The "Game Monad" keeps track of the game state (a tuple of the current player and current sum value) using the State monad. Then it also uses the IO monad below that, which we need to receive user input and print all those messages we were seeing.

newtype GameMonad a = GameMonad
  { gameAction :: StateT (Player, Int) IO a
  } deriving (Functor, Applicative, Monad)

We have a couple instances, MonadState, and MonadIO for our GameMonad to make our code a bit simpler.

instance MonadIO GameMonad where
  liftIO action = GameMonad (lift action)

instance MonadState (Player, Int) GameMonad where
  get = GameMonad get
  put = GameMonad . put

Now the drawback here, as we talked about before, is that all these GameMonad functions can do arbitrary IO. We just do liftIO and suddenly we can go ahead and read a random file if we want.

playGame :: GameMonad Player
playGame = do
  promptPlayer
  input <- readInput
  validateResult <- validateMove input
  case validateResult of
    Nothing -> playGame
    Just i -> do
      # Nothing to stop this!
      readResult <- liftIO $ readFile "input.txt"
      ...

Making Our Own Class

But we can change this with just a few lines of code. We'll start by creating our own typeclass. This class will be called MonadTerminal. It will have two functions for interacting with the terminal. First, logMessage, that will take a string and return nothing. And then getInputLine, that will return a string.

class MonadTerminal m where
  logMessage :: String -> m ()
  getInputLine :: m String

How do we use this class? Well we have to make a concrete instance for it. So let's make an instance for our GameMonad. This will just use liftIO and run normal IO actions like putStrLn and getLine.

instance MonadTerminal GameMonad where
  logMessage = liftIO . putStrLn
  getInputLine = liftIO getLine

Constraining Functions

At this point, we can get rid of the old logMessage function, since the typeclass uses that name now. Next, let's think about the readInput expression.

readInput :: GameMonad String
readInput = liftIO getLine

It uses liftIO and getLine right now. But this is exactly the same definition we used in MonadTerminal. So let's just replace this with the getInputLine class function.

readInput :: GameMonad String
readInput = getInputLine

Now let's observe that this function no longer needs to be in the GameMonad! We can instead use any monad m that satisfies the MonadTerminal constraint. Since the GameMonad does this already, there's no effect on our code!

readInput :: (MonadTerminal m) => m String
readInput = getInputLine

Now we can do the same thing with the other two functions. They call logMessage and readInput, so they require MonadTerminal. And they call get and put on the game state, so they need the MonadState constraint. But after doing that, we can remove GameMonad from the type signatures.

validateMove :: (MonadTerminal m, MonadState (Player, Int) m) => String -> m (Maybe Int)
...

promptPlayer :: (MonadTerminal m, MonadState (Player, Int) m) => m ()
...

And now these functions can no longer use arbitrary IO! They're still using using the true IO effects we wrote above, but since MonadIO and GameMonad aren't in the type signature, we can't just call liftIO and do a file read.

Of course, the GameMonad itself still has IO on its Monad stack. That's the only way we can make a concrete implementation for our Terminal class that actually does IO!

But the actual functions in our game don't necessarily use the GameMonad anymore! They can use any monad that satisfies these two classes. And it's technically possible to write instances of these classes that don't use IO. So the functions can't use arbitrary IO functionality! This has a few different implications, but it especially gives us more confidence in the limitations of what these functions do, which as a reminder, is considered a good thing in Haskell! And it also allows us to test them more easily.

Conclusion: Effectful Haskell

Hopefully you think at least that this is a cool idea. But maybe you're thinking "Woah, this is totally game changing!" If you want to learn more about Haskell's effect structures, I have an offer for you!

If you head to this page you'll learn about our Effectful Haskell course. This course will give you hands-on experience working with the ideas from this video on a small but multi-functional application. The course starts with learning the different layers of Haskell's effect structures, and it ends with launching this application on the internet.

It's really cool, and if you've read this long, I think you'll enjoy it, so take a look! As a bonus, if you subscribe to Monday Morning Haskell, you can get a code for 20% off on this or any of our courses!

Hidden Identity: Using the Identity Monad

Last week we announced our new Making Sense of Monads course. If you subscribe to our mailing list in the next week, you can get a special discount for this and our other courses! So don't miss out!

But in the meantime, we've got one more article on monads! Last week, we looked at the "Function monad". This week, we're going to explore another monad that you might not think about as much. But even if we don't specifically invoke it, this monad is actually present quite often, just in a hidden way! Once again, you can watch the video to learn more about this, or just read along below!

On its face, the identity monad is very simple. It just seems to wrap a value, and we can retrieve this value by calling runIdentity:

newtype Identity a = Identity { runIdentity :: a }

So we can easily wrap any value in the Identity monad just by calling the Identity constructor, and we can unwrap it by calling runIdentity.

We can write a very basic instance of the monad typeclass for this type, that just incorporates wrapping and unwrapping the value:

instance Monad Identity where
  return = Identity
  (Identity a) >>= f = f a

A Base Monad

So what's the point or use of this? Well first of all, let's consider a lot of common monads. We might think of Reader, Writer and State. These all have transformer variations like ReaderT, WriterT, and StateT. But actually, it's the "vanilla" versions of these functions that are the variations!

If we consider the Reader monad, this is actually a type synonym for a transformer over the Identity monad!

type Reader a = ReaderT Identity a

In this way, we don't need multiple abstractions to deal with "vanilla" monads and their transformers. The vanilla versions are the same as the transformers. The runReader function can actually be written in terms of runReaderT and runIdentity:

runReader :: Reader r a -> r -> a
runReader action = runIdentity . (runReaderT action)

Using Identity

Now, there aren't that many reasons to use Identity explicitly, since the monad encapsulates no computational strategy. But here's one idea. Suppose that you've written a transformation function that takes a monadic action and runs some transformations on the inner value:

transformInt :: (Monad m) => m Int -> m (Double, Int)
transformInt action = do
  asDouble <- fromIntegral <$> action
  tripled <- (3 *) <$> action
  return (asDouble, tripled)

You would get an error if you tried to apply this to a normal unwrapped value. But by wrapping in Identity, we can reuse this function!

>> transformInt 5
Error!
>> transformInt (Identity 5)
Identity (5.0, 15)

We can imagine the same thing with a function constraint using Functor or Applicative. Remember that Identity belongs to these classes as well, since it is a Monad!

Of course, it would be possible in this case to write a normal function that would accomplish the simple task in this example. But no matter how complex the task, we could write a version relying on the Identity monad that will always work!

transformInt' :: Int -> (Double, Int)
transformInt' = runIdentity . transformToInt . Identity

...

>> transformInt' 5
(5.0, 15)

The Identity monad is just a bit of trivia regarding monads. If you've been dying to learn how to really use monads in your own programming, you should sign up for our new course Making Sense of Monads! For the next week you can subscribe to our mailing list and get a discount on this course as well as our other courses!

Making Sense of Monads!

We have a special announcement this week! We have a new course available at Monday Morning Haskell Academy! The course is called Making Sense of Monads, and as you might expect, it tackles the concept of monads! It's a short, one module course, but it goes into a good amount of detail about this vital topic, and includes a couple challenge projects at the end. Sign up here!. If you subscribe to our mailing list, you can get a special discount on this and our other courses!

In addition to this, we've also got some new blog content! Once again, there's a video, but you can also follow along by scrolling down!

Last week we discussed the function application operator, which I used for a long time as a syntactic crutch without really understanding it. This week we'll take another look at a function-related concept, but we'll relate it to our new monads course. We're going to explore the "function monad". That is, a single-argument function can act as a monad and call other functions which take the same input in a monadic fashion. Let's see how this works!

The Structure of Do Syntax

Let's start by considering a function in a more familiar monad like IO. Here's a function that queries the user for their name and writes it to a file.

ioFunc :: IO ()
ioFunc = do
  putStrLn "Please enter your name"
  name <- getLine
  handle <- openFile "name.txt" WriteMode
  hPutStrLn handle name
  hClose handle

Do syntax has a discernable structure. We can see this when we add all the type signatures in:

ioFunc :: IO String
ioFunc = do
  putStrLn "Please enter your name" :: IO ()
  (name :: String) <- getLine :: IO String
  (handle :: Handle) <- openFile "name.txt" WriteMode :: IO Handle
  hPutStrLn handle name :: IO ()
  hClose handle :: IO ()
  return name :: IO String

Certain lines have no result (returning ()), so they are just IO () expressions. Other lines "get" values using <-. For these lines, the right side is an expression IO a and the left side is the unwrapped result, of type a. And then the final line is monadic and must match the type of the complete expression (IO String in this case) without unwrapping it's result.

Here's how we might expression that pattern in more general terms, with a generic monad m:

combine :: a -> b -> Result

monadFunc :: m Result
monadFunc = do
  (result1 :: a) <- exp1 :: m a
  (result2 :: b) <- exp2 :: m b
  exp3 :: m ()
  return (combine result1 result2) :: m Result

Using a Function

It turns out there is also a monad instance for (->) r, which is to say, a function taking some type r. To make this more concrete, let's suppose the r type is Int. Let's rewrite that generic expression, but instead of expressions like m Result, we'll instead have Int -> Result.

monadFunc :: Int -> Result
monadFunc = do
  (result1 :: a) <- exp1 :: Int -> a
  (result2 :: b) <- exp2 :: Int -> b
  exp3 :: Int -> ()
  return (combine result1 result2) :: Int -> Result

So on the right, we see an expression "in the monad", like Int -> a. Then on the left is the "unwrapped" expression, of type a! Let's make this even more concrete! We'll remove exp3 since the function monad can't have any side effects, so a function returning () can't do anything the way IO () can.

monadFunc :: Int -> Int
monadFunc = do
  result1 <- (+) 5
  result2 <- (+) 11
  return (result1 * result2)

And we can run this function like we could run any other Int -> Int function! We don't need a run function like some other functions (Reader, State, etc.).

>> monadFunc 5
160
>> monadFunc 10
315

Each line of the function uses the same input argument for its own input!

Now what does return mean in this monadic context? Well the final expression we have there is a constant expression. It must be a function to fit within the monad, but it doesn't care about the second input to the function. Well this is the exact definition of the const expression!

const :: a -> b -> a
const a _ = a -- Ignore second input!

So we could replace return with const and it would still work!

monadFunc :: Int -> Int
monadFunc = do
  result1 <- (+) 5
  result2 <- (+) 11
  const (result1 * result2)

Now we could also use the implicit input for the last line! Here's an example where we don't use return:

monadFunc :: Int -> Int
monadFunc = do
  result1 <- (+) 5
  result2 <- (+) 11
  (+) (result1 * result2)
...

>> monadFunc 5
165
>> monadFunc 10
325

And of course, we could define multiple functions in this monad and call them from one another:

monadFunc2 :: Int -> String
monadFunc2 = do
  result <- monadFunc
  showInput <- show
  const (show result ++ " " ++ showInput)

Like a Reader?

So let's think about this monad more abstractly. This monadic unit gives us access to a single read-only input for each computation. Does this sound familiar to you? This is actually exactly like the Reader monad! And, in fact, there's an instance of the MonadReader typeclass for the function monad!

instance MonadReader r ((->) r) where
...

So without changing anything, we can actually call Reader functions like local! Let's rewrite our function from above, except double the input for the call to monadFunc:

monadFunc2 :: Int -> String
monadFunc2 = do
  result <- local (*2) monadFunc
  showInput <- show
  const (show result ++ " " ++ showInput)

...

>> func2 5
"325 5"
>> func2 10
"795 10"

This isomorphism is one reason why you might not use the function monad explicitly so much. The Reader monad is a bit more canonical and natural. But, it's still useful to have this connection in mind, because it might be useful if you have a lot of different functions that take the same input!

If you're not super familiar with monads yet, hopefully this piqued your interest! To learn more, you can sign up for Making Sense of Monads! And if you subscribe to Monday Morning Haskell you can get a special discount, so don't wait!

Advanced Search with Drilling!

In last week's article we explored how we can make an AI for our main player character. This meant we could play the game without input from a user. The game can now "play itself", and churn out a lot of iterations and results. This, in turn, will let us test combinations of parameters so we can make levels that are challenging.

Our AI is still a little too simplistic. The version we made last week doesn't incorporate the drill feature at all. So this week, let's see if we can devise a way to use that. We'll start with some of the search algorithm ideas we're already using for BFS, and expand from there.

For this article, you'll want to look at the player-ai-drill branch on our Github Repository. It has the full implementation, and you can check the newest commits to see what has changed.

This article will depend a lot on our knowledge of monads, particularly the state monad. If you're newer to Haskell development, you should check out our series on Functional Data Structures. It'll help you understand this tricky concept better.

Updating Our Types

Once again, there are a few quick updates we'll want to make before we start writing our AI. Last week we wrote our main function using this type:

data MoveChoice =
  MoveUp |
  MoveRight |
  MoveDown |
  MoveLeft |
  StandStill

data PlayerMove = PlayerMove
  { playerMoveChoice :: MoveChoice
  , activateStun :: Bool
  }

makePlayerMove :: World -> PlayerMove
...

First we'll change the original type to be MoveDirection. Then to account for the drill powerup, we'll add another field using this type:

data MoveDirection =
  DirectionUp |
  DirectionRight |
  DirectionDown |
  DirectionLeft |
  DirectionNone

data PlayerMove = PlayerMove
  { playerMoveDirection :: MoveDirection
  , activateStun :: Bool
  , drillDirection :: MoveDirection
  }

So we can start out by using DirectionNone for the drill every time, and ensure our game works.

Modifying the World

With the new potential to use the drill to change our world, we'll want another modifier function. This will reuse a lot of old code from our player input section.

modifyWorldForDrill :: World -> MoveDirection -> World

To start, we'll refactor our drillLocation function to be a top level function. Nothing much has to change with its implementation. Let's recall its type signature:

drillLocation
  :: (CellBoundaries -> BoundaryType)
  -> (CellBoundaries -> CellBoundaries)
  -> (CellBoundaries -> CellBoundaries)
  -> World
  -> World

Now our player modifier is pretty straightforward. We'll do a case analysis of the desired direction, as we do with the input keys. This gives us all the necessary inputs to drillLocation:

modifyWorldForPlayerDrill :: World -> MoveDirection -> World
modifyWorldForPlayerDrill w drillDirection = case drillDirection of
  DirectionUp ->
      drillLocation upBoundary breakUpWall breakDownWall w
  DirectionRight ->
      drillLocation rightBoundary breakRightWall breakLeftWall w
  DirectionDown ->
      drillLocation downBoundary breakDownWall breakUpWall w
  DirectionLeft ->
      drillLocation leftBoundary breakLeftWall breakRightWall w
  DirectionNone -> w

And now working this into our update function is easy. It's just another function we have to compose with the other options. We'll apply the drill as the first step, even before the stun:

updateWorldForPlayerMove :: World -> World
updateWorldForPlayerMove w = if shouldMovePlayer
  then worldAfterMove
  else w
  where
    ...
    move = makePlayerMove w

    worldAfterDrill =
        modifyWorldForPlayerDrill w (drillDirection move)

    worldAfterStun = if activateStun move
      then modifyWorldForStun worldAfterDrill
      else worldAfterDrill

    … -- Apply move

Changing the AI

Now let's get cracking on a better algorithm! The good news is that we can still stick to breadth first search. But what needs to change is the items in our search queue. There's a certain amount of state involved in each path we take. Before, we know that if a path backtracks onto a previous location, it will be slower. But now, we can have a faster path coming over a previous square IF we do so with more drills. But each time we take a drill, we need to remove it from the map (from the point of view of this path). Otherwise we could keep picking up the same drill! Thus a "search item", as we'll call it, must also contain the number of drills we have as well as the set of drill power-ups existing on the map. This item has all the important world state for our player moving around the map.

type DrillSearchItem = (Location, Word, Set.Set Location)

Then the other obvious change is that we can go to more adjacent squares. As long as the drill count is at least one, we can go to any adjacent tile. We'll see how this factors into our algorithm below.

Re-Doing BFS

We're going to mimic our original BFS algorithm for the most part when it comes to the drilling version. First, let's reconsider our notion of "adjacent" cells. Remember this function from BFS?

getAdjacentLocations :: Maze -> Location -> [Location]

We now want to re-write it using our DrillSearchItem alias.

getDrillAdjacentItems :: Maze -> DrillSearchItem -> [DrillSearchItem]

In the previous version, we had a section dedicated to checking the bounds around the given location. Then we could see which locations are adjacent. We'll want a similar section for drilling, but we want to use walls as well, as long as we have at least one drill. So let's pattern match on our current item, and gather the locations we can use. We'll also use a boolean to denote if we used a drill to get to that location.

getDrillAdjacentItems :: Maze -> DrillSearchItem -> [DrillSearchItem]
getDrillAdjacentItems maze (location, drillsRemaining, drillLocs) =
  …
  where
    canDrill = drillsRemaining > 0

    maybeUpLoc = case upBoundary bounds of
      (AdjacentCell loc) -> Just (loc, False)
      (Wall loc) -> if canDrill then Just (loc, True) else Nothing
      _ -> Nothing
    maybeRightLoc = case rightBoundary bounds of
      (AdjacentCell loc) -> Just (loc, False)
      (Wall loc) -> if canDrill then Just (loc, True) else Nothing
      _ -> Nothing
    maybeDownLoc = case downBoundary bounds of
      (AdjacentCell loc) -> Just (loc, False)
      (Wall loc) -> if canDrill then Just (loc, True) else Nothing
      _ -> Nothing
    maybeLeftLoc = case leftBoundary bounds of
      (AdjacentCell loc) -> Just (loc, False)
      (Wall loc) -> if canDrill then Just (loc, True) else Nothing
      _ -> Nothing

Now we want a helper function to convert each of these results into a new DrillSearchItem. If we applied the drill, we'll want to subtract one from the remaining drills count. But then if we go over a drill powerup, we'll increment the count and remove this location from our set:

getDrillAdjacentItems :: Maze -> DrillSearchItem -> [DrillSearchItem]
getDrillAdjacentItems maze (location, drillsRemaining, drillLocs) =
  ...
  where
    ...
    mkItemFromResult :: (Location, Bool) -> DrillSearchItem
    mkItemFromResult (loc, usedDrill) =
      let drillsAfterMove =
        if usedDrill
          then drillsRemaining - 1
          else drillsRemaining

      let (drillsAfterPickup, newDrillLocs) =
        if Set.member loc drillLocs
          then (drillsAfterMove + 1, Set.delete loc drillLocs)
          else (drillsAfterMove, drillLocs)
      in  (loc, drillsAfterPickup, newDrillLocs)

And then finally we apply this function over every Just result in our adjacent items!

getDrillAdjacentItems :: Maze -> DrillSearchItem -> [DrillSearchItem]
getDrillAdjacentItems maze (location, drillsRemaining, drillLocs) =
  mkItemFromResult <$>
   (catMaybes [maybeUpLoc, maybeRightLoc, maybeDownLoc, maybeLeftLoc])
  where
  ...

When we rewrite the other BFS functions, the changes are quite trivial. We'll write a new function for the BFS search, since it will apply the different helper, along with other surface level tweaks. The state stays the same except for using DrillSearchItems:

data DrillBFSState = DrillBFSState
  (Seq.Seq DrillSearchItem)
  (Set.Set DrillSearchItem)
  (Map.Map DrillSearchItem DrillSearchItem)

drillBFS :: Maze -> Location -> State DrillBFSState [Location]

Note that we're still only returning a list of locations. We'll let other functions handle the logic of determining if we used the drill or not. So our final call to this function is pretty clean. It just takes a couple extra arguments for our initial state:

getShortestPathWithDrills
  :: Maze
  -> Word
  -> Set.Set Location
  -> Location
  -> Location
  -> [Location]
getShortestPathWithDrills
  maze numDrills drillLocs initialLocation targetLocation = 
      evalState
          (drillBFS maze targetLocation)
          (DrillBFSState
          (Seq.singleton initialItem)
          (Set.singleton initialItem)
          Map.empty)
  where
    initialItem =
      (initialLocation, numDrills, drillLocs)

Last Touches

Once we've changed our algorithm, we have to make one more change to the makePlayerMove function. We'll examine the shortestPathMoveDirection. This will tell us the location we're supposed to go to next. If this is behind a wall, we know we also have to apply the drill in that direction. If it's an AdjacentCell, the drill is not necessary, so use DirectionNone.

makePlayerMove :: World -> PlayerMove
makePlayerMove w =
  PlayerMove finalMoveDirection useStun drillDirection
  where
    ...
    shortestPath = getShortestPathWithDrills
      maze
      (playerDrillsRemaining currentPlayer)
      (Set.fromList $ worldDrillPowerUpLocations w)
      playerLoc
      (endLocation w)
    shortestPathMoveLocation = if null shortestPath
      then playerLoc
      else (head shortestPath)
    shortestPathMoveDirection =
      getMoveDirection playerLoc shortestPathMoveLocation

    locationBounds = maze Array.! playerLoc


    -- Apply the drill if there's a wall!
    drillDirection = case shortestPathMoveDirection of
      DirectionUp -> case upBoundary locationBounds of
        Wall _ -> DirectionUp
        _ -> DirectionNone
      DirectionRight -> case rightBoundary locationBounds of
        Wall _ -> DirectionRight
        _ -> DirectionNone
      DirectionDown -> case downBoundary locationBounds of
        Wall _ -> DirectionDown
        _ -> DirectionNone
      DirectionLeft -> case leftBoundary locationBounds of
        Wall _ -> DirectionLeft
        _ -> DirectionNone
      DirectionNone -> DirectionNone

      ...

Note that we don't need to perform any checks on whether drilling is viable here. If, for some reason, our AI tells us to use the drill and it's invalid, drillLocation will stop this. Then our function for getting the next location will keep the player stationary.

Now we can go ahead and play the game with the AI enabled. We can see that it uses the drill effectively and makes intelligent choices about where and when to do so. It will sometimes go out of its way to pick up an extra drill if this allows it to make a strategic hole. It's not 100% optimal. For instance, we won't use a drill to break a wall to pick up three hidden drills. But it covers most of the important cases for us.

There is a drawback with our algorithm. The game can actually appear a little choppy, especially at the start of the maze. Because we modified the search state to contain a lot more information, the search space is many times bigger. So it is slower to arrive at solutions, especially when we're far from the end.

There are ways we can make this basic algorithm more efficient. Caching is a good place to start. We recompute a lot of information about distances within the maze every time. But there are also other search approaches we can make that will generally be faster. In the coming weeks, we'll explore some of these options.

Conclusion

But first, we'll take a look next week at how we can now run the game separately from the UI. This will allow us to perform many iterations. We'll measure the AI's success rate under different parameters. We'll see how the size of the maze, the number of enemies, and the number of drills affects that rate. This will give us information we can use to make a better use experience for players.

If you want to learn more about Haskell, you should subscribe to our mailing list! You'll get our monthly newsletter, as well as access to our subscriber resouces! This includes, for instance, our Beginners Checklist, to help you get started!

And last, don't forget to take a look at our Github Repository to see all the code in its final state! For this article, look for the player-ai-drill branch!

Smarter Enemies with BFS!

Last week we added enemies to our maze. These little squares will rove around the maze, and if they touch our character, we have to restart the maze. We made it so that these enemies moved around at random. Thus they're not particularly efficient at getting to us.

This week, we're going to make them much more dangerous! They'll use the breadth first search algorithm to find the shortest path towards our player. We'll use three kinds of data structures from the containers package. So if you want to get a little more familiar with that, this article is a great start! Take a look at our Github Repository to see the full code! Look at the part-6 branch for this article!

We'll also make use of the state monad throughout. If you're still a little uncomfortable with monads, make sure to read our series on them! It'll help you with the basics. By the end you'll know about the state monad and how to use it in conjunction with other monads! If you're new to Haskell, you should also take a look at our Beginners Checklist!

BFS Overview

The goal of our breadth first search will be to return the fastest path from one location to another. We'll be writing this function:

getShortestPath :: Maze -> Location -> Location -> [Location]

It will return all the locations on the path from the initial location to the target location. If there's no possible path, we'll return the empty list. In practice, we'll usually only want to take the first element of this list. But there are use cases for having the whole path that we'll explore later. Here's a basic outline of our algorithm:

1. Keep a queue of locations that we'll visit in the future. At the start, this should contain our starting location.
2. Dequeue the first location (if the queue is empty, return the empty list). Mark this location as visited. If it is our target location, skip to step 5.
3. Find all adjacent locations that we haven't visited/enqueued yet. Put them into the search queue. Mark the dequeued location as the "parent" location for each of these new locations.
4. Continue dequeuing elements and inserting their unvisited neighbors. Stop when we dequeue the target location.
5. Once we have the target location, use the "parents" map to create the full path from start to finish.

Data Structures Galore

Now let's start getting into the details. As we'll see, there are several different data structures we'll need for this! We'll do some of the same things we did for depth first search (the first time around). We'll make a type to represent our current algorithm state. Then we'll make a recursive, stateful function over that type. In this case, we'll want three items in our search state.

1. A set of "visited" cells
2. A queue for cells we are waiting to visit
3. A mapping of cells to their "parent"

And for all three of these, we'll want different structures. Data.Set will suffice for our visited cells. Then we'll want Data.Map for the parent map. For the search queue though, we'll use something that we haven't used on this blog before: Data.Sequence. This structure allows us to add to the back and remove from the front quickly. Here's our search state type:

data BFSState = BFSState
  { bfsSearchQueue :: Seq.Seq Location
  , bfsVisistedLocations :: Set.Set Location
  , bfsParents :: Map.Map Location Location
  }

Before we get carried away with our search function, let's fill in our wrapper function. This will initialize the state with the starting location. Then it will call evalState to get the result:

getShortestPath :: Maze -> Location -> Location -> [Location]
getShortestPath maze initialLocation targetLocation = evalState
  (bfs maze initialLocation targetLocation)
  (BFSState 
    (Seq.singleton initialLocation) 
    (Set.singleton initialLocation) 
    Map.empty)

bfs :: Maze -> Location -> Location -> State BFSState [Location]
bfs = ...

Making Our Search

As with depth first search, we'll start by retrieving the current state. Then we'll ask if the search queue is empty. If it is, this means we've exhausted all possibilities, and should return the empty list. This indicates no path is possible:

bfs :: Maze -> Location -> Location -> State BFSState [Location]
bfs maze initialLocation targetLocation = do
  BFSState searchQueue visitedSet parentsMap <- get
  if Seq.null searchQueue
    then return []
    else do
      ...

Now let's consider the first element in our queue. If it's our target location, we're done. We'll write the exact helper for this part later. But first let's get into the meat of the algorithm:

bfs maze initialLocation targetLocation = do
  BFSState searchQueue visitedSet parentsMap <- get
  if Seq.null searchQueue
    then return []
    else do
      let nextLoc = Seq.index searchQueue 0
      if nextLoc == targetLocation
        then … -- Get results
        else do
          ...

Now our code will actually look imperative, to match the algorithm description above:

1. Get adjacent cells and filter based on those we haven't visited
2. Insert the current cell into the visited set
3. Insert the new cells at the end of the search queue, but drop the current (first) element from the queue as well.
4. Mark the current cell as the "parent" for each of these new cells. The new cell should be the "key", the current should be the value.

There's a couple tricky folds involved here, but nothing too bad. Here's what it looks like:

bfs :: Maze -> Location -> Location -> State BFSState [Location]
bfs maze initialLocation targetLocation = do
  BFSState searchQueue visitedSet parentsMap <- get
  ...
      if nextLoc == targetLocation
        then ...
        else do
              -- Step 1 (Find next locations)
          let adjacentCells = getAdjacentLocations maze nextLoc
              unvisitedNextCells = filter 
                (\loc -> not (Set.member loc visitedSet)) 
                adjacentCells

              -- Step 2 (Mark as visited)
              newVisitedSet = Set.insert nextLoc visitedSet

              -- Step 3 (Enqueue new elements)
              newSearchQueue = foldr
                (flip (Seq.|>))
                -- (Notice we remove the first element!)
                (Seq.drop 1 searchQueue)
                unvisitedNextCells

              -- Step 4
              newParentsMap = foldr
                (\loc -> Map.insert loc nextLoc)
                parentsMap
                unvisitedNextCells

Then once we're done, we'll insert these new elements into our search state. Then we'll make a recursive call to bfs to continue the process!

bfs :: Maze -> Location -> Location -> State BFSState [Location]
bfs maze initialLocation targetLocation = do
  BFSState searchQueue visitedSet parentsMap <- get
  ...
      if nextLoc == targetLocation
        then ...
        else do
              -- Step 1
          let adjacentCells = getAdjacentLocations maze nextLoc
              unvisitedNextCells = filter 
                (\loc -> not (Set.member loc visitedSet)) 
                adjacentCells
              -- Step 2
              newVisitedSet = Set.insert nextLoc visitedSet
              -- Step 3
              newSearchQueue = foldr
                (flip (Seq.|>))
                -- (Notice we remove the first element!)
                (Seq.drop 1 searchQueue)
                unvisitedNextCells
              -- Step 4
              newParentsMap = foldr
                (\loc -> Map.insert loc nextLoc)
                parentsMap
                unvisitedNextCells

          -- Replace the state and make recursive call!
          put (BFSState newSearchQueue newVisitedSet newParentsMap)
          bfs maze initialLocation targetLocation

For the last part of this, we need to consider what happens when we hit our target. In this case, we'll "unwind" the path using the parents map. We'll start with the target location in our path list. Then we'll look up its parent, and append it to the list. Then we'll look up the parent's parent. And so on. We do this recursion (of course).

bfs :: Maze -> Location -> Location -> State BFSState [Location]
bfs maze initialLocation targetLocation = do
  BFSState searchQueue visitedSet parentsMap <- get
  if Seq.null searchQueue
    then return []
    else do
      let nextLoc = Seq.index searchQueue 0
      if nextLoc == targetLocation
        then return (unwindPath parentsMap [targetLocation])
        ...
  where
    unwindPath parentsMap currentPath =
      case Map.lookup (head currentPath) parentsMap of
        Nothing -> tail currentPath
        Just parent -> unwindPath parentsMap (parent : currentPath)

The only cell we should find without a parent is the initial cell. So when we hit this case, we return the trail of the current path (so removing the current cell from it). And that's all!

Modifying the Game

All we have to do to wrap things up is call this function instead of our random function for the enemy movements. We'll keep things a little fresh by having them make a random move about 20% of the time. (We'll make this a tunable parameter in the future). Here's the bit where we keep some randomness, like what we have now:

updateEnemy :: Maze -> Location -> Enemy -> State StdGen Enemy
updateEnemy maze playerLocation e@(Enemy location) =
  if (null potentialLocs)
    then return e
    else do
      gen <- get
      let (randomMoveRoll, gen') = randomR (1 :: Int, 5) gen
      let (newLocation, newGen) = if randomMoveRoll == 1
            then
              let (randomIndex, newGen) =
                randomR (0, (length potentialLocs) - 1) gen'
              in  (potentialLocs !! randomIndex, newGen)
          ...
  where
    potentialLocs = getAdjacentLocations maze location

And in the rest of the cases, we'll call our getShortestPath function!

updateEnemy :: Maze -> Location -> Enemy -> State StdGen Enemy
updateEnemy maze playerLocation e@(Enemy location) =
  if (null potentialLocs)
    then return e
    else do
      gen <- get
      let (randomMoveRoll, gen') = randomR (1 :: Int, 5) gen
      let (newLocation, newGen) = if randomMoveRoll == 1
            then
              let (randomIndex, newGen) =
                randomR (0, (length potentialLocs) - 1) gen'
              in  (potentialLocs !! randomIndex, newGen)
            else
              let shortestPath =
                getShortestPath maze location playerLocation
              in  (if null shortestPath then location 
                     else head shortestPath, gen')
      put newGen
      return (Enemy newLocation)
    where
      potentialLocs = getAdjacentLocations maze location

And now the enemies will chase us around! They're hard to avoid!

Conclusion

With our enemies now being more intelligent, we'll want to allow our player to fight back against them! Next week, we'll create a mechanism to stun the ghosts to give ourselves a better chance! After, we'll look a some other ways to power up our player!

If you've never programmed in Haskell, hopefully this series is giving you some good ideas of the possibilities! We have a lot of resources for beginners! Check out our Beginners Checklist as well as our Liftoff Series!

Common (But not so Common) Monads

Last week we looked at how monads can help you make the next jump in your Haskell development. We went over the runXXXT pattern and how it’s a common gateway for us to use certain monads from the rest of our code. But sometimes it also helps to go back to the basics. I actually went a long time without really grasping how to use a couple basic monads. Or at the very least, I didn’t understand how to use them as monads.

In this article, we’ll look at how to use the list monad and the function monad. Lists and functions are core concepts that any Haskeller learns from the get-go. But the list data structure and function application are also monads! And understanding how they work as such can teach us more about how monads work.

For an in-depth discussion of monads, check out our Functional Data Structures Series!

The General Pattern of Do Syntax

Using do syntax is one of the keys to understanding how to actually use monads. The bind operator makes it hard to track where your arguments are. Do syntax keeps the structure clean and allows you to pass results with ease. Let’s see how this works with IO, the first monad a lot of Haskellers learn. Here’s an example where we read the second line from a file:

readLineFromFile :: IO String
readLineFromFile = do
  handle <- openFile “myFile.txt” ReadMode
  nextLine <- hGetLine handle
  secondLine <- hGetLine handle
  _ <- hClose handle
  return secondLine

By keeping in mind the type signatures of all the IO functions, we can start to see the general pattern of do syntax. Let’s replace each expression with its type:

openFile :: FilePath -> IOMode -> IO Handle
hGetLine :: Handle -> IO String
hClose :: Handle -> IO ()
return :: a -> IO a

readLineFromFile :: IO String
readLineFromFile = do
  (Handle) <- (IO Handle)
  (String) <- (IO String)
  (String) <- (IO String)
  () <- (IO ())
  IO String

Every line in a do expression (except the last) uses the assignment operator <-. Then it has an expression of IO a on the right side, which it assigns to a value of a on the left side. The last line’s type then matches the final return value of this function. What’s important now is to recognize that we can generalize this structure to ANY monad:

monadicFunction :: m c
monadicFunction = do
  (_ :: a) <- (_ :: m a)
  (_ :: b) <- (_ :: m b)
  (_ :: m c)

So for example, if we have a function in the Maybe monad, we can use it and plug that in for m above:

myMaybeFunction :: a -> Maybe a

monadicMaybe :: a -> Maybe a
monadicMaybe x = do
  (y :: a) <- myMaybeFunction x
  (z :: a) <- myMaybeFunction y
  (Just z :: Maybe a)

The important thing to remember is that a monad captures a computational context. For IO, this context is that the computation might interact with the terminal or network. For Maybe, the context is that the computation might fail.

The List Monad

Now to graph the list monad, we need to know its computational context. We can view any function returning a list as non-deterministic. It could have many different values. So if we chain these computations, our final result is every possible combination. That is, our first computation could return a list of values. Then we want to check what we get with each of these different results as an input to the next function. And then we’ll take all those results. And so on.

To see this, let’s imagine we have a game. We can start that game with a particular number x. On each turn, we can either subtract one, add one, or keep the number the same. We want to know all the possible results after 5 turns, and the distribution of the possibilities. So we start by writing our non-deterministic function. It takes a single input and returns the possible game outputs:

runTurn :: Int -> [Int]
runTurn x = [x - 1, x, x + 1]

Here’s how we’d apply on this 5 turn game. We’ll add the type signatures so you can see the monadic structure:

runGame :: Int -> [Int]
runGame x = do
  (m1 :: Int) <- (runTurn x :: [Int])
  (m2 :: Int) <- (runTurn m1 :: [Int])
  (m3 :: Int) <- (runTurn m2 :: [Int])
  (m4 :: Int) <- (runTurn m3 :: [Int])
  (m5 :: Int) <- (runTurn m4 :: [Int])
  return m5

On the right side, every expression has type [Int]. Then on the left side, we get our Int out. So each of the m expressions represents one of the many solutions we'll get from runTurn. Then we run the rest of the function imagining we’re only using one of them. In reality though, we’ll run them all, because of how the list monad defines its bind operator. This mental jump is a little tricky. And it’s often more intuitive to just stick to using where expressions when we do list computations. But it's cool to see patterns like this pop up in unexpected places.

The Function Monad

The function monad is another one I struggled to understand for a while. In some ways, it's the same as the Reader monad. It encapsulates the context of having a single argument we can pass to different functions. But it’s not defined in the same way as Reader. When I tried to grok the definition, it didn’t make much sense to me:

instance Monad ((->) r) where
  return x = \_ -> x
  h >>= f = \w -> f (h w) w

The return definition makes sense. We’ll have a function that takes some argument, ignore that argument, and give the value as an output. The bind operator is a little more complicated. When we bind two functions together, we’ll get a new function that takes some argument w. We’ll apply that argument against our first function ((h w)). Then we’ll take the result of that, apply it to f, and THEN also apply the argument w again. It’s a little hard to follow.

But let’s think about this in the context of do syntax. Every expression on the right side will be a function that takes our type as its only argument.

myFunctionMonad :: a -> (x, y, z)
myFunctionMonad = do
  x <- :: a -> b
  y <- :: a -> c
  z <- :: a -> d
  return (x, y, z)

Now let’s imagine we’ll pass an Int and use a few different functions that can take an Int. Here’s what we’ll get:

myFunctionMonad :: Int -> (Int, Int, String)
myFunctionMonad = do
  x <- (1 +)
  y <- (2 *)
  z <- show
  return (x, y, z)

And now we have valid do syntax! So what happens when we run this function? We’ll call our different functions on the same input.

>> myFunctionMonad 3
(4, 6, "3")
>> myFunctionMonad (-1)
(0, -2, "-1")

When we pass 3 in the first example, we add 1 to it on the first line, multiply it by 2 on the second line, and show it on the third line. And we do this all without explicitly stating the argument! The tricky part is that all your functions have to take the input argument as their last argument. So you might have to do a little bit of argument flipping.

Conclusion

In this article we explored lists and functions, two of the most common concepts in Haskell. We generally don’t use these as monads. But we saw how they still fit into the monadic structure. We can use them in do-syntax, and follow the patterns we already know to make things work.

Perhaps you’ve tried to learn Haskell before but found monads a little too complex. Hopefully this article helped clarify the structure of monads. If you want to get your Haskell journey back under way, download our Beginners Checklist! Or to learn monads from the ground up, read our series on Functional Data Structures!

Making the Jump II: Using More Monads

A few weeks ago, we addressed some important steps to advance past the "beginner" stage of Haskell. We learned how to organize your project and how to find the relevant documentation. This week we’re going to continue to look at another place where we can make a big step up. We’ll explore how to expand our vocabulary on monad usage.

Monads are a vital component of Haskell. You can’t use a lot of libraries unless you know how to incorporate their monadic functions. These functions often involve a monad that is custom to that library. When you’re first starting out, it can be hard to know how to incorporate these monads into the rest of your program.

In this article, we’ll focus on a specific pattern a lot of monads and libraries use. I call this pattern the “run” pattern. Often, you’ll use a function with a name like runXXX or runXXXT, where XXX is the name of the monad. These functions will always take a monadic expression as their first argument. Then they'll also take some other initialization information, and finally return some output. This output can either be in pure form or a different monad you’re already using like IO. We’ll start by seeing how this works with the State monad, and then move onto some other libraries.

Once you grasp this topic, it seems very simple. But a lot of us first learned monads with a bad mental model. For instance, the first thing I learned about monads was that they had side effects. And thus, you can only call them from places that have the same side effects. This applies to IO but doesn’t generalize to other monads. So even though it seems obvious now, I struggled to learn this idea at first. But let's start looking at some examples of this pattern.

For a more in depth look at monads, check out our series on Functional Data Structures! We start by learning about simpler things like functors. Then we eventually work our way up to monads and even monad transformers!

The Basics of “Run”: The State Monad

Let’s start by recalling the State monad. This monad has a single type parameter, and we can access this type as a global read/write state. Here’s an example function written in the State monad:

stateExample :: State Int (Int, Int, Int)
stateExample = do
  a <- get
  modify (+1)
  b <- get
  put 5
  c <- get
  return (a, b, c)

If this function is confusing, you should take a look at the documentation for State. It’ll at least show you the relevant type signatures. First we read the initial state. Then we modify it with some function. Finally we completely change it.

In the example above, if our initial state is 1, we’ll return (1,2,5) as the result. If the initial state is 2, we’ll return (2,3,5). But suppose we have a pure function. How do we call our state function?

pureFunction :: Int -> Int
pureFunction = ???

The answer is the runState function. We can check the documentation and find its type:

runState :: State s a -> s -> (a, s)

This function has two parameters. The first is a State action. We’ll pass our function above as this parameter! Then the second is the initial state, and this is how we’ll configure it. Then the result is pure. It contains our result, as well as the final value of the state. So here’s a sample call we can make that gives us this monadic expression in our pure function. We’ll call it from a where clause, and discard the final state:

pureFunction :: Int -> Int
pureFunction input = a + b + c
  where
    ((a,b,c), _) = runState stateExample input

This is the simplest example of how we can use the runXXX pattern.

Upgrading to Transformers

Now, suppose our State function isn’t quite pure. It now wants to print some of its output, so it’ll need the IO monad. This means it’ll use the StateT monad transformer over IO:

stateTExample :: StateT Int IO (Int, Int, Int)
stateTExample = do
  a <- get
  lift $ print “Initial Value:”
  lift $ print a
  modify (+1)
  b <- get
  lift $ putStrLn “After adding 1:”
  lift $ print b
  put 5
  c <- get
  lift $ putStrLn “After setting as 5:”
  lift $ print c
  return (a, b, c)

Now instead of calling this function from a pure format, we’ll need to call it from an IO function. But once again, we’ll use a runXXX function. Now though, since we’re using a monad transformer, we won’t get a pure result. Instead, we’ll get our result in the underlying monad. This means we can call this function from IO. So let’s examine the type of the runStateT function. We’ve substituted IO for the generic monad parameter m:

runStateT :: StateT s IO a -> s -> IO (a, s)

It looks a lot like runState, except for the extra IO parameters! Instead of returning a pure tuple for the result, it returns an IO action containing that result. Thus we can call it from the IO monad.

main :: IO ()
main = do
  putStrLn “Please enter a number.”
  input <- read <$> getLine
  results <- runStateT stateTExample input
  print results

We’ll get the following output as a result:

Please enter a number.
10
Initial Value:
10
After adding 1
11
After setting as 5
5
(10, 11, 5)

Using Run For Libraries

This pattern will often extend into libraries you use. For example, in our series on parsing, we examine the Megaparsec library. A lot of the individual parser combinators in that library exist in the Parsec or ParsecT monad. So we can combine a bunch of different parsers together into one function.

But then to run that function from your normal IO code (or another monad), you need to use the runParserT function. Let’s look at its type signature:

runParserT
  :: Monad m
  -> ParsecT e s m a
  -> String -- Name of source file
  -> s -- Input for parser
  -> m (Either (ParseError (Token s) e) a)

There are a lot of type parameters there that you don’t need to understand. But the structure is the same. The first parameter to our run function is the monadic action. Then we’ll supply some other inputs we need. Then we get some result, wrapped in an outer monad (such as IO).

We can see the same pattern if we use the servant-client library to make client-side API calls. Any call you make to your API will be in the ClientM monad. Now here’s the type signature of the runClientM function:

runClientM :: ClientM a -> ClientEnv -> IO (Either ServantError a)

So again, the same pattern emerges. We’ll compose our monadic action and pass that as the first parameter. Then we’ll provide some initial state, in this case a ClientEnv. Finally, we’ll get our result (Either ServantError a) wrapped in an outer monad (IO).

Monads Within Expressions

It’s also important to remember that a lot of basic monads work without even needing a runXXX function! For instance, you can use a Maybe or Either monad to take out some of your error handling logic:

divideIfEven :: Int -> Maybe Int
divideIfEven x = if x `mod` 2 == 0
  then Just (x `quot` 2)
  else Nothing

dividesBy8 :: Int -> Bool
dividesBy8 = case thirdResult of
  Just _ -> True
  Nothing -> False
  where
    thirdResult :: Maybe Int
    thirdResult = do
      y <- divideIfEven x
      z <- divideIfEven y
      divideIfEven z

Conclusion

Monads are the key to using a lot of different Haskell libraries. But when you’re first starting out, it can be very confusing how you call into these functions from your code. The same applies with some common monad transformers like Reader and State. The most common pattern to look out for is the runXXXT pattern. Master this pattern and you’re well on your to understanding monads and writing better Haskell!

For a closer look at monads and similar structures, make sure to read our series on Functional Data Structures. If the code in this article was confusing, you should definitely check it out! And if you’ve never written Haskell but want to start, download our Beginners Checklist!

Functors Done Quick!

Suppose we're writing some code to deal with bank accounts. Most of our code will refer to these using a proper data type. But less refined parts of our code might use a tuple with the same information instead. We would want a conversion function to go between them. Here's a simple example:

data BankAccount = BankAccount
  { bankName :: String
  , ownerName :: String
  , accountBalance :: Double
  }

convertAccount :: (String, String, Double) -> BankAccount
convertAccout (bank, owner, balance) = BankAccount bank owner balance

Naturally, we'll want a convenience function for performing this operation on a list of items. We'll can use map for lists.

convertAccounts :: [(String, String, Double)] -> [BankAccount]
convertAccounts = map convertAccount

But Haskell has a plethora of different data structures. We can store our data in a Set, or a Vector, for a couple examples. What if different parts of our code store the data differently? They would need their own conversion functions, since the list version of map doesn't work on a Set or Vector. Can we make this code more generic?

Functors

If you read the blog post a couple weeks ago, you'll remember the idea of typeclasses. This is how we can make our code generic! We want to generalize the behavior of running a transformation over a data structure. We can make a typeclass to encapsulate this behavior. Luckily, Haskell already has such a typeclass, called Functor. It has a single function, fmap. Here is how it is defined:

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

If that type signature looks familiar, that's because it's almost identical to the map function over lists. And in fact, the List type uses map as it's implementation for fmap:

map :: (a  ->  b)  ->  [a]  ->  [b]

instance Functor [] where
  fmap = map

Other Functor Instances

Now, Set and Vector do have map functions. But to make our code generic, we have to define functor instances as a go-between:

instance Functor Vector where
  fmap = Data.Vector.map

instance Functor Set where
  fmap = Data.Set.map

With all this in mind, we can now rewrite convertAccounts generically.

convertAccounts :: (Functor f) => f (String, String, Double)  ->  f BankAccount
convertAccounts = fmap convertAccount

Now anything can use convertAccounts no matter how it structures the data, as long as it uses a functor! Let's looks at some of the other functors out there!

While it might not seem to fit in the same category as lists, vectors and sets, Maybe is also a functor! Here's its implementation:

instance Functor Maybe where
  fmap _ Nothing = Nothing
  fmap f (Just a) = Just (f a)

Another example of a functor is Either. This one is a little confusing since Either has two type parameters. But really, we have to fix the first parameter. Then the conversion function is only applied to the second. This means that, like with the Nothing case above, when we have Left, we return the original value:

instance Functor (Either a) where
  fmap _ (Left a) = Left a
  fmap f (Right x) = Right (f x)

Conceptualizing Functors

So concretely, Functor is a typeclass in Haskell. But how can we think of it conceptually? This is actually pretty simple. A functor is nothing more than a generic container or box. We don't know how many elements it contains. We don't know what the structure of those elements is. But if we have a way to transform those elements, we can apply that function over all of them. The result will be a new container with the same structure, but new elements. As far as abstractions go, this is probably the cleanest one we'll get, so enjoy it!

Conclusion

Functor is an example of typeclass that we can use to get general behavior. In this case, the behavior is transforming a group of objects in a container while maintaining the container's structure. We saw how this typeclass allowed us to re-use a function over many different types. Functors are the simplest in a series of important typeclasses. Applicative functors would come next, and then monads. Monads are vital to Haskell. So understanding functors is an important first step towards learning more complex Haskell.

But you can't learn about data structures until you know the basics! If you've never written any Haskell before, download out Getting Started Checklist! If you're comfortable with the basics and want more of a challenge, take a look at our Recursion Workbook!

Eff to the Rescue!

In the last couple weeks, we’ve seen quite a flurry of typeclasses. We used MonadDatabase and MonadCache to abstract the different effects within our API. This brought with it some benefits, but also some drawbacks. With these concepts abstracted, we could distill the API code into its simpler tasks. We didn't need to worry about connection configurations or lifting through different monads.

As we’ve seen though, there was a lot of boilerplate code involved. And there would be more if we wanted the freedom to have different parts of our app use different monad stacks. Free Monads are one solution to this problem. They allow you to compose your program so that the order in which you specify your effects does not matter. We’ll still have to write “interpretations” as we did before. But now they’ll be a lot more composable.

You can follow along the code for this by checking out the effects-3 branch on Github. Also, I do have to give a shoutout to Sandy Maguire for his talk on Eff and Free monads from BayHac. Most of what I know about free monads comes from that talk. You should also check out his blog as well.

Typeclass Boilerplate

Let’s review the main drawback of our type class approach. Recall our original definition of the AppMonad, and some of the instances we had to write for it:

newtype AppMonad a = AppMonad (ReaderT RedisInfo (SqlPersistT (LoggingT IO)) a)
  deriving (Functor, Applicative, Monad)

instance MonadDatabase AppMonad where
  fetchUserDB = liftSqlPersistT . fetchUserDB
  createUserDB = liftSqlPersistT . createUserDB
  deleteUserDB = liftSqlPersistT . deleteUserDB
  fetchArticleDB = liftSqlPersistT . fetchArticleDB
  createArticleDB = liftSqlPersistT . createArticleDB
  deleteArticleDB = liftSqlPersistT . deleteArticleDB
  fetchArticlesByAuthor = liftSqlPersistT . fetchArticlesByAuthor
  fetchRecentArticles = liftSqlPersistT fetchRecentArticles

liftSqlPersistT :: SqlPersistT (LoggingT IO) a -> AppMonad a
liftSqlPersistT action = AppMonad $ ReaderT (const action)

instance (MonadIO m, MonadLogger m) => MonadDatabase (SqlPersistT m) where
  ...

But suppose another part of our application wants to use a different monad stack. Perhaps it uses different configuration information and tracks different state. But it still needs to be able to connect to the database. As a result, we’ll need to write more instances. Each of these will need a new definition for all the different effect functions. Most all these will be repetitive and involve some combination of lifts. This isn’t great. Further, suppose we want arbitrary reordering of the monad stack. The number of instances you’ll have to write scales quadratically. Once you get to six or seven layers, this is a real pain.

Main Ideas of Eff

We can get much better composability by using free monads. I’m not going to get into the conceptual details of free monads. Instead I’ll show how to implement them using the Eff monad from the Freer Effects library. Let's first think back to how we define constraints on monads in our handler functions.

fetchUsersHandler :: (MonadDatabase m, MonadCache m) => Int64 -> m User

We take some generic monad, and constrain it to implement our type classes. With Eff, we’ll specify constraints in a different way. We have only one monad, the Eff monad. This monad is parameterized by a type-level list of other monads that it carries on its stack.

type JustIO a = Eff ‘[IO] a

type ReaderWithIO a = Eff ‘[Reader RedisInfo, IO] a

With this in mind, we can specify constraints on what monads are part of our stack using Member. Here’s how we’ll re-write the type signature from above:

fetchUsersHandler :: (Member Database r, Member Cache r) => Int64 -> Eff r User

We’ll specify exactly what Database and Cache are in the next section. But in essence, we’re stating that we have these two kinds of effects that live somewhere on our monad stack r. It doesn’t matter what order they’re in! This gives us a lot of flexibility. But before we see why, let’s examine how we actually write these effects.

Coding Up Effects

The first thing we’ll do is represent our effects as data types, rather than type classes. Starting with our database functionality, we’ll make a type Database a. This type will have one constructor for each function from our MonadDatabase typeclass. We’ll capitalize the names since they’re constructors instead of functions names. Then we’ll use GADT syntax, so that the result will be of type Database instead of a function in a particular monad. To start, here’s what our FetchUserDB constructor looks like:

{-# LANGUAGE GADTs #-}

data Database a where
  FetchUserDB :: Int64 -> Database (Maybe User)
  ...

Our previous definition looked like Int64 -> m (Maybe User). But we’re now constructing a Database action. Here’s the rest of the definition:

data Database a where
  FetchUserDB :: Int64 -> Database (Maybe User)
  CreateUserDB :: User -> Database Int64
  DeleteUserDB :: Int64 -> Database ()
  FetchArticleDB :: Int64 -> Database (Maybe Article)
  CreateArticleDB :: Article -> Database Int64
  DeleteArticleDB :: Int64 -> Database ()
  FetchArticlesByAuthor :: Int64 -> Database [KeyVal Article]
  FetchRecentArticles :: Database [(KeyVal User, KeyVal Article)]

Now we can also do the same thing with a Cache type instead of our MonadCache class:

data Cache a where
  CacheUser :: Int64 -> User -> Cache ()
  FetchCachedUser :: Int64 -> Cache (Maybe User)
  DeleteCachedUser :: Int64 -> Cache ()

Now, unfortunately, we do need some boilerplate with Eff. For each of constructor we create, we’ll need a function to run that item within the Eff monad. For these, we’ll use the send function from the Eff library. Each function states that our effect type is a member of our monad set. Then it will otherwise match the type of that constructor, only within the Eff monad. Here are the three examples for our Cache type.

cacheUser :: (Member Cache r) => Int64 -> User -> Eff r ()
cacheUser uid user = send $ CacheUser uid user

fetchCachedUser :: (Member Cache r) => Int64 -> Eff r (Maybe User)
fetchCachedUser = send . FetchCachedUser

deleteCachedUser :: (Member Cache r) => Int64 -> Eff r ()
deleteCachedUser = send . DeleteCachedUser

But wait! You might be asking, aren’t we trying to avoid boilerplate? Well, it’s hard to avoid all boilerplate. But the real gain we’ll get is that our boilerplate will scale in a linear fashion. We only need this code once per effect type we create. Remember, the alternative is quadratic growth.

Interpreting our Effects

To write "interpretations" of our effects in the type class system, we wrote instances. Here, we can do it with functions that we'll prefix with run. These will assume we have an action where our effect is on "top" of the monad stack. The result will be a new action with that layer peeled off.

runDatabase :: Eff (Database ': r) a -> Eff r a
runDatabase = ...

Now, we have to consider, what would be necessary to run our database effects? For our production application, we need to know that SqlPersistT lives in the monad stack. So we’ll add (SqlPersistT (LoggingT IO)) as a constraint on the rest of the r for our monad.

runDatabase :: (Member (SqlPersistT (LoggingT IO)) r) => Eff (Database ': r) a -> Eff r a

So we are in effect constraining the ordering of our monad, but doing it in a logical way. It wouldn’t make sense for us to ever run our database effects without knowing about the database itself.

To write this function, we specify a transformation between this Member of the rest of our stack and our Database type. We can run this transformation with runNat:

runDatabase :: (Member (SqlPersistT (LoggingT IO)) r) => Eff (Database ': r) a -> Eff r a
runDatabase = runNat databaseToSql
  where
    databaseToSql :: Database a -> SqlPersistT (LoggingT IO) a
    ...

Now we need a conversion between a Database object and a SqlPersistT action. For this, we plug in all the different function definitions we’ve been using all along. For instance, here’s what our fetchUserDB and createDB definitions look like:

databaseToSql (FetchUserDB uid) = get (toSqlKey uid)
databaseToSql (CreateUserDB user) = fromSqlKey <$> insert user

Our other constructors will follow this pattern as well.

Now, we’ll also want a way to interpret SqlPersistT effects within Eff. We’ll depend on only having IO as a deeper member within the stack here, though we also need the PGInfo parameter. Then we use runNat and convert between our SqlPersistT action and a normal IO action. We’ve done this before with runPGAction:

runSqlPersist :: (Member IO r) => PGInfo -> Eff ((SqlPersistT (LoggingT IO)) ': r) a -> Eff r a
runSqlPersist pgInfo = runNat $ runPGAction pgInfo

We go through this same process with Redis and our cache. To run a Redis action from our monad stack, we have to take the RedisInfo as a parameter and then also have IO on our stack:

runRedisAction :: (Member IO r) => RedisInfo -> Eff (Redis ': r) a -> Eff r a
runRedisAction redisInfo = runNat redisToIO
  where
    redisToIO :: Redis a -> IO a
    redisToIO action = do
      connection <- connect redisInfo
      runRedis connection action

Once we have this transformation, we can use the dependency on Redis to run Cache actions.

runCache :: (Member Redis r) => Eff (Cache ': r) a -> Eff r a
runCache = runNat cacheToRedis
  where
    cacheToRedis :: Cache a -> Redis a
    cacheToRedis (CacheUser uid user) = void $ setex (pack . show $ uid) 3600 (pack . show $ user)
    cacheToRedis (FetchCachedUser uid) = do
      result <- get (pack . show $ uid)
      case result of
        Right (Just userString) -> return $ Just (read . unpack $ userString)
        _ -> return Nothing
    cacheToRedis (DeleteCachedUser uid) = void $ del [pack . show $ uid]

And now we're done with our interpretations!

A Final Natural Transformation

Since we’re using Servant, we’ll still have to pick a final ordering. We need a natural transformation from Eff to Handler. Thus we'll specify a specific order so we have a specific Eff. We’ll put our cache effects on the top of our stack, then database operations, and finally, plain old IO.

transformEffToHandler ::
  PGInfo ->
  RedisInfo ->
  (Eff '[Cache, Redis, Database, SqlPersistT (LoggingT IO), IO]) :~> Handler

So how do we define this transformation? As always, we’ll want to create an IO action that exposes an Either value so we can catch errors. First, we can use our different run functions to peel off all the layers on our stack until all we have is IO:

transformEffToHandler ::
  PGInfo ->
  RedisInfo ->
  (Eff '[Cache, Redis, Database, SqlPersistT (LoggingT IO), IO]) :~> Handler
transformEffToHandler pgInfo redisInfo = NT $ \action -> do
  -- ioAct :: Err ‘[IO] a
  let ioAct = (runSqlPersist pgInfo . runDatabase . runRedisAction redisInfo . runCache) action
  ...

When we only have a single monad on our stack, we can use runM to get an action in that monad. So we need to apply that to our action, handle errors, and return the result as a Handler!

transformEffToHandler ::
  PGInfo ->
  RedisInfo -> 
  (Eff '[Cache, Redis, Database, SqlPersistT (LoggingT IO), IO]) :~> Handler
transformEffToHandler pgInfo redisInfo = NT $ \action -> do
  let ioAct = (runSqlPersist pgInfo . runDatabase . runRedisAction redisInfo . runCache) action
  result <- liftIO (runWithServantHandler (runM ioAct))
  Handler $ either throwError return result

And with that we’re done! Here’s the big win with Eff. It’s quite easy for us to write a different transformation on a different ordering of the Stack. We just change the order in which we apply our run functions!

-- Put Database on top instead of Cache
transformEffToHandler :: 
  PGInfo -> 
  RedisInfo -> 
  (Eff '[Database, SqlPersistT (LoggingT IO), Cache, Redis, IO]) :~> Handler
transformEffToHandler pgInfo redisInfo = NT $ \action -> do
  let ioAct = (runRedisAction redisInfo . runCache . runSqlPersist pgInfo . runDatabase) action
  result <- liftIO (runWithServantHandler (runM ioAct))
  Handler $ either throwError return result

Can we avoid outside services with this approach? Sure! We can specify test interpretations of our effects that don’t use SqlPersistT or Redis. We’ll still have IO for reasons mentioned last week, but it’s still an easy change. We'll define separate runTestDatabase and runTestCache functions that use the same effects we saw last week. They’ll depend on using the State over our in-memory maps.

runTestDatabase :: 
  (Member (StateT (UserMap, ArticleMap, UserMap) IO) r) => 
  Eff (Database ': r) a -> 
  Eff r a
runTestDatabase = runNat databaseToState
  where
    databaseToState :: Database a -> StateT (UserMap, ArticleMap, UserMap) IO a
    …

runTestCache ::
  (Member (StateT (UserMap, ArticleMap, UserMap) IO) r) =>
  Eff (Cache ': r) a ->
  Eff r a
runTestCache = runNat cacheToState
  where
    cacheToState :: Cache a -> StateT (UserMap, ArticleMap, UserMap) IO a
    ...

Then we fill in the definitions with the same functions we used when writing our TestMonad. After that, we define another natural transformation, in the same pattern:

transformTestEffToHandler ::
  MVar (UserMap, ArticleMap, UserMap) ->
  Eff '[Cache, Database, StateT (UserMap, ArticleMap, UserMap) IO] :~> Handler
transformTestEffToHandler sharedMap = NT $ \action -> do
  let stateAct = (runTestDatabase . runTestCache) action
  result <- liftIO (runWithServantHandler (runEff stateAct))
  Handler $ either throwError return result
  where
    runEff :: Eff '[StateT (UserMap, ArticleMap, UserMap) IO] a -> IO a
    runEff action = do
      let stateAction = runM action
      runStateTWithPointer stateAction sharedMap

Incorporating our Interpretations

The final step we’ll take is to change a couple different type signatures within our API code. We’ll pass a new natural transformation to our Server function:

fullAPIServer :: 
  ((Eff '[Cache, Redis, Database, SqlPersistT (LoggingT IO), IO]) :~> Handler) ->
  Server FullAPI
fullAPIServer nt = ...

And then we’ll change all our handlers to use Eff with the proper members, instead of AppMonad:

fetchUsersHandler :: (Member Database r, Member Cache r) => Int64 -> Eff r User
createUserHandler :: (Member Database r) => User -> Eff r Int64
fetchArticleHandler :: (Member Database r) => Int64 -> Eff r Article
createArticleHandler :: (Member Database r) => Article -> Eff r Int64
fetchArticlesByAuthorHandler :: (Member Database r) => Int64 -> Eff r [KeyVal Article]
fetchRecentArticlesHandler :: (Member Database r) => Eff r [(KeyVal User, KeyVal Article)]

Conclusion

We’ve come a long way with our small application. It doesn’t do much. But it has served as a great launchpad for learning many interesting libraries and techniques. In particular, we’ve seen in these last few weeks how to organize effects within our application. With the Eff library, we can represent our effects with data types that we can re-order with ease.

If you’ve never tried Haskell before, give it a shot! Download our Getting Started Checklist and get going!

If you’ve done a little Haskell but aren’t set on your skills yet, maybe this article went over your head. That’s OK! You can work on your skills more with our Recursion Workbook!

A Different Point of View: Interpreting our Monads Without Outside Services

Last week we updated our API to use some interesting monadic constructs. These allowed us to narrow down the places where effects could happen in our application. This week we’ll examine another advantage of this system. We’ll examine how we can simplify our tests and remove the dependency on outside services.

You can follow along this code by looking at the effects-2 branches on the Github repository. In effects-2-start, we’ve updated our tests to use the AppMonad instead of normal IO functions. We can still do better though (see the effects-2-end branch for the final product). We can create a second monad that implements our MonadDatabase and MonadCache classes. This creates what we call a different interpretation of our effects. We can do this in such a way that they don’t rely on running instances of Postgres and Redis.

Re-Imagining our Monad

Let’s imagine the simplest possible way to have a “database”. Instead of using a remote service, we could use in-memory maps. So let’s start with a couple type synonyms:

type UserMap = Map.Map Int64 User
type ArticleMap = Map.Map Int64 Article

There are three different maps in our application. The first map will be our normal Users table from the database. The second map will be the database’s Article table. The third map will refer to our Users cache. Now we’ll create a monad that links all these different elements together, and wraps them in StateT. We’ll then be able to update these maps between requests. We still need IO on our monad stack for reasons we’ll see later.

newtype TestMonad a = TestMonad (StateT (UserMap, ArticleMap, UserMap) IO a)
  deriving (Functor, Applicative, Monad)

instance MonadIO TestMonad where
  liftIO action = TestMonad $ liftIO action

Now we want to create instances of our database type classes for this monad. Let’s start an implementation of MonadDatabase by considering how we’ll fetch a user:

instance MonadDatabase TestMonad where
  fetchUserDB uid = ...

All we need to do is grab the first map out of our state tuple, and then use the normal Map lookup function! We can do the same with an article:

fetchUserDB uid = TestMonad $ do
  userDB <- (view _1) <$> get
  return $ Map.lookup uid userDB

fetchArticleDB aid = TestMonad $ do
  articleDB <- (view _2) <$> get
  return $ Map.lookup aid articleDB

Creating elements is a little more complicated, since we have to generate the keys. This isn’t that hard though! We’ll check if the map is empty and use 1 for the key if there are no entries. Otherwise find the max key and add 1 to it (note that the API for Map.findMax has changed since I wrote this) :

createUserDB user = TestMonad $ do
  (userDB, articleDB, userCache) <- get
  let newUid = if Map.null userDB
        then 1
        else 1 + (fst . Map.findMax) userDB
  ...

Now we’ll create a modified map by inserting our new element. Then we’ll put the modified map back in along with the other maps:

createUserDB user = TestMonad $ do
  (userDB, articleDB, userCache) <- get
  let newUid = if Map.null userDB
        then 1
        else 1 + (fst . Map.findMax) userDB
  let userDB' = Map.insert newUid user userDB
  put (userDB', articleDB, userCache)
  return newUid

createArticleDB article = TestMonad $ do
  (userDB, articleDB, userCache) <- get
  let newAid = if Map.null articleDB
        then 1
        else 1 + (fst . Map.findMax) articleDB
  let articleDB' = Map.insert newAid article articleDB
  put (userDB, articleDB', userCache)
  return newAid

Deletion follows the same general pattern. The only difference is we delete from the map instead of inserting!

deleteUserDB uid = TestMonad $ do
  (userDB, articleDB, userCache) <- get
  let userDB' = Map.delete uid userDB
  put (userDB', articleDB, userCache)

deleteArticleDB aid = TestMonad $ do
  (userDB, articleDB, userCache) <- get
  let articleDB' = Map.delete aid articleDB
  put (userDB, articleDB', userCache)

Now our final two functions will involve actually performing some application logic. To fetch articles by author, we get the list of articles in our database and filter it using the author ID:

fetchArticlesByAuthor uid = TestMonad $ do
  articleDB <- (view _2) <$> get
  return $ map KeyVal (filter articleByAuthor (Map.toList articleDB))
  where
    articleByAuthor (_, article) = articleAuthorId article == toSqlKey uid

For fetching the recent articles, we first sort all the articles in our map by timestamp. Then we take the ten most recent:

fetchRecentArticles = TestMonad $ do
  (userDB, articleDB, _) <- get
  let recentArticles = take 10 (sortBy orderByTimestamp (Map.toList articleDB)) 
  ...
  where
    orderByTimestamp (_, article1) (_, article2) =
      articlePublishedTime article2 `compare` articlePublishedTime article1

But now we have to match each of them with right user. This involves performing a lookup based on the user ID. But then we’re done!

fetchRecentArticles = TestMonad $ do
  (userDB, articleDB, _) <- get
  let recentArticles = take 10 (sortBy orderByTimestamp (Map.toList articleDB)) 
  return $ map (matchWithAuthor userDB) recentArticles
  where
    orderByTimestamp (_, article1) (_, article2) =
      articlePublishedTime article2 `compare` articlePublishedTime article1
    matchWithAuthor userDB (aid, article) =
      case Map.lookup (fromSqlKey (articleAuthorId article)) userDB of
        Nothing -> error "Found article with no user" 
        Just u -> (KeyVal (fromSqlKey (articleAuthorId article), u), KeyVal (aid, article))

Our instance for MonadCache is very similar. We'll manipulate the third map instead of the first 2:

instance MonadCache TestMonad where
  cacheUser uid user = TestMonad $ do
    (userDB, articleDB, userCache) <- get
    let userCache' = Map.insert uid user userCache
    put (userDB, articleDB, userCache')
  fetchCachedUser uid = TestMonad $ do
    userCache <- (view _3) <$> get
    return $ Map.lookup uid userCache
  deleteCachedUser uid = TestMonad $ do
    (userDB, articleDB, userCache) <- get
    let userCache' = Map.delete uid userCache
    put (userDB, articleDB, userCache')

Another Natural Transformation

Now we’re not quite done. We need the ability to run a version of our server that uses this interpretation of our effects. To do this, we need a natural transformation like we had before with AppMonad. Unfortunately, the StateT of our maps won’t get threaded through properly unless we use a pointer to it. This is why we need IO on our stack. Here’s a function that will use a pointer (MVar) to our state, run it, and then swap in the new map.

runStateTWithPointer :: (Exception e, MonadIO m) => StateT s m a -> MVar s -> m (Either e a)
runStateTWithPointer action ref = do
  env <- liftIO $ readMVar ref
  (val, newEnv) <- runStateT action env
  void $ liftIO $ swapMVar ref newEnv
  return $ Right val

Now for our transformation, we’ll take this pointer and run the state. Then we need to catch exceptions like we did in our transformation for AppMonad:

transformTestToHandler :: MVar (UserMap, ArticleMap, UserMap) -> TestMonad :~> Handler
transformTestToHandler sharedMap = NT $ \(TestMonad action) -> do
  result <- liftIO $ handleAny handler $
    runStateTWithPointer action sharedMap 
  Handler $ either throwError return result
  where
    handler :: SomeException -> IO (Either ServantErr a)
    handler e = return $ Left $ err500 { errBody = pack (show e) }

Now when we setup our tests, we’ll run our server using this transformation instead. Notice that we don’t have to do anything with Postgres or Redis here!

setupTests :: IO (ClientEnv, MVar (UserMap, ArticleMap, UserMap), ThreadId)
setupTests = do
  mgr <- newManager tlsManagerSettings
  baseUrl <- parseBaseUrl "http://127.0.0.1:8000"
  let clientEnv = ClientEnv mgr baseUrl
  let initialMap = (Map.empty, Map.empty, Map.empty)
  mapRef <- newMVar initialMap
  tid <- forkIO $
    run 8000 (serve usersAPI (testAPIServer (transformTestToHandler mapRef)))
  threadDelay 1000000
  return (clientEnv, mapRef, tid)

Now when our tests run, they’ll hit a server storing the information in memory instead of a Postgres server. This is super cool!

Integrating with our Tests

Unfortunately, it’s still a little awkward to write our tests. A lot of what they’re actually testing is the internal state of the “database” in question. So we need this function that takes the pointer to the map (the same pointer used by the server) and runs actions on it:

runTestMonad :: MVar (UserMap, ArticleMap, UserMap) -> TestMonad a -> IO a
runTestMonad mapVar (TestMonad action) = do
  currentState <- readMVar mapVar
  (result, newMap) <- runStateT action currentState
  swapMVar mapVar newMap
  return result

Now in our tests, we’ll wrap any calls to the database with this action. Here’s an example of our first before hook:

beforeHook1 :: ClientEnv -> MVar (UserMap, ArticleMap, UserMap) -> IO (Bool, Bool, Bool)
beforeHook1 clientEnv mapVar = do
  callResult <- runClientM (fetchUserClient 1) clientEnv
  let throwsError = isLeft callResult
  (inPG, inRedis) <- runTestMonad mapVar $ do
    inPG <- isJust <$> fetchUserDB 1
    inRedis <- isJust <$> fetchCachedUser 1
    return (inPG, inRedis)
  return (throwsError, inPG, inRedis)

One excellent consequence of using an in-memory map is that we don’t care if there’s data in our “database” at the end. Thus we can completely get rid of our after hooks, which were a bit of a pain!

main :: IO ()
main = do
  (clientEnv, dbMap, tid) <- setupTests
  hspec $ before (beforeHook1 clientEnv dbMap) spec1
  hspec $ before (beforeHook2 clientEnv dbMap) spec2
  hspec $ before (beforeHook3 clientEnv dbMap) spec3
  hspec $ before (beforeHook4 clientEnv dbMap) spec4
  hspec $ before (beforeHook5 clientEnv dbMap) spec5
  hspec $ before (beforeHook6 clientEnv dbMap) spec6
  killThread tid 
  return ()

And now our tests also run perfectly well without needing the docker container to be active! Hooray!

Conclusion

There’s a certain argument that we haven’t really accomplished much. Our app is very shallow, and most of the logic happens within the database calls themselves. Recall that many of our handler functions reduced to the database calls. Hence, the only thing we’re testing right now is our test interpretation!

But it’s easy to imagine that if our application were more complicated, this logic wouldn’t be at the core of our code. In most cases, database queries are the prelude to manipulating the data. And this TestMonad would remove the inconvenience of sourcing that data from outside.

Stay tuned for next week, where we’ll wrap up this consideration of effects by looking at free monads! We’ll consider the “freer-effects” library. It will let us cut down a bit on some of the boilerplate we get with this MTL style approach.

Never tried Haskell before? Do you have visions of conquering all foes with these sorts of abstractions? Check out our Getting Started Checklist and start your journey!

Have you dabbled a little but want to test your skills some more? Take a look at our Recursion Workbook!

Organizing our Effects Effectively

In the last 5 weeks or so, we’ve built a web application exposing a small API. The application is quite narrow, encompassing only a small amount of functionality. But it is still deep, covering several different libraries and techniques.

In these next couple weeks, we’ll look at some architectural considerations. We’ll observe some of the weaknesses of this system, and how we can improve on them. This week will focus on an approach with type classes and monad transformers. In a couple weeks, we’ll consider free monads, and how we can use them.

You can follow along with this code on the effects-1 branch of the Github repo.

Weaknesses

In our current system, there are a lot of different functions like these:

fetchUserPG :: PGInfo -> Int64 -> IO (Maybe User)
createUserPG :: PGInfo -> User -> IO Int64
cacheUser :: RedisInfo -> Int64 -> User -> IO ()

Now, the parameters do inform us what each function should be accessing. But the functions are still regular IO functions. This means a novice programmer could come in and get the idea that it’s fine to use arbitrary effects. For instance, why not fetch our Postgres information from the Redis function? After all, fetchPGInfo is an IO function as well:

fetchPostgresConnection :: IO PGInfo
...

cacheUser :: RedisInfo -> Int64 -> User -> IO ()
cacheUser = do
  pgInfo <- fetchPostgresConnection
  -- Connect to Postgres instead of Redis :(

Our API also has some uncomfortable lifting in our handler functions. We have to call liftIO because all our database functions are IO functions.

fetchUsersHandler :: PGInfo -> RedisInfo -> Int64 -> Handler User
fetchUsersHandler pgInfo redisInfo uid = do
  -- liftIO #1
  maybeCachedUser <- liftIO $ fetchUserRedis redisInfo uid
  case maybeCachedUser of
    Just user -> return user
    Nothing -> do
      -- liftIO #2
      maybeUser <- liftIO $ fetchUserPG pgInfo uid
      case maybeUser of
        -- liftIO #3
        Just user -> liftIO (cacheUser redisInfo uid user) >> return user
        Nothing -> Handler $ (throwE $ err401 { errBody = "Could not find user with that ID" })

At the very least, our connection parameters are explicit here. If we hid them in a Reader, this would introduce even more lifts.

This article will focus on using type classes to restrict how we use effects. With any luck, we'll also clean up our code a bit and make it easier to test things. But we’ll focus more on testing more next week.

Now, depending on the project size and scope, these weaknesses might not be issues. But it’s definitely a useful exercise to see alternative ways to organize our code.

Defining our Type Classes

Our first step for limiting our effects will be to create two type classes. We'll have one for our main database, and one for our cache. We'll try to make these functions agnostic to the underlying database representation. Hence, we’ll change our API to remove the notion of Entity. We’ll replace it with the idea of KeyVal, a wrapper around a tuple.

newtype KeyVal a = KeyVal (Int64, a)

With that, here are the 8 functions we have for accessing our database:

class (Monad m) => MonadDatabase m where
  fetchUserDB :: Int64 -> m (Maybe User) 
  createUserDB :: User -> m Int64 
  deleteUserDB :: Int64 -> m ()
  fetchArticleDB :: Int64 -> m (Maybe Article)
  createArticleDB :: Article -> m Int64
  deleteArticleDB :: Int64 -> m ()
  fetchArticlesByAuthor :: Int64 -> m [KeyVal Article]
  fetchRecentArticles :: m [(KeyVal User, KeyVal Article)]

And then we have three functions for how we interact with our cache:

class (Monad m) => MonadCache m where
  cacheUser :: Int64 -> User -> m ()
  fetchCachedUser :: Int64 -> m (Maybe User)
  deleteCachedUser :: Int64 -> m ()

We can now create instances of these type classes for any different monad we want to use. Let’s start by describing implementations for our existing libraries.

Writing Instances

We’ll start with SqlPersistT. We want to make an instance of MonadDatabase for it. We'll gather all the different functionality from the last few articles.

instance (MonadIO m, MonadLogger m) => MonadDatabase (SqlPersistT m) where
  fetchUserDB uid = get (toSqlKey uid)

  createUserDB user = fromSqlKey <$> insert user

  deleteUserDB uid = delete (toSqlKey uid :: Key User)

  fetchArticleDB aid = ((fmap entityVal) . listToMaybe) <$> (select . from $ \articles -> do
    where_ (articles ^. ArticleId ==. val (toSqlKey aid))
    return articles)

  createArticleDB article = fromSqlKey <$> insert article

  deleteArticleDB aid = delete (toSqlKey aid :: Key Article)

  fetchArticlesByAuthor uid = do
    entities <- select . from $ \articles -> do
      where_ (articles ^. ArticleAuthorId ==. val (toSqlKey uid))
      return articles
    return $ unEntity <$> entities

  fetchRecentArticles = do
    tuples <- select . from $ \(users `InnerJoin` articles) -> do
      on (users ^. UserId ==. articles ^. ArticleAuthorId)
      orderBy [desc (articles ^. ArticlePublishedTime)]
      limit 10
      return (users, articles)
    return $ (\(userEntity, articleEntity) -> (unEntity userEntity, unEntity articleEntity)) <$> tuples

Since we’re removing Entity from our API, we use this unEntity function. It will give us back the key and value as a KeyVal:

unEntity :: (ToBackendKey SqlBackend a) => Entity a -> KeyVal a
unEntity (Entity id_ val_) = KeyVal (fromSqlKey id_, val_)

Now we’ll do the same with our cache functions. We’ll make an instance of MonadCache for the Redis monad:

instance MonadCache Redis where
  cacheUser uid user = void $ setex (pack . show $ uid) 3600 (pack . show $ user)
  fetchCachedUser uid = do
    result <- get (pack . show $ uid)
    case result of
      Right (Just userString) -> return $ Just (read . unpack $ userString)
      _ -> return Nothing
  deleteCachedUser uid = void $ del [pack . show $ uid]

And that’s all there is here! Let’s see how we can combine these for easy use within our API.

Making our App Monad

We’d like to describe an “App Monad” that will allow us to access both these functionalities with ease. We’ll make a wrapper around a monad transformer incorporating a Reader for the Redis information and the SqlPersistT monad. We derive Monad for this type using GeneralizedNewtypeDeriving:

{-# LANGUAGE GeneralizedNewtypeDeriving #-}

newtype AppMonad a = AppMonad (ReaderT RedisInfo (SqlPersistT (LoggingT IO)) a)
  deriving (Functor, Applicative, Monad)

Now we’ll want to make instances of MonadDatabase and MonadCache. The instances are easy though; we'll use the instances for the underlying monads. First, let's define a transformation from an SqlPersistT action to our AppMonad. We need to build out the ReaderT RedisInfo for this. We'll use the ReaderT constructor and ignore the info with const.

liftSqlPersistT :: SqlPersistT (LoggingT IO) a -> AppMonad a
liftSqlPersistT action = AppMonad $ ReaderT (const action)

We can also define a transformation on Redis actions:

liftRedis :: Redis a -> AppMonad a
liftRedis action = do
  info <- AppMonad ask
  connection <- liftIO $ connect info
  liftIO $ runRedis connection action

We'll apply our underlying instances like so:

instance MonadDatabase AppMonad where
  fetchUserDB = liftSqlPersistT . fetchUserDB
  createUserDB = liftSqlPersistT . createUserDB
  deleteUserDB = liftSqlPersistT . deleteUserDB
  fetchArticleDB = liftSqlPersistT . fetchArticleDB
  createArticleDB = liftSqlPersistT . createArticleDB
  deleteArticleDB = liftSqlPersistT . deleteArticleDB
  fetchArticlesByAuthor = liftSqlPersistT . fetchArticlesByAuthor
  fetchRecentArticles = liftSqlPersistT fetchRecentArticles

instance MonadCache AppMonad where
  cacheUser uid user = liftRedis (cacheUser uid user)
  fetchCachedUser = liftRedis . fetchCachedUser 
  deleteCachedUser = liftRedis . deleteCachedUser

And that's it! We have our instances. Now we want to move on and figure out how we’ll actually incorporate this new monad into our API.

Writing a Natural Transformation

We would like to make it so that our handler functions can use AppMonad instead of the Handler monad. But Servant is sort’ve hard-coded to use Handler, so what do we do? The answer is we define a “Natural Transformation”.

I found this term to be a bit like "category". It seems innocuous but actually refers to something deeply mathematical. But we don't need to know too much to use it. The type operator (:~>) defines a natural transformation. All we need to make it is a function that takes an action in our monad and converts it into an action in the Handler monad. We'll need to pass our connection information to make this work.

transformAppToHandler :: PGInfo -> RedisInfo -> AppMonad :~> Handler

We’ll start by defining a “handler” that will catch any errors we throw and recast them as Servant errors. In general, you want to list the specific types of exceptions you’ll catch. It's not a great idea to catch every exception like this. But for this example, we’ll keep it simple:

handler :: SomeException -> IO (Either ServantErr a)
handler e = return $ Left $ err500 { errBody = pack (show e)}

Notice this returns an Either which is always a Left. Let's now define how we convert an action from our “AppMonad” into an Either as well. We’ll get the result and pass it on as a Right value.

runAppAction :: Exception e => AppMonad a -> IO (Either e a)
runAppAction (AppMonad action) = do
  result <- runPGAction pgInfo $ runReaderT action redisInfo
  return $ Right result

And putting it together, here’s our transformation. We catch errors, and then wrap the result up in Handler.

transformAppToHandler :: PGInfo -> RedisInfo -> AppMonad :~> Handler
transformAppToHandler pgInfo redisInfo = NT $ \action -> do
  result <- liftIO (handleAny handler (runAppAction action))
  Handler $ either throwError return result
  ...

Incorporating the App Monad

All we have to do now is incorporate our new monad into our handlers. First off, let’s change our API to remove Entities:

type FullAPI =
       "users" :> Capture "userid" Int64 :> Get '[JSON] User
  :<|> "users" :> ReqBody '[JSON] User :> Post '[JSON] Int64
  :<|> "articles" :> Capture "articleid" Int64 :> Get '[JSON] Article
  :<|> "articles" :> ReqBody '[JSON] Article :> Post '[JSON] Int64
  :<|> "articles" :> "author" :> Capture "authorid" Int64 :> Get '[JSON] [KeyVal Article]
  :<|> "articles" :> "recent" :> Get '[JSON] [(KeyVal User, KeyVal Article)]

We want to update the type of each function. The AppMonad incorporates all the configuration information. So we don’t need to pass connection information explicitly. Instead, we can use constraints on our monad type classes to expose those effects. Here’s what our type signatures look like:

fetchUsersHandler :: (MonadDatabase m, MonadCache m) => Int64 -> m User
createUserHandler :: (MonadDatabase m) => User -> m Int64
fetchArticleHandler :: (MonadDatabase m) => Int64 -> m Article
createArticleHandler :: (MonadDatabase m)=> Article -> m Int64
fetchArticlesByAuthorHandler :: (MonadDatabase m) => Int64 -> m [KeyVal Article]
fetchRecentArticlesHandler :: (MonadDatabase m) => m [(KeyVal User, KeyVal Article)]

And now a lot of our functions are simple monadic calls. We don’t even need to use “lift”!

createUserHandler :: (MonadDatabase m) => User -> m Int64
createUserHandler = createUserDB

createArticleHandler :: (MonadDatabase m)=> Article -> m Int64
createArticleHandler = createArticleDB

fetchArticlesByAuthorHandler :: (MonadDatabase m) => Int64 -> m [KeyVal Article]
fetchArticlesByAuthorHandler = fetchArticlesByAuthor

fetchRecentArticlesHandler :: (MonadDatabase m) => m [(KeyVal User, KeyVal Article)]
fetchRecentArticlesHandler = fetchRecentArticles

The “fetch” functions are a bit more complicated since we’ll want to do stuff like check the cache first. But again, all our functions are simple monadic calls without using any lifting. Here’s how our fetch handlers look:

fetchUsersHandler :: (MonadDatabase m, MonadCache m) => Int64 -> m User
fetchUsersHandler uid = do
  maybeCachedUser <- fetchCachedUser uid
  case maybeCachedUser of
    Just user -> return user
    Nothing -> do
      maybeUser <- fetchUserDB uid
      case maybeUser of
        Just user -> cacheUser uid user >> return user
        Nothing -> error "Could not find user with that ID"

fetchArticleHandler :: (MonadDatabase m) => Int64 -> m Article
fetchArticleHandler aid = do
  maybeArticle <- fetchArticleDB aid
  case maybeArticle of
    Just article -> return article
    Nothing -> error "Could not find article with that ID"

And now we’ll change our Server function. We’ll update it so that it takes our natural transformation as an argument. Then we’ll use the enter function combined with that transformation. This is how Servant knows what monad we want for our handlers:

fullAPIServer :: (AppMoand :~> Handler) -> Server FullAPI
fullAPIServer naturalTransformation =
  enter naturalTransformation $
    fetchUsersHandler :<|>
    createUserHandler :<|>
    fetchArticleHandler :<|>
    createArticleHandler :<|>
    fetchArticlesByAuthorHandler :<|>
    fetchRecentArticlesHandler

runServer :: IO ()
runServer = do
  pgInfo <- fetchPostgresConnection
  redisInfo <- fetchRedisConnection
  -- Pass the natural transformation as an argument!
  run 8000 (serve usersAPI (fullAPIServer (transformAppToHandler pgInfo redisInfo)))

And now we’re done!

Weaknesses with this Approach

Of course, this system is not without it’s weaknesses. In particular, there’s quite a bit of boilerplate. This is especially true if we don’t want to fix the ordering of our monad stack. For instance what if another part of our application puts SqlPersistT on top of Redis? What if we want to mix other monad transformers in? We’ll need new instances of MonadDatabase and MonadCache for that. We'll end up writing a lot more simple definitions. We’ll examine solutions to this weakness in a couple weeks when we look at free monads.

We’ll also need to add new functions to our type classes every time we want to update their functionality. And then we’ll have to update EVERY instance of that typeclass, which can be quite a pain. The more instances we have, the more painful it will be to add new functionality.

Conclusion

So with a few useful tricks, we can come up with code that is a lot cleaner. We employed type classes to great effect to limit how effects appear in our application. By writing instances of these classes for different monads, we can change the behavior of our application. Next week, we’ll see how we can use this behavior to write simpler tests!

When managing an application with this many dependencies you need the right tools. I used Stack for all my Haskell project organization. Check out our free Stack mini-course to learn more!

But if you’ve never tried Haskell at all, give it a try! Take a look at our Getting Started Checklist.

Obey the (Type) Laws!

We should now have a decent grasp on functors, applicative functors, and monads. Be sure to check these articles out if you need a refresher! Now we understand the concepts, so it’s time to learn the laws around them.

Remember Haskell represents each of these mathematical classes by a type class. Each of these type classes has one or two main functions. So, as long as we implement those functions and it type checks, we have a new functor/applicative/monad, right?

Well not quite. Yes, your program will compile and you’ll be able to use the instances. But this doesn't mean your instances follow the mathematical constructs. If they don't, your instances won't fulfill other programmers’ expectations. Each type class has its own “laws”. For instance, let's think back to the GovDirectory type we created in the functor article. Suppose we made a different functor instance than we had there:

data GovDirectory a = GovDirectory {
  mayor :: a,
  interimMayor :: Maybe a,
  cabinet :: Map String a,
  councilMembers :: [a]
}

instance Functor GovDirectory where
  fmap f oldDirectory = GovDirectory {
    mayor = f (mayor oldDirectory),
    interimMayor = Nothing,
    cabinet = f <$> cabinet oldDirectory,
    councilMembers = f <$> councilMembers oldDirectory
  }

As we’ll see, this would violate one of the functor laws. In this case it would not be a true functor. Its behavior would confuse any other programmer trying to use it. We should take care to make sure that our instances make sense. Once you get a feel for these type classes, the likelihood is that the instances you’ll create follow the laws. So don’t sweat it if a few of these are confusing. This article will be very math-y, and we won’t dwell too much on the concepts. You can understand and use these classes without knowing these laws by heart. So without further ado, let’s dive into the laws!

Functor Laws

There are two functor laws. The first is an identity law. We’ll see some variation of this idea for each of the type classes. Remember how fmap "maps" a function over our container. If we map the identity function over a container, the result should be the same container object:

fmap id = id

In other words, our functor should not be applying any extra changes or side effects. It should only apply the function. The second law is a composition law. It states our functor implementation should not break the composition of functions:

fmap (g . f) = fmap g . fmap f

-- For reference, remember the type of the composition operator:
(.) :: (b -> c) -> (a -> b) -> (a -> c)

On one side we compose two functions, and map the resulting function over our container. On the other side, we map the first function, get the result, and map the second function over it. The functor composition law states these outcomes should be identical. This sounds complex. But you don't need to worry about it much. If you break the composition law in Haskell, you'll also likely break the identity law.

Those are the only two laws for functors! So let's move on to applicative functors.

Applicative Laws

Applicative functors are a little more complicated. They have four different laws. The first is easy though. It's another simple identity law. It says:

pure id <*> v = v

On the left side, we wrap the identity function. Then we apply it over our container. The applicative identity law states this should result in an identical object. Simple enough.

The second law is the homomorphism law. Suppose we wrap a function and an object in pure. We can then apply the wrapped function over the wrapped object. Of course, we could also apply the normal function over the normal object, and THEN wrap it in pure. The homomorphism law states these results should be the same.

pure f <*> pure x = pure (f x)

We should see a distinct pattern here. The overriding theme of almost all these laws is that our type classes are containers. The type class function should not have any side effects. All they should do is facilitate the wrapping, unwrapping, and transformation of data.

The third law is the interchange law. It’s a little more complicated, so don’t sweat it too much. It states that the order that we wrap things shouldn’t matter. One on side, we apply any applicative over a pure wrapped object. On the other side, first we wrap a function applying the object as an argument. Then we apply this to the first applicative. These should be the same.

u <*> pure y = pure ($ y) <*> u

The final applicative law mimics the second functor law. It is a composition law. It states that function composition holds across applications within the functor:

pure (.) <*> u <*> v <*> w = u <*> (v <*> w)

The sheer number of laws here can be a little overwhelming. Remember, the instances you make will probably follow the laws! Let’s move on to our final example: monads.

Monad Laws

Monads have three laws. The first two are simple identity laws, like our other classes have had:

return a >>= f = f
m >>= return = m

These are the left and right identities. They state effectively that the only thing the return function is allowed to do is to wrap the object (sound familiar?). It cannot manipulate the data in any way. Our main takeaway from these is that the following code samples are equivalent:

func1 :: IO String
func1 = do
  str <- getLine
  return str

func2 :: IO String
func2 = getLine

The third law is a bit more interesting. It tells us that associativity holds within monads:

(m >>= f) >>= g = m >>= (\x -> f x >>= g)

But we see this third law has a parallel structure to the other composition laws. In the first case, we apply two functions in two steps. In the second case, we compose the functions first, and THEN apply the result. These should be the same.

So in summary, there are two main ideas from all the laws. First, identity should be preserve over wrapper functions, like pure and return. Second, function composition should hold across our structures.

Checking the Laws

As I stated before, most of the instances that you come up with will naturally follow these rules. As you get more experience with the different type classes, this will be even more true. Yet, it also pays to be sure. Haskell has an excellent tool for verifying your instances pass a certain law.

This utility is QuickCheck. It can take any a certain rule, generate many different test cases on the rule, and verify the rule holds. In this section, we’ll run a few tests on our GovDirectory functor instance. We'll see how QuickCheck proves its initial failure, and ultimate success. First we need to implement the Arbitrary type class over our type. We can do this a long as the inner type is also Arbitrary, such as a built-in string type. Then we’ll use all the other Arbitrary instances that exist over our inner types:

instance Arbitrary a => Arbitrary (GovDirectory a) where
  arbitrary = do
    m <- arbitrary
    im <- arbitrary
    cab <- arbitrary
    cm <- arbitrary
    return $ GovDirectory
      { mayor = m
      , interimMayor = im
      , cabinet = cab
      , councilMembers = cm }

Once you have done that, you can write a test case over a particular rule. In this case, we check the identity function for functors:

main :: IO ()
main = quickCheck govDirectoryFunctorCheck

govDirectoryFunctorCheck :: GovDirectory String -> Bool
govDirectoryFunctorCheck gd = fmap id gd == gd

Now let’s test this on the faulty instance we used above. We can see that a particular test will fail:

*** Failed! Falsifiable (after 2 tests):
GovDirectory {mayor = "", interimMayor = Just "\156", cabinet = fromList [("","")], councilMembers = []}

It specifies for us an arbitrary instance that failed the test. Now suppose we correct the instance:

interimMayor = f <$> (interimMayor oldDirectory),

We’ll see the tests pass!

+++ OK, passed 100 tests.

Summary

We've discussed three major type classes: functors, applicative functors, and monads. They all have particular laws their instances should follow. Other programmers who use your code will expect any instances you make to follow these laws. Once you are familiar with the types, you will likely create instances that follow the laws. But if you are unsure, you can use the QuickCheck utility to verify them.

This concludes our series on monads! You should now have all the tools you need to start using them in practice. Remember that they are a difficult concept, and you'll likely have to review them a couple times. But eventually, you'll understand them!

If you're now inspired to get started with Haskell, make sure to check out our free Getting Started Checklist! It'll help kickstart your Haskell experience by helping you through the download process and making your first project with Stack!

If you're up for a bigger challenge, you should get our Recursion Workbook. It's also free! It has a couple chapters of material on recursion and higher order functions. It also has 10 practice problems for you to try out!

Making Sense of Multiple Monads

We’ve recently how the maybe monad has helped us avoid triangle of doom code patterns. Without it, we had to check each function call for success. However, the examples we looked at were all pure code examples. Consider this:

main :: IO
main = do
  maybeUserName <- readUserName
  case maybeUserName of
    Nothing -> print “Invalid user name!”
    Just (uName) -> do
      maybeEmail <- readEmail
      case maybeEmail of
        Nothing -> print “Invalid email!”
        Just (email) -> do
          maybePassword <- readPassword
          Case maybePassword of
            Nothing -> print “Invalid Password”
            Just password -> login uName email password

readUserName :: IO (Maybe String)
readUserName = do
  str <- getLIne
  if length str > 5
    then return $ Just str
    else return Nothing

readEmail :: IO (Maybe String)
...

readPassword :: IO (Maybe String)
...

login :: String -> String -> String -> IO ()
...

In this example, all our potentially problematic code takes place within the IO monad. How can we use the Maybe monad when we’re already in another monad?

Monad Transformers

Luckily, we can get the desired behavior by using monad transformers to combine monads. In this example, we’ll wrap the IO actions within a transformer called MaybeT.

A monad transformer is fundamentally a wrapper type. It is generally parameterized by another monadic type. You can then run actions from the inner monad, while adding your own customized behavior for combining actions in this new monad. The common transformers add T to the end of an existing monad. Here’s the definition of MaybeT:

newtype MaybeT m a = MaybeT { runMaybeT :: m (Maybe a) }

instance (Monad m) => Monad (MaybeT m) where
    return = lift . return
    x >>= f = MaybeT $ do
        v <- runMaybeT x
        case v of
            Nothing -> return Nothing
            Just y  -> runMaybeT (f y)

So MaybeT itself is simply a newtype. It in turn contains a wrapper around a Maybe value. If the type m is a monad, we can also make a monad out of MaybeT.

Let’s consider our example. We want to use MaybeT to wrap the IO monad, so we can run IO actions. This means our new monad is MaybeT IO. Our three helper functions all return strings, so they each get the type MaybeT IO String. To convert the old IO code into the MaybeT monad, all we need to do is wrap the IO action in the MaybeT constructor.

readUserName :: MaybeT IO String
readUserName = MaybeT $ do
  str <- getLIne
  if length str > 5
    then return $ Just str
    else return Nothing

readEmail :: MaybeT IO String
...

readPassword :: MaybeT IO String
...

Now we can wrap all three of these calls into a single monadic action, and do a single pattern match to get the results. We’ll use the runMaybeT function to unwrap the Maybe value from the MaybeT:

main :: IO ()
main = do
  maybeCreds <- runMaybeT $ do
    usr <- readUserName
    email <- readEmail
    pass <- readPassword
    return (usr, email, pass)
  case maybeCreds of
    Nothing -> print "Couldn't login!"
    Just (u, e, p) -> login u e p

And this new code will have the proper short-circuiting behavior of the Maybe monad! If any of the read functions fail, our code will immediately return Nothing.

Adding More Layers

Here’s the best part about monad transformers. Since our newly created type is a monad itself, we can wrap it inside another transformer! Pretty much all common monads have transformer types in the same way the MaybeT is a transformer for the ordinary Maybe monad.

For a quick example, suppose we had an Env type containing some user information. We could wrap this environment in a Reader. However, we want to still have access to IO functionality, so we’ll use the ReaderT transformer. Then we can wrap the result in MaybeT transformer.

type Env = (Maybe String, Maybe String, Maybe String)

readUserName :: MaybeT (ReaderT Env IO) String
readUserName = MaybeT $ do
  (maybeOldUser, _, _) <- ask
  case maybeOldUser of
    Just str -> return str
    Nothing -> do
      -- lift allows normal IO functions from inside ReaderT Env IO!
      input <- lift getLine
      if length input > 5
        then return (Just input)
        else return Nothing

Notice we had to use lift to run the IO function getLine. In a monad transformer, the lift function allows you to run actions in the underlying monad. So using lift in the ReaderT Env IO action allows IO functions. Within a MaybeT (ReaderT Env IO) function, calling lift would allow you to run a Reader function. We don’t need this above since the bulk of the code lies in Reader actions wrapped by the MaybeT constructor.

To understand the concept of lifting, think of your monad layer as a stack. When you have a ReaderT Env IO action, imagine a Reader Env monad on top of the IO monad. An IO action exists on the bottom layer. So to run it from the upper layer, you need to lift it up. If your stack is more than two layers, you can lift multiple times. Calling lift twice from the MaybeT (ReaderT Env IO) monad will allow you to call IO functions.

It’s inconvenient to have to know how many times to call lift to get to a particular level of the chain. Thus helper functions are frequently used for this. Additionally, since monad transformers can run several layers deep, the types can get complicated, so it is typical to use type synonyms liberally.

type TripleMonad a = MaybeT (ReaderT Env IO) a

performReader :: ReaderT Env IO a -> TripleMonad a
performReader = lift

performIO :: IO a -> TripleMonad a
performIO = lift . lift

Typeclasses

As a similar idea, there are some typeclasses which allow you to make certain assumptions about the monad stack below. For instance, you often don’t care what the exact stack is, but you just need IO to exist somewhere on the stack. This is the purpose of the MonadIO typeclass:

class (Monad m) => MonadIO m where
  liftIO :: IO a -> m a

We can use this behavior to get a function to print even when we don’t know its exact monad:

debugFunc :: (MonadIO m) => String -> m a
debugFunc input = do
  liftIO $ print “Interpreting Input: “ ++ input
  …

One final note: You cannot, in general, wrap another monad with the IO monad using a transformer. You can, however, make the other monadic value the return type of an IO action.

func :: IO (Maybe String)
-- This type makes sense

func2 :: IO_T (ReaderT Env (Maybe)) string
-- This does not exist

Summary

Monad Transformers allow us to wrap monads within other monads. All of the basic built-in monads have transformer types. We name these types by adding T to the end of the name, like MaybeT. Monad transformers let us get useful behavior from all the different monads on our stack. The lift function allows us to run functions within monads further down the stack.

Monad transformers are extremely important when trying to write meaningful Haskell code. If you want to get started with Haskell, be sure to check out our free checklist for Haskell tools.

Want to practice some Haskell skills, but aren’t ready for monads? You can also take a look at our recursion workbook (it’s also free!). It has two chapters of content on recursion and higher order functions, as well as 10 practice problems.

Stay tuned, because next week we will complete our discussion of our abstract wrapper types (functors, applicatives, monads) by exploring the laws governing their behavior.

The Monadic State of Mind

In this article, we’re going to describe one final monad. The State monad is among the most common and most useful. We’ve seen the Reader monad, which allows you to have a common global value among several functions. We also examined the Writer monad, which allows you to keep adding to a particular monoid value. The State monad combines these ideas to give us a full read-write state. We’ll see how this allows our code to have many of the qualities of other programming languages that Haskell seems to lack.

Motivating Example: Monopoly

For this article, we’ll use a simple model for a Monopoly-like game. The main object is the GameState data type containing several important pieces of information.

data GameState = GameState
  { players :: [Player]
  , chanceDeck :: [GameCard]
  , properties :: Map Property PropertyState
  , piecePositions :: Map Player Property 
  . generator :: StdGen }

data PropertyState = Unowned | Owned Player

data ChanceCard = …
data Player = …
data BoardPostion = …
data GameAction = ...

Let’s think at a high level about how some of our game functions would work. We could, for instance, have a function for rolling the dice. This would output a number and alter our game’s number generator. We would then make a move based on the dice output and the current player. This would change the piece positions in the board state as well as leaving us with an output action to resolve (like drawing a card, or taking action on a property).

Buying a property also changes the board’s state. Drawing a chance card would update the state of the deck while returning us a GameCard to resolve. We see a common pattern here among the different actions. Almost all of them will update GameState in some way, and some of them will have an additional piece of output we’ll want to use.

The State Monad

This is exactly the situation the State monad deals with. The State monad wraps computations in the context of reading and modifying a global state object. This context chains two operations together by determining what the state should be after the first operation, and then resolving the second operation with the new state.

It is parameterized by a single type parameter s, the state type in use. So just like the Reader has a single type we read from, the State has a single type we can both read from and write to.

The two main functions we’ll use within the State monad with are get and put. They do exactly what you expect they’d do. The get function works much like the ask function of the reader monad, retrieving our state value. Meanwhile, put works similarly to tell in the Writer monad, where we’ll pass an updated state. Finally we observe there will still be a final return type on each expression in State, just as there is in any other monad. Thus our different function types will look like this for a return type of a:

State GameState a

Our Monopoly Functions

Now we can examine some of the different functions mentioned above and determine their types. We have for instance, rolling the dice:

rollDice :: State GameState Int
rollDice = do
  currentState <- get
  let gen = generator currentState
  let (d1, gen') = randomR (1,6) gen
  let (d2, gen'') = randomR (1,6) gen'
  put (currentState { generator = gen'' } )
  return (d1 + d2)

This outputs an Int to us, and modifies the random number generator stored in our state! Now we also have the function making a move:

movePiece :: Player -> Int -> State GameState Property
movePiece player roll = do
  currentState <- get
  let currentPositions = piecePositions currentState
  let currentPos = fromJust (M.lookup player currentPositions)
  let next = nextProperty currentPos roll
  let newMap = M.insert player next currentPositions
  put (currentState { piecePositions = newMap } ) 
  return next

nextProperty :: Property -> Int -> Property
...

This will give us the output of the new property we landed on, while also modifying the board with our new position of our piece. Based on the resulting position, we might take different actions, like drawing a chance card:

drawChance :: State GameState ChanceCard
drawChance = do
  currentState <- get
  let (fstCard : deck) = chanceDeck currentState
  put (currentState { chanceDeck = deck } )
  return fstCard

As we said above, this will modify the pile of available cards in the chance pile. There are other stateful functions we could describe, such as resolving a property purchase, or paying rent to another player. These would also exist within the state monad.

buyProperty :: Player -> Property -> State GameState ()
…

payRent :: Player -> Property -> State GameState ()
...

So finally, we can combine all these functions together with do-syntax, and it actually looks quite clean! We don’t need to worry about the side effects. The different monadic functions handle them. Here’s a sample of what your function might look like to play one turn of the game:

resolveTurn :: State GameState ()
resolveTurn = do
  currentState <- get
  let playerToMove = currentPlayer currentState 
  roll <- rollDice
  newProperty <- movePiece playerToMove roll
  action <- actionForProperty playerToMove newProperty
  resolveAction action
  switchNextPlayer
  return ()

Obviously, we haven’t described all these functions, but the general idea should be clear. They would all exist within the state monad.

State, IO, and Other Languages

When thinking about Haskell, it is often seen as a restriction that we can’t have global variables we can modify, like you could with Java class variables. However, we see now this isn’t true. We could have a data type with exactly the same functionality as a Java class, where many functions can modify the global state of the class object using the State monad.

The difference is in Haskell we simply put a label on these types of functions. We don’t allow it to happen for free. We want to know when side effects can potentially happen, because knowing when they can happen makes our code easier to reason about. In a Java class, many of the methods won’t actually need to modify the state. But they could, which makes it harder to debug them. In Haskell we can simply make these pure functions, and our code will be simpler.

IO is the same way. It’s not like we can’t perform IO in Haskell. Instead, we want to label the areas where we can, to increase our certainty about the areas where we don’t need to. When we know part of our code cannot communicate with the outside world, we can be far more certain of its behavior.

Summary

The State monad allows us to have a global readable and writable state. It gives Haskell exactly the kind of flexibility you expect to find in any other programming language. But by separating stateful code from our pure code, our pure code becomes much easier to reason about.

Since we have so many monads under our belts now, the next step is to know how to combine them. Next week we’ll talk about monad transformers, and how those enable us to use multiple monadic functionalities together!

If this has piqued your curiosity for Haskell but you don’t know where to begin, checkout out our checklist to learn more!

If this has inspired you to try out some Haskell code, be sure to try out our free workbook on recursion and higher order function. It includes 10 practice problems so you can hone your skills!

How to Read and Write (with Monads!)

So last week we discussed what a monad is. It isn’t some scary thing only wizards with arcane knowledge of category theory can understand. It’s just a type class with a couple functions describing a particular context. These functions, when used properly, can dramatically expand what we can do while keeping our code purely functional.

We haven’t gone over all the “laws” these functions need to follow. But if we explore enough examples, we’ll have an intuitive grasp of what should happen. We saw some simple examples last time with the Maybe, Either, and IO monads. In this article, we will look at the Reader and Writer monads.

Global Variables (or a lack thereof)

In Haskell, our code is generally “pure”, meaning functions can only interact with the arguments passed to them. This effectively means we cannot have global variables. We can have global expressions, but these are fixed at compile time. If user behavior might change them, we have to wrap them in the IO monad, which means they can’t be used from pure code.

Consider this example where we might want to have an Environment containing different parameters as a global variable. However, we might have to load these from a config file or a command line interface, which requires the IO monad.

main :: IO ()
main = do
  env <- loadEnv
  let str = func1 env
  print str

data Environment = Environment
  { param1 :: String
  , param2 :: String
  , param3 :: String }

loadEnv :: IO Environment
loadEnv = …

func1 :: Environment -> String
func1 env = “Result: “ ++ (show (func2 env))

func2 :: Environment -> Int
func2 env = 2 + floor (func3 env)

func3 :: Environment -> Float
func3 env = … -- Some calculation based on the environment

The only function actually using the environment is func3. However func3 is an impure function. This means it cannot directly call loadEnv, an impure function. This means the environment has to be passed through as a variable to the other functions, just so they can ultimately pass it to func3. In a language with global variables, we could save env as a global value in main. Then func3 could access it directly. There would be no need to have it as a parameter to func1 and func2. In larger programs, these “pass-through” variables can cause a lot of headaches.

The Reader Solution

The Reader monad solves this problem. It effectively creates a global read-only value of a specified type. All functions within the monad can “read” the type. Let’s look at how the Reader monad changes the shape of our code. Our functions no longer need the Environment as an explicit parameter, as they can access it through the monad.

main :: IO ()
main = do
  env <- loadEnv
  let str = runReader func1 env
  print str

data Environment = Environment
  { param1 :: String
  , param2 :: String
  , param3 :: String }

loadEnv :: IO Environment
loadEnv = …

func1 :: Reader Environment String
func1 = do
  res <- func2
  return (“Result: “ ++ (show res))

func2 :: Reader Environment Int
func2 = do
  env <- ask
  let res3 = func3 env
  return (2 + (floor res3))

func3 :: Environment -> Float
...

The ask function unwraps the environment so we can use it. The monad’s bind action allows us to glue different Reader actions together together. In order to call a reader action from pure code, all we need to do is call the runReader function and supply the environment as a parameter. All functions within the action will be able to treat it like a global variable.

It might not seem like we’ve accomplished much, but our code is much more intuitive now. We keep func3 as it was. It makes sense to describe it as a function from an Environment to a value. However, our other two functions no longer take the environment as an explicit parameter. They simply exist in a context where the environment is a global variable.

Accumulating Values

Now, to motivate the Writer monad, let’s talk about the accumulation problem. Suppose we have a few different functions. Each will perform some string operations we’ve assigned an arbitrary “cost” to. We want to keep track of how “expensive” it was to run the full computation. We can do this by using accumulator arguments to keep track of the cost we’ve seen so far. We then keep passing the accumulated value along.

-- Calls func2 if even length, func3 and func4 if odd
func1 :: String -> (Int, String)
func1 input = if length input `mod` 2 == 0
  then func2 (0, input)
  else (i1 + i2, str1 ++ str2)
    where
      (i1, str1) = func3 (0, tail input)
      (i2, str2) = func4 (0, take 1 input)

-- Calls func4 on truncated version
func2 :: (Int, String) -> (Int, String)
func2 (prev, input) = if (length input) > 10
  then func4 (prev + 1, take 9 input)
  else (10, input)

-- Calls func2 on expanded version if a multiple of 3
func3 :: (Int, String) -> (Int, String)
func3 (prev, input) = if (length input) `mod` 3 == 0
  then (prev + f2resI + 3, f2resStr)
  else (prev + 1, tail input)
  where
    (f2resI, f2resStr) = func2 (prev, input ++ "ab")

func4 :: (Int, String) -> (Int, String)
func4 (prev, input) = if (length input) < 10
  then (prev + length input, input ++ input)
  else (prev + 5, take 5 input)

However, an Int isn’t the only type of value we could accumulate. We could instead be accumulating a list of strings to print as log messages so we know what computations were run. There is a generalization of this behavior: the Monoid typeclass.

The Monoid Typeclass

In this example, Int is a simple example of a Monoid. Let’s look at the monoid typeclass definition:

class Monoid a where
  mempty :: a
  mappend :: a -> a -> a

This is effectively an accumulation class. It defines two functions. The mempty function is an initial value for our monoid. Then with mappend, we can combine two values of this type into a result. It is quite easy to how we can make a monoid instance for Int:

instance Monoid Int where
  memty = 0
  mappend a b = a + b

Our accumulator starts at 0, and we combine values by adding them.

Using Writer to Track the Accumulator

The Writer monad is parameterized by some monoidal type. Its main job is to keep track of an accumulated value of this type. So it’s operations live in the context of having a global value that they can modify in this particular way. We can change our code examples above to use the Writer monad as follows:

func1 :: String -> (String, Int)
func1 input = if length input `mod` 2 == 0
  then runWriter (func2 input)
  else runWriter $ do
    str1 <- func3 input
    str2 <- func4 (take 1 input)
    return (str1 ++ str2)

func2 :: String -> Writer Int String
func2 input = if (length input) > 10
  then do
    tell 1
    func4 (take 9 input)
  else do
    tell 10
    return input

func3 :: String -> Writer Int String
func3 input = if (length input) `mod` 3 == 0
  then do
    tell 3
    func2 (input ++ “ab”)
  else do
    tell 1
    return $ tail input

func4 :: String -> Writer Int String
func4 input = if (length input) < 10
  then do
    tell (length input)
    return (input ++ input)
  else do
    tell 5
    return (take 5 input)

Notice we no longer need to actually explicitly keep track of the accumulator. It is now wrapped by the Writer monad. We can increase it in any of our functions by calling “tell”. Now our code is much simpler and our types are cleaner.

Conclusion

The Reader and Writer monads both offer pure functional ways to deal with common side effects. The Reader monad allows you to keep track of a shared global state. It allows you to avoid passing that state as an explicit parameter to functions that don’t really use it. The Writer monad allows you to keep track of a global accumulated value using a monoid. Next week we’ll learn how we can wrap these ideas into one with the State monad!

Hopefully this article has helped convinced you that monads (and Haskell for that matter) aren’t all that scary! If this has inspired you to pick up Haskell and start writing some code, check out our free checklist for getting stated!

Not quite ready for monads but want to try some different Haskell skills? Check out our recursion workbook. It includes 2 chapters of material on recursion and higher order functions, as well as 10 practice problems with a test harness.

(Finally) Understanding Monads (Part 1)

We should now have a decent grasp on functors and applicative functors (check out the links if you aren’t!). Now it’s time to take the next step up. We’re going to tackle the dreaded concept of Monads. There are dozens of monad tutorials and descriptions on the internet. This makes sense. Monads are vital to writing any kind of meaningful program in Haskell. They aren’t the hardest concept in functional programming, but they are the biggest roadblock because of their importance. In this series of articles, we’re going to try tackling the concept in small, manageable chunks.

So without further ado, here’s my crack at a definition: A Monad wraps a value or a computation with a particular context. A monad must define both a means of wrapping normal values in the context, and a way of combining computations within the context.

This definition is quite broad. So let’s look at a more practical level to try to make sense of this.

The Monad Typeclass

Just like with functors and applicative functors, Haskell represents monads with a type class. It has two functions:

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

These two functions correspond to the two ideas from above. The return function specifies a how to wrap values in the monad’s context. The >>= operator, which we call the “bind” function, specifies how to combine two operations within the context. Let’s clarify this further by exploring a few specific monad instances.

The Maybe Monad

Just as Maybe is a functor and an applicative functor, it is also a monad. To motivate the Maybe monad, let’s consider this code.

maybeFunc1 :: String -> Maybe Int
maybeFunc1 “” = Nothing
maybeFunc1 str = Just $ length str

maybeFunc2 :: Int -> Maybe Float
maybeFunc2 i = if i `mod` 2 == 0
  then Nothing
  Else Just ((fromIntegral i) * 3.14159)

maybeFunc3 :: Float -> Maybe [Int]
maybeFunc3 f = if f > 15.0
  then Nothing
  else $ Just [floor f, ceil f]

runMaybeFuncs :: String -> Maybe [Int]
runMaybeFuncs input = case maybeFunc1 input of
  Nothing -> Nothing
  Just i -> case maybeFunc2 i of
    Nothing -> Nothing
    Just f -> maybeFunc3 f

We can see we’re starting to develop a hideous triangle pattern as we continue pattern matching on the results of successive function calls. If we were to add more Maybe functions onto this, it would keep getting worse. When we consider Maybe as a monad, we can make the code much cleaner. Let’s take a look at how Haskell implements Maybe as a monad to see how.

instance Monad Maybe where
  return = Just
  Nothing >>= _ = Nothing
  Just a >>= f = f a

The context the Maybe monad describes is simple. Computations in Maybe can either fail or succeed with a value. We can take any value and wrap it in this context by calling the value a “success”. We do this with the Just constructor. We represent failure by Nothing.

We combine computations in this context by examining the result of the first computation. If it succeeded, we takes its value, and pass it to the second computation. If it failed, then we have no value to pass to the next step. So the total computation is a failure. Let’s look at how we can use the bind operator to combine our operations:

runMaybeFuncs :: String -> Maybe [Int]
runMaybeFuncs input = maybeFunc1 input >>= maybeFunc2 >>= maybeFunc3

This looks much cleaner! Let’s see why the types work out. The result of maybeFunc1 input is simply Maybe Int. Then the bind operator allows us to take this Maybe Int value and combine it with maybeFunc2, whose type is Int -> Maybe Float. The bind operator resolves these to a Maybe Float. Then we pass this similarly through the bind operator to maybeFunc3, resulting in our final type, Maybe [Int].

Your functions will not always combine so cleanly though. This is where do notation comes into play. We can rewrite the above as:

runMaybeFuncs :: String -> Maybe [Int]
runMaybeFuncs input = do
  i <- maybeFunc1 input
  f <- maybeFunc2 f
  maybeFunc3 f

The <- operator is special. It effectively unwraps the value on the right-hand side from the monad. This means the value i has type Int, even though the result of maybeFunc1 is Maybe Int. The bind operation happens under the hood, and if the function returns Nothing, then the entire runMaybeFuncs function will return Nothing.

At first glance, this looks more complicated than the bind example. However, it gives us a lot more flexibility. Consider if we wanted to add 2 to the integer before calling maybeFunc2. This is easy to deal with in do notation, but more difficult when simply using binds:

runMaybeFuncs :: String -> Maybe [Int]
runMaybeFuncs input = do
  i <- maybeFunc1 input
  f <- maybeFunc2 (i + 2)
  maybeFunc3 f

-- Not so nice
runMaybeFuncsBind :: String -> Maybe [Int]
runMaybeFuncsBind input = maybeFunc1 input
  >>= (\i -> maybeFunc2 (i + 2))
  >>= maybeFunc3

The gains are even more obvious if we want to use multiple previous results in a function call. Using binds, we would have to continually accumulate arguments in anonymous functions. One note about do notation: we never use <- to unwrap the final operation in a do-block. Our call to maybeFunc3 has the type Maybe [Int]. This is our final type (not [Int]) so we do not unwrap.

The Either Monad

Now, let’s examine the Either monad, which is quite similar to the Maybe monad. Here’s the definition:

instance Monad (Either a) where
  return r = Right r
  (Left l) >>= _ = Left l
  (Right r) >>= f = f r

Whereas the Maybe either succeeds with a value or fails, the Either monad attaches information to failures. Just like Maybe, it wraps values in its context by calling them successful. The monadic behavior also combines operations by short-circuiting on the first failure. Let’s see how we can use this to make our code from above more clear.

maybeFunc1 :: String -> Either String Int
maybeFunc1 “” = Left “String cannot be empty!”
maybeFunc1 str = Right $ length str

maybeFunc2 :: Int -> Either String Float
maybeFunc2 i = if i `mod` 2 == 0
  then Left “Length cannot be even!”
  else Right ((fromIntegral i) * 3.14159)

maybeFunc3 :: Float -> Either String [Int]
maybeFunc3 f = if f > 15.0
  then Left “Float is too large!”
  else $ Right [floor f, ceil f]

runMaybeFuncs :: String -> Either String [Int]
runMaybeFuncs input = do
  i <- maybeFunc1 input
  f <- maybeFunc2 i
  maybeFunc3 f

Before, every failure just gave us a Nothing value:

>> runMaybeFuncs ""
Nothing
>> runMaybeFuncs "Hi"
Nothing
>> runMaybeFuncs "Hithere"
Nothing
>> runMaybeFuncs "Hit"
Just [9,10]

Now when we run our code, we can look at the resulting error string, and this will tell us which function actually failed.

>> runMaybeFuncs ""
Left "String cannot be empty!"
>> runMaybeFuncs "Hi"
Left "Length cannot be even!"
>> runMaybeFuncs "Hithere"
Left "Float is too large!"
>> runMaybeFuncs "Hit"
Right [9,10]

Notice we parameterize the Either monad by the error type. If we have:

maybeFunc2 :: Either CustomError Float
…

This function is in a different monad now. It won’t be quite as simple to combine this with our other functions. If you’re curious how we might do this, check out this answer on quora.

The IO Monad

The IO Monad is perhaps the most important monad in Haskell. It is also one of the hardest monads to understand starting out. Its actual implementation is a bit too intricate to discuss when first learning monads. So we’ll learn by example.

The IO monad wraps computations in the following context: “This computation can read information from or write information to the terminal, file system, operating system, and/or network”. If you want to get user input, print a message to the user, read information from a file, or make a network call, you’ll need to do so within the IO Monad. These are “side effects”. We cannot perform them from “pure” Haskell code.

The most important job of pretty much any computer program is to interact with the outside world in some way. For this reason, the root of all executable Haskell code is a function called main, with the type IO (). So every program starts in the IO monad. From here you can get any input you need, call into relatively “pure” code with the inputs, and then output the result in some way. The reverse does not work. You cannot call into IO code from pure code, the same way you can call into a Maybe function from pure code.

Let’s look at a simple program showing a few of the basic IO functions. We’ll use do-notation to illustrate the similarity to the other monads we’ve discussed. We list the types of each IO function for clarity.

main :: IO ()
main = do
  -- getLine :: IO String
  input <- getLIne
  let uppercased = map Data.Char.toUpper input
  -- print :: String -> IO ()
  print uppercased

So we see once again each line of our program has type IO a. (A let statement can occur in any monad). Just as we could unwrap i in the maybe example to get an Int instead of a Maybe Int, we can use <- to unwrap the result of getLine as a String. We can then manipulate this value using string functions, and pass the result to the print function.

This is a simple echo program. It reads a line from the terminal, and then prints the line back out in all caps. Hopefully it gives you a basic understanding of how IO works. We’ll get into more details in the next couple articles.

Summary

A monad wraps computations in a particular context. It defines functions for wrapping values in its context, and combining operations in the context. Maybe is a monad. We describe its context by saying its computations can succeed or fail. Either is similar to Maybe, except it can add error information to failures. The IO monad is hugely important, encapsulating the context of operations reading from and writing to the terminal, network, and file system. The easiest way to learn monadic code is to use do notation. In this notation, every line has a right-side value of the monad. You can then unwrap the value on the left side using the <- operator.

Stay tuned next week as we continue our exploration of monads. We’ll examine the Reader and Writer monads, and demonstrate how they encapsulate different kinds of side effects then we might get from the IO monad.

Hopefully this article has started you off on (finally) understanding monads. If you haven’t written any Haskell code yet and want to get started so you can test your knowledge of monads, be sure to check out our free checklist for getting started with Haskell!

Not quite ready for monads but want to try some different Haskell skills? Check out our recursion workbook. It includes 2 chapters of material on recursion and higher order functions, as well as 10 practice problems with a test harness.

Applicatives: One Step Further

So last week, we discussed the Functor typeclass. We found it allows us to run transformations on data regardless of how the data is wrapped. No matter if our data were in a List, a Maybe, an Either, or even a custom type, we could simply call fmap. However, what happens when we try to combine wrapped data? For instance, if we try to have GHCI interpret these calculations, we’ll get type errors:

>> (Just 4) * (Just 5)
>> Nothing * (Just 2)

Functors Falling Short

Can functors help us here? We can use fmap to wrap multiplication by the particular wrapped Maybe value:

>> let f = (*) <$> (Just 4)
>> :t f
f :: Num a => Maybe (a -> a)
>> (*) <$> Nothing
Nothing

This gives us a partial function wrapped in a Maybe. But we still cannot unwrap this and apply it to (Just 5) in a generic fashion. So we have to resort to code specific to the Maybe type:

funcMaybe :: Maybe (a -> b) -> Maybe a -> Maybe b
funcMaybe Nothing _ = Nothing
funcMaybe (Just f) val = f <$> val

This obviously won’t work with other functors types.

Applicatives to the Rescue

This is exactly what the Applicative typeclass is for. It has two main functions:

pure :: a -> f a
(<*>) :: f (a -> b) -> f a -> f b

The pure function takes some value and wraps it in a minimal context. The <*> function, called sequential application, takes two parameters. First, it takes a function wrapped in the context. Next, a wrapped value. Its output is the result of applying the function to the value, rewrapped in the context. An instance is called an applicative functor because it allows us to apply a wrapped function. Since sequential application takes a wrapped function, we typically begin our use of applicatives by wrapping something with either pure or fmap. This will become more clear with some examples.

Let’s first consider multiplying Maybe values. If we are multiply by a constant value we can use the functor approach. But we can also use the applicative approach by wrapping the constant function in pure and then using sequential application:

>> (4 *) <$> (Just 5)
Just 20
>> (4 *) <$> Nothing
Nothing
>> pure (4 *) <*> (Just 5)
Just 20
>> pure (4 *) <*> Nothing
Nothing

Now if we want to multiply 2 maybe values, we start by wrapping the bare multiplication function in pure. Then we sequentially apply both Maybe values:

>> pure (*) <*> (Just 4) <*> (Just 5)
Just 20
>> pure (*) <*> Nothing <*> (Just 5)
Nothing
>> pure (*) <*> (Just 4) <*> Nothing
Nothing

Implementing Applicatives

From these examples, we can tell the Applicative instance for Maybe is implemented exactly how we would expect. The pure function simply wraps a value with Just. Then to chain things together, if either the function or the value is Nothing, we output Nothing. Otherwise apply the function to the value and re-wrap with Just.

instance Applicative Maybe where
  pure = Just
  (<*>) Nothing _ = Nothing
  (<*>) _ Nothing = Nothing
  (<*>) (Just f) (Just x) = Just (f x)

The Applicative instance for Lists is a little more interesting. It doesn’t exactly give the behavior we might first expect.

instance Applicative [] where
  pure a = [a]
  fs <*> xs = [f x | f <- fs, x <- xs]

The pure function is what we expect. We take a value and wrap it as a singleton in a list. When we chain operations, we now take a LIST of functions. We might expect to apply each function to the value in the corresponding position. However, what actually happens is we apply every function in the first list to every value in the second list. When we have only one function, this results in familiar mapping behavior. But when we have multiple functions, we see the difference:

>> pure (4 *) <*> [1,2,3]
[4,8,12]
>> [(1+), (5*), (10*)] <*> [1,2,3]
[2,3,4,5,10,15,10,20,30]

This makes it easy to do certain operations, like finding every pairwise product of two lists:

>> pure (*) <*> [1,2,3] <*> [10,20,30]
[10,20,30,20,40,60,30,60,90]

You might be wondering how we might do parallel application of functions. For instance, we might want to use the second list example above, but have the result be [2,10,30]. There is a construct for this, called ZipList! It is a newtype around list, whose Applicative instance is designed to use this behavior.

>> ZipList [(1+), (5*), (10*)] <*> [5,10,15]
ZipList {getZipList = [6,50,150]}

Summary

1. Applicative functors take the idea of normal functors one step further.
2. They allow function application to occur within the wrapper context.
3. In some circumstances, this allows us to reuse generic code.
4. In other cases, this gives us clean idioms to express simple concepts and solve common problems.

The Easiest Haskell Idiom

Once you master the basics of Haskell, the next important step is to understand the patterns that make it easier to write good, idiomatic Haskell code. The next few posts will focus on some of the most important patterns to learn. The simplest of these is functors.

A Simple Example

Here’s a simple example to start us on our way. This code converts an input string like “John Doe 24” into a tuple. We want to consider all inputs though, so the resulting type is a Maybe.

tupleFromInputString :: String -> Maybe (String, String, Int)
tupleFromInputString input = if length stringComponents /= 3
  then Nothing
  else Just (stringComponents !! 0, stringComponents !! 1, age)
  where 
    stringComponents = words input
    age = (read (stringComponents !! 2) :: Int)

This simple function simply takes a string and converts it into parameters for first name, last name, and age. Suppose we have another part of our program using a data type to represent a person instead of a tuple. We might write a conversion function between these two different types. We want to account for the possibility of failure. So we’ll have another function handling that case.

data Person = Person {
  firstName :: String,
  lastName :: String,
  age :: Int
}

personFromTuple :: (String, String, Int) -> Person
personFromTuple (fName, lName, age) = Person fName lName age

convertTuple :: Maybe (String, String, Int) -> Maybe Person
convertTuple Nothing = Nothing
convertTuple (Just t) = Just (personFromTuple t)

A Change of Format

But imagine our original program changes to read in a whole list of names:

listFromInputString :: String -> [(String, String, Int)]
listFromInputString contents = mapMaybe tupleFromInputString (lines contents)

tupleFromInputString :: String -> Maybe (String, String, Int)
...

Now if we passed this result to the code using Person, we would have to change the type of the convertTuple function. It would have a parallel structure though. Maybe and List can both act as containers for other values. Sometimes, we don’t care how values are wrapped. We just want to transform whatever underlying value exists, and then return the new value in the same wrapper.

Introduction to Functors

With this idea in mind, we can start understanding functors. First and foremost, Functor is a typeclass in Haskell. In order for a data type to be an instance of the Functor typeclass, it must implement a single function: fmap.

fmap :: (a -> b) -> f a -> f b

The fmap function takes two inputs. First, it demands a function between two data types. The second parameter is some container of the first type. The output then is a container of the second type. Now let’s look at a few different Functor instances for some familiar types. For lists, fmap is simply defined as the basic map function:

instance Functor [] where
  fmap = map

In fact, fmap is a generalization of mapping. For example, the Map data type is also a functor. It uses its own map function for fmap. Functors simply take this idea of transforming all underlying values and apply it to other types. With this in mind, let’s observe how Maybe is a functor:

instance Functor Maybe where
  fmap _ Nothing = Nothing
  fmap f (Just a) = Just (f a)

This looks a lot like our original convertTuple function! If we have no value in the first place, then the result is Nothing. If we do have a value, simply apply the function to the value, and rewrap it in Just. The Either data type can be seen as a Maybe type with more information about how it failed. It has similar behavior:

instance Functor (Either a) where
    fmap _ (Left x) = Left x
    fmap f (Right y) = Right (f y)

Note the first type parameter of this instance is fixed. Only the second parameter of an Either value is changed by fmap. Based on these examples, we can see how to rewrite convertTuple to be more generic:

convertTuple :: Functor f => f (String, String, Int) -> f Person
convertTuple = fmap personFromTuple

Making Our Own Functors

We can also take our own data type and define an instance of Functor. Suppose we have the following data type representing a directory of local government officials. It is parameterized by the type a. This means we allow different directories using different representations of a person:

data GovDirectory a = GovDirectory {
  mayor :: a,
  interimMayor :: Maybe a,
  cabinet :: Map String a,
  councilMembers :: [a]
}

One part of our application might represent people with tuples. Its type would be GovDirectory (String, String, Int). However, another part could use the type GovDirectory Person. We can define the following Functor instance for GovDirectory by defining fmap. Since our underlying types are mostly functors themselves, this mostly involves calling fmap on the individual fields!

instance Functor GovDirectory where
  fmap f oldDirectory = GovDirectory {
    mayor = f (mayor oldDirectory),
    interimMayor = f <$> interimMayor oldDirectory,
    cabinet = f <$> cabinet oldDirectory,
    councilMembers = f <$> councilMembers oldDirectory
  }

Note <$> is simply a synonym for fmap. Now we have our own functor instance, sp transforming the underlying data type of our directory class is easy! We can just use:

convertTuple <$> oldDirectory

Summary

1. Functors, in general, wrap some kind of data
2. In Haskell, Functor is a typeclass, with a single function fmap
3. The fmap function allows us to transform the underlying data without caring how the data is contained.
4. This allows us to write much more flexible code in certain circumstances.

Stay tuned for next week, when we’ll discuss applicative functors! If you’re starting to get a grasp for Haskell and want to try new skills, be sure to check out our free workbook on Recursion, which comes with 10 practice problems!