Monads

Abstracting Code Patterns

a.k.a. Dont Repeat Yourself

Lists




Rendering the Values of a List




Squaring the values of a list




Common Pattern: map over a list

Refactor iteration into mapList

Reuse map to implement inc and sqr

Trees




Incrementing and Squaring the Values of a Tree

QUIZ: map over a Tree

Refactor iteration into mapTree! What should the type of mapTree be?









Lets write mapTree

QUIZ

Wait … there is a common pattern across two datatypes

Lets make a class for it!

What type should we give to map?







Reuse Iteration Across Types

Haskell’s libraries use the name Functor instead of Mappable

And now we can do

Exercise: Write a Functor instance for Result

When you’re done you should see

Next: A Class for Sequencing

Recall our old Expr datatype

But, what is the result

A crash! Lets look at an alternative approach to avoid dividing by zero.

The idea is to return a Result Int (instead of a plain Int)

  • If a sub-expression had a divide by zero, return Error "..."
  • If all sub-expressions were safe, then return the actual Result v

The good news, no nasty exceptions, just a plain Error result

The bad news: the code is super duper gross

Lets spot a Pattern

The code is gross because we have these cascading blocks

but really both blocks have something common pattern

  1. Evaluate e
  2. If the result is an Error then return that error.
  3. If the result is a Value v then do further processing on v.

Lets bottle that common structure in two functions:

  • >>= (pronounced bind)
  • return (pronounced return)
Bottling a Magic Pattern
Bottling a Magic Pattern

NOTE: return is not a keyword; it is just the name of a function!

A Cleaned up Evaluator

The magic bottle lets us clean up our eval

The gross pattern matching is all hidden inside >>=

Notice the >>= takes two inputs of type:

  • Result Int (e.g. eval e1 or eval e2)
  • Int -> Result Int (e.g. The processing function that takes the v and does stuff with it)

In the above, the processing functions are written using \v1 -> ... and \v2 -> ...

NOTE: It is crucial that you understand what the code above is doing, and why it is actually just a “shorter” version of the (gross) nested-case-of eval.

A Class for >>=

Like fmap or show or jval or ==, or <=, the >>= operator is useful across many types!

Lets capture it in an interface/typeclass:

Notice how the definitions for Result fit the above, with m = Result

Syntax for >>=

In fact >>= is so useful there is special syntax for it.

Instead of writing

you can write

Thus, we can further simplify our eval to:









Writing Applications

In most language related classes, we start with a “Hello world!” program.

With 130, we will end with it.

Purity and the Immutability Principle

Haskell is a pure language. Not a value judgment, but a precise technical statement:

The “Immutability Principle”:

  • A function must always return the same output for a given input

  • A function’s behavior should never change









No Side Effects

Haskell’s most radical idea: expression ==> value

  • When you evaluate an expression you get a value and nothing else happens

Specifically, evaluation must not have an side effects

  • change a global variable or

  • print to screen or

  • read a file or

  • send an email or

  • launch a missile.









Purity

Means functions may depend only on their inputs

  • i.e. functions should give the same output for the same input every time.









But… how to write “Hello, world!”

But, we want to …

  • print to screen
  • read a file
  • send an email

A language that only lets you write factorial and fibonacci is … not very useful!

Thankfully, you can do all the above via a very clever idea: Recipe









Recipes

This analogy is due to Joachim Brietner

Haskell has a special type called IO – which you can think of as Recipe

A value of type Recipe a is

  • a description of an effectful computations

  • when when executed (possibly) perform some effectful I/O operations to

  • produce a value of type a.

Recipes have No Effects

A value of type Recipe a is

  • Just a description of an effectful computation

  • An inert, perfectly safe thing with no effects.

Cake vs. Recipe
Cake vs. Recipe

(L) chocolate cake, (R) a sequence of instructions on how to make a cake.

They are different (hint: only one of them is delicious.)

Merely having a Recipe Cake has no effects: holding the recipe

  • Does not make your oven hot

  • Does not make your your floor dirty

Executing Recipes

There is only one way to execute a Recipe a

Haskell looks for a special value

The value associated with main is handed to the runtime system and executed

Baker Aker
Baker Aker

The Haskell runtime is a master chef who is the only one allowed to cook!

How to write an App in Haskell

Make a Recipe () that is handed off to the master chef main.

  • main can be arbitrarily complicated

  • will be composed of many smaller recipes

Hello World

The function putStrLn

  • takes as input a String
  • returns as output a Recipe ()

putStrLn msg is a Recipe () when executed prints out msg on the screen.

… and we can compile and run it

QUIZ: Combining Recipes

Next, lets write a program that prints multiple things:

What must the type of combine be?





Using Intermediate Results

Next, lets write a program that

  1. Asks for the user’s name using
  1. Prints out a greeting with that name using

Problem: How to pass the output of first recipe into the second recipe?





QUIZ: Using Yolks to Make Batter

Suppose you have two recipes

and we want to get

What must the type of combineWithResult be?





Looks Familar

Wait a bit, the signature looks familiar!

Remember this

Recipe is an instance of Monad

In fact, in the standard library

So we can put this together with putStrLn to get:

or, using do notation the above becomes

Exercise

  1. Compile and run to make sure its ok!
  2. Modify the above to repeatedly ask for names.
  3. Extend the above to print a “prompt” that tells you how many iterations have occurred.








Monads are Amazing

Monads have had a revolutionary influence in PL, well beyond Haskell, some recent examples

  • Error handling in go e.g. 1 and 2

  • Asynchrony in JavaScript e.g. 1 and 2

  • Big data pipelines e.g. LinQ and TensorFlow








A Silly App to End CSE 130

Lets write an app called moo inspired by cowsay

A Command Line App

moo
moo

moo works with pipes

Thanks, and good luck for the final!
Thanks, and good luck for the final!