then it was rediscovered in computer science in the 1990s. And what it gives

you, is a new way of thinking about programming with effects. And for me, this

is one of the most important new ideas in programming languages in the last 25

years. So that's what we're going to be looking at today - programming with monads.

We're going to come at this using a simple example, and the example that

we're going to look at is the idea of writing a function that evaluates simple

expressions. And I'm going to use Haskell for this, but it doesn't matter if you don't

know anything about Haskell, because we're going to use it in a very simple

way, and I'm going to explain everything as we're going along. So, what we're going

to start with, is by defining a simple datatype for the kind of expressions

that we're going to be evaluating. So, we'll use the data keyword in Haskell,

which introduces a new data type, and then we're going to define a new data

type for expressions. And then there's two things that an expression can be. It

can either be an integer value, so we'll write that down - we have Val of an Int.

Or, it can be the division of two sub-expressions. So we've got two

constructors here in our data type - we've got Val,

which builds expressions from integers, and we've got Div, which builds expressions

from two sub-expressions. So, just to reiterate what what's actually going on

here, we're declaring a new data type called Expr, and it's got two new

constructors - one called Val, which takes an integer parameter, and one

called Div, which takes two sub-expressions as parameters as well.

So basically what we're working with is expressions that are built up from

integer values using a simple division operator. So, many of you may not be

familiar of this kind of syntax, so let's have a couple of examples of values of

this data type, so that we make sure everyone's on the same page. So, what I'm

going to do here, is draw a little table. So, on one side, on the left-hand side, I'm

going to have what we would normally write down in mathematics. And then on

the right-hand side, we'll think how would you translate this into a value in

this Haskell data type? So, let's have three simple examples here - we'll have

one, and we'll have six divided by two, and

let's do one more example, we'll have six divided by three divided by one. So, these are

simple expressions built up from integers using a division operator. But, we're

writing Haskell programs today, so let's think how do these things actually get

represented as values of our expression data type? So, the first one is very

simple - if we want to represent the value one, we just need to use the Val tag, so we

write Val of one. If we want to have an expression like six divided by two, well it's

a division, so we have a Div at the top level, and then we have two values - we

have Val six, and Val two. And actually, I'll leave the last one is a little exercise

for you here, so you can try this one for yourself - how do you represent this as a

value in Haskell? Well, you're gonna need two divisions, you're going to need three

Val constructors, and then a bunch of brackets. So, this is the basic idea -

we've got simple expressions built up from integers using division, and we want

to think about how do we write a program to evaluate these expressions? Let's

write a program to do that. So, we're going to write an evaluator, and it's

going to be a program, or a function in this case, that takes an expression as

input, and what it's going to give back is the integer value of that expression.

And there's going to be two cases here, because we have two kinds of expressions.

We have a case for values, and we need to figure out what to do with that, which

we'll do in a moment. And then we have a case for division, and we need to think

what to do with that. So, we've got the skeleton here of a program, and then we

just need to fill in the details. So, how do you evaluate an integer value? Well,

that's very simple, you just give back the number - so if I had Val of one,

it's value is just one. And then how do I evaluate a division? Well, these two

expressions here, x and y, these could be as complicated as you wish. So, we need to

evaluate these recursively. So what we would do, is evaluate the first one, x, and

that will give us an integer. And then we'll evaluate the second one, y, and that

will give us another integer. And then, all we need to do is divide one by the

other. So, this is a nice simple program that evaluates these kind of expressions

built up from integers using division - we just have a simple recursive program, two

cases, and everything looks fine. But there's a

problem with this program, and the problem is that it may crash - because if

you divide a number by zero, then that's undefined, so this program will just

crash. So, in particular, if the value of the expression y here was zero, then this

division operator would crash, and you get some kind of runtime error. So we

don't want our programs to crash, so we think, what do we do to fix this problem?

First of all, what we're going to do is we're going to define a safe version of

the division operator, which doesn't crash anymore. Because that's basically

the root of the problem here - division by zero gives an undefined result, and the

program is going to crash. So, let's define a safe version of the division

operator. We're going to define a function called safediv, and it's going

to take a couple of integers, and it's going to give back Maybe an integer. And

Maybe is the way that we deal with things that can possibly fail in Haskell.

So, the type here is not Int to Int to Int, it's Int to Int to Maybe Int, because

division may fail. And we'll see how this Maybe type works in a moment. So, how do

we actually define safediv? We take two integers, n and m, and then what we'll do

is check - is the second of these zero? Because that's the case when things

would go wrong. So, if m happened to be zero, then we will give back the result

Nothing. Okay, so Nothing is one of the constructors in the Maybe type. If m is

not zero, what we're going to do is Just give back the result of dividing. So, Just

is another constructor in the Maybe type - Maybe only has two constructors, Nothing,

which represents things that have gone wrong, or in our case division by zero,

and Just, which represent things that have gone fine. In this case, we actually

just get back the result of dividing one number by the other. So, what we have here

now is a safe version of the division operator, which is explicitly checking

for the case when the program would have crashed. So this doesn't crash anymore, it

returns one of two values - either Nothing if things go wrong, or Just of the

