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.
