Sunday, February 19, 2017

Ten example uses of Monads

In this “monad tutorial” we are not going to learn what monads are, how they are implemented or how they work internally. Instead we are going to look at ten example use cases. We will look at monadic APIs for safe concurrency, build dependencies, stream processing, probabilistic programming, web server programming, mutable references, logic programming, test specification, parsing and HTML5 canvas manipulation.

There is a repository on github with a minimal complete example for each monad discussed. If you want to play with monads you should clone that repository and start from there. Each example in the repository comes with an idea for a small extension. In this post we will only look at a snippet from each example.

Probability

The probability monad allows you to describe and compose probability distributions. The following snippet describes the normalized probability of possible outcomes when you roll two twenty-sided dice and take the maximum of the two rolls.

enemyRolls :: Probability Int
enemyRolls = norm (do
  firstRoll <- twentySided
  secondRoll <- twentySided
  return (max firstRoll secondRoll))

Check out the full example to see how we can compose this probability distribution with others to calculate your odds of winning in a made-up role-playing game scenario.

STM

STM stands for software transactional memory. The following swaps the content of two variables in a transaction.

swapTVars :: TVar Int -> TVar Int -> STM ()
swapTVars tvar1 tvar2 = do

    value1 <- readTVar tvar1
    value2 <- readTVar tvar2

    writeTVar tvar1 value2
    writeTVar tvar2 value1

We can execute this transaction atomically. Or we can compose it with other transactions into one big transaction before doing so. In the full example we fork 100001 threads that concurrently try to swap the content of the same two variables.

In software transactional memory we do not block other threads when we want to execute a transaction atomically. We just execute it, watch out for conflicts and roll back if necessary. This rollback is always possible because we know that actions in the STM monad do not have side effects.

(Build) Action

Shake is a build system embedded into Haskell. The following snippet describes a build action. It reads a newline-delimited list of file names from the file "shake-data/filenames". It sums the total number of lines in all listed files and writes the result to the file at linecountPath.

linecountAction :: FilePath -> Action ()
linecountAction linecountPath = do

  fileNames <- readFile' "shake-data/filenames"

  fileContents <- forM (lines fileNames) readFile'

  let linecount = sum (map (length . lines) fileContents)

  writeFile' linecountPath (show linecount)

When we run this program it remembers which files it read and wrote and skips work when we invoke it a second time and nothing changed.

You describe which action to take for each file-type in the Rules monad. The full example shows how to do that. Shake is a viable replacement for make.

ST

Sometimes it is easier or more efficient to express an algorithm imperatively with explicit memory mutation instead of declaratively with immutable data. The histogram function in the following snippet is such an example. In Haskell we use the ST (state thread) monad for this.

histogramST :: Vector Word8 -> ST s (MVector s Int)
histogramST vector = do

  resultVector <- MVector.new 256

  MVector.set resultVector 0

  Vector.forM_ vector (\value -> do

    MVector.modify resultVector (+1) (fromIntegral value))

  return resultVector

The full example exposes a pure histogram function that uses the histogramST function internally and freezes the resulting vector afterwards. This is an example of how monads allow us to keep side-effects local.

Pipe

A pipe awaits values from upstream and yields values to downstream. The following snippet is a pipe that awaits messages from upstream and only yields them to downstream when the time since the previous message is larger than 3.

rateLimitLoop :: (Monad m) => Message -> Pipe Message Message m r
rateLimitLoop previousMessage = do

  message <- await

  let timeDifference =
        timestamp message - timestamp previousMessage

  if timeDifference > 3
      then do
          yield message
          rateLimitLoop message
      else do
          rateLimitLoop previousMessage

In the full example we compose this pipe with others and then run it on a stream of messages.

ScottyM

Let’s look at a how we’d write a silly web application using the scotty web framework: ALLCAPS AS A SERVICE. When a user requests a route like "/allcaps/example" we respond with the text EXAMPLE.

routes :: ScottyM ()
routes = do
  get "/" rootAction
  get "/allcaps/:input" allcapsAction

allcapsAction :: ActionM ()
allcapsAction = do
  input <- param "input"
  text (Text.toUpper input)

In the full example we start our web server locally and listen for requests on port 3000.

Spec

Writing tests is an important part of software development. In the following snippet we specify tests for a capitalize function that we define in the full example.

capitalizeSpec :: Spec
capitalizeSpec = do

  specify "Capitalizes \"monad\"" (do
    capitalize "monad" `shouldBe` "Monad")

  specify "Empty string" (do
    capitalize "" `shouldBe` "")

  specify "Allcaps string" (do
    capitalize "NOTATION!" `shouldBe` "Notation")

  specify "Is idempotent" (do
    property (\s -> capitalize (capitalize s) == capitalize s))

We have three test cases and one property that is checked on randomly generated inputs. If you run the tests you will detect a typo in the test specification.

Logic

The logic monad provides us with a declarative way to to create backtracking search algorithms. In this example we use the expressions function from the following snippet to search for solutions to the four fours puzzle.

expressions :: Int -> Logic Expression
expressions numberOfFours = case numberOfFours of

  1 -> do
    return Four

  _ -> do
    numberOfFoursLeft <- choose [1 .. numberOfFours - 1]

    let numberOfFoursRight = numberOfFours - numberOfFoursLeft

    expressionLeft <- expressions numberOfFoursLeft
    expressionRight <- expressions numberOfFoursRight
    operator <- choose [Add, Subtract, Multiply, Divide]

    when (operator == Divide) (
      guard (not (evaluate expressionRight == 0)))

    return (Binary operator expressionLeft expressionRight)

The expressions function generates arithmetic expressions that contain exactly the given number of fours. When we have to generate an expression that contains exactly one four we return a constant Four. When we have to generate an expression that contains more than one four we generate a binary operation (Add, Subtract, Mutliply, Divide) between two expressions. We non-deterministically split the number of fours for the left-hand-side and the right-hand-side of the binary operator.

Parser

A monadic API is particularly nice for parsing. In this example we parse strings that represent chemical formulas like "H2O" or "NaCl". The following snippet is a part of that parser. It parses a chemical element like "H" or "Na", optionally followed by a decimal number. If there is no number we return a default number of 1.

elementAndNumberParser :: Parser (Element, Int)
elementAndNumberParser = do
  element <- elementParser
  number <- option 1 decimal
  return (element, number)

Monadic parsers can parse any file format, but you can also use them as a more verbose, typed and compositional alternative to regular expressions.

Canvas

Let’s write JavaScript in Haskell. This is a translation of the HTML5 canvas example taken from here.

canvas :: Canvas ()
canvas = do

  fillStyle("cornflowerblue")
  strokeStyle("red")

  shadowColor("rgba(50, 50, 50, 1.0)")
  shadowOffsetX(2)
  shadowOffsetY(2)
  shadowBlur(4)

  lineWidth(20)
  lineCap("round")

  beginPath()
  moveTo(120.5, 130);
  quadraticCurveTo(150.8, 130, 160.6, 150.5)
  quadraticCurveTo(190, 250.0, 210.5, 160.5)
  quadraticCurveTo(240, 100.5, 290, 70.5)
  stroke()

The full example starts a web server on port 3000 that generates the corresponding JavaScript code and ships it to the client where it draws the following picture:

Red tick drawn with blank-canvas

You can use Haskell to abstract over and compose JavaScript snippets. Neat, right?

That’s it

Monads are everywhere. I hope this convinces you that they are not magical, abstract or hard to use.

No comments:

Post a Comment