0:04

Alright, in this section I just want to show some more examples of data type

bindings in particular, because the only example I've show you so far was just a

silly example that didn't actually do anything useful.

So I want to explore the idea of one of types and some of the common idioms that

we see them used for. Alright.

So these example will be small. But they'll nonetheless be indicative of

the sort of things to use data types for. So the simplest example is probably just

for what's e-nums or enumerations are used for in other languages.

If you haven't heard of those, no problem.

So supposed I just want to represent what suit a playing card is.

So in English, every playing card is either a club, a diamond, a heart, or a

spade. So it would be a great example to just

have a datatype binding. I have a new type suite, and then if I

want to do something for each possible suite I can just have a case expression

that has one branch for each pattern. If you don't do this with an enumeration

you end up just encoding something like oh, one is for club, two is for diamond,

three is for heart. And that sort of thing is hard to keep

track of, you don't get as much error checking,

it's harder to read. Data types are perfect for this.

Now what's interesting is this is a very simple use of data types because none of

the constructors, club, diamond, heart, spade, carried any data, there were no

underlying values, and that's fine data types just can do more than that.

So another example is if I wanted the rank of a playing card.

So this is the thing that in America is called a Jack, a Queen, a King or an Ace

or is a number between two and ten. So the second data type I have here can

represent that fairly well, you could argue that by doing num of int I'm not

restricting that int to be between two and ten, it could be negative seven, it

could be a 142. But this is still a pretty good concise

way, a very readable way to read the rank part of a playing card.

You would then, and we'll see how to do this in a future segment, create an each

of type that had a suit and a rank. And that would represent a card.

Alright, so another common pattern, another common idiom that we use data

types for is when we just have alternate ways of identifying some object, some

thing that we're representing in our program.

So suppose I had a bunch of students in my class.

And mostly I wanted to represent them by some sort of student number.

But some of the students were say, just taking a pass/fail or just sitting in,

they were turning in the homework but they didn't have a student number.

So then what I might want, is some type, like called ID, for student ID, that was

either an int, which I'll mark with a constructor student num.

Or a name, which could have a first name, a last name, and maybe an optional middle

name. And since for each student I only want

one of these possibilities. I don't want any confusion, I don't want

all of this stuff. this is a perfectly reasonable way to

represent them. So compare it if you will to trying to do

that same idea with each of types and unfortunately students often do this and

we often even see code and programming languages that encourage using each of

types when you have conceptually one of type.

So here's something that's really bad style Let's do the same idea where we

have a record, with a STUDENTNUM field, a FIRST field, a MIDDLE field, and a LAST

field, but we'll say, even though students' IDs have all these, you should

never use them all. And what we'll do is we'll say the

STUDENTNUM is what you should use, but if it's minus one, or some other special

value, then ignore it and use the first middle and last field.

Alright? So what don't I like about this approach?

You're basically giving up all the benefits of using a language concert that

enforces that you have a 1-0 type. You're getting no help that people should

only use a number or a name, not both. You have to read this comment to

understand that you have to expect a minus one value and react accordingly.

It just makes it a lot less clear, what it is that you're actually doing.

And that's why in any programming language, it's worth learning how 1-0

types should be represented, and then using that pattern when it's the right

thing to do. Alright, now that said, this is a bit of

a strange example because there are situations where it makes sense to use an

each of type to represent students. Suppose we just had a slightly different

thing we were modeling, where every person does have a name and optionally

has a student number. And I want to have both of those.

Well if you want both things then each of is exactly the right thing, and you

should use a record time like you see here.

This student num should just be an int option.

Don't use minus one, it's too hard to remember to check for it.

Use and options, which is the sum of a number, or none.

That's the one of. And then the first, middle and last names

should always be present. Since the middle name may not always be

present, we'll make that an option as well.

So this is a big thing you have to do when you're designing your software, is

understand what kind of data you want, how you're going to model those things in

your program, and then use the right kind of compound types, to directly capture

the idea of what you're doing. Alright.

So that's all good. Now, in the rest of the segment, let me

focus on an example of another kind of data type binding that's going to be

recursive, and is going to be near and dear to our hearts.

Because it's how you represent things like programming languages themselves.

