Imperative Programming with The State Monad

A Tree Datatype

A tree with data at the leaves

Here’s an example Tree Char










Lets Work it Out!

Write a function to add a distinct label to each leaf

such that










Labeling a Tree











EXERCISE

Now, modify label so that you get new numbers for each letter so,

That is, a separate counter for each key a, b, c etc.

HINT Use the following Map k v type











Common Pattern?

Both the functions have a common “shape”

If we generally think of Int and Map Char Int as global state












State Transformers

Lets capture the above “pattern” as a type

  1. A State Type
  1. A State Transformer Type

A state transformer is a function that

  • takes as input an old s :: State
  • returns as output a new s' :: State and value v :: a











Executing Transformers

Lets write a function to evaluate an ST a









QUIZ

What is the value of quiz ?

A. 103

B. [100, 101, 102]

C. (103, [100, 101, 102])

D. [0, 1, 2]

E. Type error











Lets Make State Transformer a Monad!











EXERCISE: Implement returnST!

What is a valid implementation of returnST?












What is returnST doing ?

returnST v is a state transformer that … ???




(Can someone suggest an explanation in English?)












HELP

Now, lets implement bindST!











What is returnST doing ?

returnST v is a state transformer that … ???




(Can someone suggest an explanation in English?)












What is returnST doing ?

returnST v is a state transformer that … ???




(Can someone suggest an explanation in English?)












bindST lets us sequence state transformers

st >>= f

  1. Applies transformer st to an initial state s
    • to get output s' and value va
  2. Then applies function f to the resulting value va
    • to get a second transformer
  3. The second transformer is applied to s'
    • to get final s'' and value vb

OVERALL: Transform s to s'' and produce value vb











Lets Implement a Global Counter

The (counter) State is an Int

A function that increments the counter to return the next Int.

next is a state transformer that that returns String values












QUIZ

Recall that

What does quiz evaluate to?

A. "100"

B. "101"

C. "0"

D. "1"

E. (101, "100")













QUIZ

Recall the definitions

Now suppose we have

What does quiz evaluate to?

A. 100

B. 101

C. 0

D. 1

E. (101, 100)













Example













Riyadh Moosa

Example













QUIZ

Consider a function wtf2 defined as

What does quiz evaluate to?

A. Type Error!

B. [100, 100, 100]

C. [0, 0, 0]

D. [100, 101, 102]

E. [102, 102, 102]












Chaining Transformers

>>= lets us chain transformers into one big transformer!

So we can define a function to increment the counter by 3

And then sequence it twice to get








Lets do the above examples

Remember, do is just nice syntax for the above!

And then sequence it twice to get












Labeling a Tree with a “Global Counter”

Lets rewrite our Tree labeler with ST







Wow, compare to the old code!

Avoid worrying about propagating the “right” counters

  • Automatically handled by ST monad instance!










Executing the Transformer

In the old code we called the helper with an initial counter 0

In the new code what should we do?

Now, we should be able to exec the labelS transformer











How to implement keyLabel?

So far, we hardwired an Int counter as our State

Have to reimplement the monad if we want a different state?

  • e.g. Map Char Int to implement keyLabel

Don’t Repeat Yourself!











A Generic State Transformer

Don’t have separate types for IntList and CharList

  • Define a generic list [a] where a is a type parameter

  • Instantiate a to get [Int] and [Char]

Similarly, reuse ST with a type parameter!

  • State is represented by type s
  • Return Value is the type a (as before).














A Generic State Transformer Monad

Lets make the above a(n instance of) Monad

(exactly the same code as returnST and bindST)











Lets implement keyLabel

  1. Define a Map Char Int state-transformer
  1. Modify next to take a Char
  1. Modify helper to use charNext

Lets make sure it works!












Lets look at the final “state”

The returned Tree is

and the final State is














Generically Getting and Setting State

As State is “generic”

  • i.e. a type variable not Int or Map Char Int or …

It will be convenient to have “generic” get and put functions

  • that read and update the state















EXERCISE

Can you fill in the implementations of get and set ?

HINT Just follow the types…














Using get and put : Global Counter

We can now implement the plain global counter next as








Using get and put : Frequency Map

Lets implement the char-frequency counter charNext as











A State-Transformer Library

The Control.Monad.State module

  • defines a State-Transformer like above.

  • hides the implementation of the transformer

Clients can only use the “public” API

Your homework will give you practice with using these

  • to do imperative functional programming















The IO Monad

Remember the IO a or Recipe a type from this lecture

  • Recipes that return a result of type a
  • But may also perform some input/output

A number of primitives are provided for building IO recipes

Basic actions that can be “chained” via >>= etc.














A Recipe to Read a Line from the Keyboard









IO is a “special case” of the State-Transformer

The internal state is a representation of the state of the world

A Recipe is a function that

  • takes the current World as its argument
  • returns a value a and a modified World

The modified World reflects any input/output done by the Recipe

This is just for understanding, GHC implements IO more efficiently!