division if things have gone fine. So, what we can do then, with this safe

division operator, is rewrite our little evaluator program to make sure that it

doesn't crash. So, our new evaluator is going to have a slightly different type

than before. So before, the original program just took an expression

as input, and then it gave back an integer. But that program could crash. The

new evaluator takes an expression as input as before, but now it Maybe gives

you an integer, because it could fail, it could have division by zero. So, how do we

rewrite this evaluator? So, we'll do the two cases again - write down the skeleton,

and then we'll fill in the details. So, in the base case, we can't just return n

this time, because we've got to return a Maybe value. And there's only two things

we could return, either Nothing or Just, and in this case the right thing to do

is to return Just of n, because if you evaluate a value that's always going to

succeed, so we use a success tag, which is Just, and then we have the integer

value sitting in here. If we have a division, now we need to do a bit more

work, because when we evaluate x that may fail, when we evaluate y that may fail,

and then when we do the division that may fail. So, we're going to need to do a

little bit of checking and management of failure. So, what we're going to do, is

when we evaluate a division, first of all, we'll do a case analysis on the result

of evaluating x. And that could be one of two things - it could either be Nothing, in

which case we're going to do something, or we could get Just of some number, in

which case we're going to do something. So, there's two cases to consider - when we

evaluate the first parameter x, either it succeeds or it fails. So in the failure

case, if we get back Nothing, the only sensible thing to do is just to say, well

if evaluation of x fails, the evaluation of the whole division fails. So we'll

just return Nothing as well. In the Just case, then we need to evaluate the second

parameter y. So, what we're going to do is do another case analysis, we'll do a case

eval of y, and then again there's two possible outcomes which we could have

here - either we could have Nothing, which means it failed, or we could have Just of m,

some other number, in which case we've succeeded. Then again, we need to think

what do we do in each of these two cases. So, in the first case, if the evaluation

of y fails, the only sensible thing to do is say, well, we fail as well. In the

second case, we've now got to successfully evaluated expressions - x has

given the result n, y has given the result m, and now we can do the safe

division. So, in this case we just do safediv. Now we have a working evaluator.

We started off with a two-line program, which kind of did the essence of

evaluation, but it didn't check for things going wrong - it didn't check for a

division by zero. Now we've fixed the problem completely, we

have a program which works, this program will never crash, it will always give a

well-defined result, either Nothing or Just, but there's a bit of a problem with

this program, in that it's a bit too long. It's a bit too verbose, there's

quite a lot of noise in here, I can hardly see what's going on anymore,

because it's all of this management of failure. So, we can look at this program,

and think - how can we make this program better? And how can we make it more like

the original program, that didn't work, but still maintain the fact that this

actually does the right thing? And the idea here, is we're going to observe a

common pattern. So, when you look at this program, you can see quite clearly we're

doing the same thing twice - we're doing two case analyses. What we're doing, is

doing a case analysis on the result of evaluating x, and if it's Nothing we give

back Nothing, and if it's Just, we do something with the result. And then we do

exactly the same thing with eval of y - we're doing a case analysis on the

result of evaluating y, if that gives Nothing we give back Nothing, and if it's

a Just, we do something with it. So, a very common idea in computing is

when you see the same things multiple times, you abstract them out, and have

them as a definition. And that's what we're going to do here. So, let's draw a

little picture first, to capture the pattern which we've seen twice. So, the

pattern we have here, is we're doing a case analysis on something, so let me

just draw as a little box - we don't know what's in there, we're doing a case

analysis on something. And, there's two cases - if it's Nothing, we give back

Nothing, and if we get Just of some value x, then what we're going to do is we're

going to process it in some way, we're going to apply some other function to x.

So, this is the pattern which we've seen twice. In the first case, we had eval of x

sitting here, and in the second case, we had eval of y sitting here, but this is

the same pattern that we see two times in the new evaluator

which we've just written. So, what we can do now, is abstract this out as a

definition. And the idea here, is that we're going to give names to these boxes.

So, this box is a Maybe value - it's going to be either Nothing or a Just, so we'll

call it m. And this box is going to be a function, it's going

process the result in the case we're successful, so we'll call this f. So, we

can turn this picture here into a definition now, and then we can use it to

make our program simpler. So, the definition we're going to have is,

if we have some Maybe value, feeding into, or in sequence with, some function f. So,

the operator we're defining here is this funny sequencing symbol, and we'll

back to that in a second. What we're going to do, is a case analysis - we're

going to look at what the Maybe value is - if it's Nothing,

we'll give back Nothing, and if it's Just of x, we'll apply the function to it. Okay,

so we'll just captured the pattern, which we've seen twice, by a definition now. So,

we have some Maybe value, then, or in sequence with, some function f, and all

we're going to do is look at what the value of the Maybe is - if it's failed,

we'll fail, if it succeeds, we pass the result to the function f. It's just the

idea of abstracting out a common pattern as a definition. So, now we can use this

definition to make our program simpler. So, let's rewrite our evaluator once

again. The type will remain the same - it takes in an expression as input, and

it's going to give back a Maybe value, as before. But the definition is going

to be a bit simpler this time. So, let's write down the skeleton. So, if we