So here's the last data type binding I'm going to show you in this segment.

It's called X for expression. And it defines a little language if you

will of arithmetic expressions. So it says, an expression is one of the

following things. It's either a constant, which holds an

ent. Or a negation of a smaller expression;

not just an INT, but any smaller expression.

An add, an addition of two smaller expressions, or a multiply of two smaller

expressions. So notice how we're using self-reference

here. Many of the constructors themselves hold

other Xs the same way a list in its tail holds another list.

And what we're actually doing is defining a set of trees.

The set of trees that this data type binding represents are trees where at the

leaves are constants, with a number attached.

And at the internal nodes, are either negate, which has one child, one smaller

expression. Or, add and multiply, that have two

smaller expressions. So NML, once we have this data type

binding, we could write an expression like you see here in the middle.

We could just call the add constructor with two arguments that each themselves

have type X. The first one could be constant, which we

just need to call with any thing of type int.

Like the result of the expression ten plus nine.

And then negate, which has to be called with one expression.

And another expression could be the constant four.

So that's how we would write these MML. But what I want you to have in your head

is this tree version of it. To think of this expression as evaluating

to this value. It's a tree that has add here at the

root, two children constant, which holds a nineteen, and negate, which itself has

a child which is a constant that holds four.

And so every value of type X is going to look like some sort of tree that has this

kind of shape. So now we very concisely, in just a

4-line data binding, described a set of trees that represent an interesting

collection of arithmetic expressions. And now what we could do is we could

write functions that operate over things of type x.

And probably the most obvious type of functions, to write is something that

takes an X and returns the integer you get if you evaluate it.

Right. So we have a little language here.

Let's write a function, e-val of type X arrow int.

So we're going to take any X and we're going to return the int that arithmetic

expression should evaluate to if you actually ran it.

So here's what we would do, we would have a case expression.

We would say, well, any X is built with constant, negate or multiply.

What should we do in each case? Well, if it's built with constant.

Let's get the underlying int out. That's the result.

That's the number. But what if we have a negate.

Well then we have some smaller expression here.

We'll bind it to E2. So now over here in this right branch, we

have an expression that is in the variable E2.

And what we could do is recursively call e-val on it.

And that will tell us the result of evaluating E2 in this little language.

And then we could use ML's negation operator to negate the result.

For add, lets bind a two local variables. The two sub trees, E1 and E2 recursively

call eval on both of them. Take those two numbers we get back and

use ML's plus, ML's addition to come up with the result.

And if you like that, multiply is very similar.

Create two variables. E1 and E2 for the two parts,

recursively called Eval, and then multiply them together.

So, it's perhaps not very surprising that functions over recursive data types, data

type bindings that have self reference like this, end up being recursive.

You want to do something useful within the X you have.

Usually you need to consider the smaller expressions that are in the subtrees of

that tree. And they way that your going to

recursively· find those and figure out how they're made is with a recursive

function call that then has it's own case expression.

All right. So that's most of the code I wanted to

show you. Everything I've shown you on the slides

is over here in the file. You'll also notice a second function

here, number of ads, and then I have some example codes.

So for example here's what I had on the slide.

So example X is just a little variable, mining of type X.

And then example ints what I call eval on example E, will just be something of type

int. I have one other, this function number of

ads, also, happens to have the same type as eval, X arrow int.

But what it does, is it doesn't run the expression doesn't, compute it's answer.

Instead, it just counts how many additions are anywhere in the expression.

And it's the same kind of recursive processing.

I'll just do a case on E. If it's a constant, there are no ads in

it. If it's in a gate, it has the same number

of ads that are in E two. So just recursively call number of ads

with E two, and that's our answer. If it is an ad,

well then, there's one ad. But we need to also include any ads that

are in the sub expressions. So let's recursively call number of ads,

E1, number of ads, E2, add those together, add one to that, that

will be our answer. And multiply is similar, except we don't

have the one plus. Because the multiply itself is not an ad.

And there's an example here of trying that out as well.

And so what I want to leave you with, is data types are useful for representing

lots of different kinds of data. Particularly, these interesting tree like

structures, that we can then write recursive functions over, to produce

answers, in terms of the answers for the sub trees.