In this segment I want to go back to talking about the lists and options that we learned earlier and tell you the truth about them which is that they're actually data type bindings and a better way to use lists and options is with case expressions. So, to explain that let me first show something that's not the built in lists and options. Let's see that we already know how to use datatype bindings to define our own recursive structures like the arithmetic expressions we've been dealing with. Now we can realize that that's all length list is itself a recursive little data structure. So like you see here on the slide if I wanted to create my own list of integers that had any number of integers in it that I wanted, I could define a data type my_int_list that was either empty for the list that has no items in it, or maybe built out of the Cons constructor, where I would have an int and then another int list. So then I could do a couple of things. I could create a variable of type my_int_list like I do here. This is the list holding four and then 23 and then 2008, which happens to be my nephew's birthday. And you see that this is just using constructors the way we understand them. The Cons constructor here has to take two arguments: an int and my_int_list. So 2008 and empty. That fits- that should type check. So this here Cons 2008 empty is in my_int_list so that my_int_list can be the second argument to this Cons constructor the 23, and then that can be the second argument to this Cons constructor with the first argument of four. So this overall variable x holds of my_int_list. So it's an example of using this list type that we defined ourselves, and then we could write in a pen function, for example, over these things. So we would just use case expressions. We'll use our append algorithm that we understood for the built in lists, but we'll use it for this data type binding instead. So if x's was made by the empty constructor then just return y's. Otherwise, we can pattern match x's as x and x's prime. You can't do this in many programming languages but it's a nice sort of mathematical name for a variable here x's prime. And then what we will do is we will create the my_int_list that you get from calling the Cons constructor with x, that's the first element here. And the result of the recursive call of append_my_list with x's prime and y's. So that's simple. There's nothing to it. So we don't need the lists and the options that are provided by ML. But they are there, they're convenient, you should use them when they're available. So this is bad style you should use ML's built in lists. I just wanted to show it to you so that the pattern matching I'm about to show you for the built in type definitions seems as mysterious as it should. Okay. So let's do option's first. Just because they're a little easier to read and understand. It turns out I'd previously told you that you made an option either with none or some and then you tested whether you had to none or a some with isSome and you've got the value out of a sum with valOf. Well, now what I'm going to do is I'm going to stop using isSome and valOf as soon as I tell you a tiny little truth which is that option types are made from a data type binding and none and some are just constructors. So yes, you can make things with non and some, but you can also use them in patterns and so you can use them in pattern matching in case expressions. So here's a little function that takes in an int option and if it's given none, it returns zero. If it's given some of i, it returns i plus one. And it uses pattern matching exactly like we've been studying. All you have to know is that N-O-N-E all capital and S-O-M-E all capital are constructors for a data type binding- so they can appear in pattern. NONE carries no data, so you don't have any variables here. SOME carries one thing, so we'll have one variable here which will then be bound to whatever is under the SOME. So why is this better style than using isSome and valOf? For all the reasons that we like case expressions, you can't forget one case or the other, it's pleasant to read, you never make the mistake of applying a valOf two and none, which leads to a runtime error, and so on. So for homework two, and in general when programming in ML, you usually prefer this style to isSome and valOf. We just use those so that we could learn one thing at a time. They work fine, there are enough for options, but I like case expressions more. So that's options. Now let's do the lists that are built into ML. So it turns out that they are just constructors as well. So the same way we're not going to use isSome or valOf anymore, we're not going use hd tl or null either, Instead we're going to use case expressions and our patterns are going to use bracket bracket for the empty list and colon colon for non empty list. Now, these look strange because they don't look like the other constructors. And I actually kind of wish ML had not made this decision of having them look different. It's kind of a historical thing. People find it more pleasant to read. It just makes the patterns look a little bit different even though the exact same thing is going on. So let me show you two examples here: function for summing all the elements in a list and a function for appending two lists together. All right. So this first one I have this list x's and I have this case expression, and my pattern for the empty list just looks like bracket bracket. So just like none, N-O-N-E was a pattern, bracket bracket is a pattern and it matches the empty list. And the sum of all the numbers in an empty list is just zero. That is the proper base case for a recursive function. When you write a pattern for colon colon, you might expect- Here let me just flip over to over here- you might expect that the pattern would look something like colon colon x comma y for the two variables, the head of the list and the tail of the list. It doesn't look like that. Instead, we put the colon colon in the middle. So this is just the pattern. Just like with any other constructor, but we put the first variable on the left and the second variable on the right. And then we can use those variables as always on the right hand side of the pattern. We write x plus some list of x's prime. And this I find to be a very elegant short function that directly captures the idea of how you sum the elements of a list. You see if the list is empty, then returns zero, otherwise let the first element be X and add that to the sum of the rest of the list which is in the variable x's prime. So I was like showing append. Here's the proper way to write append using case expressions. It's the same algorithm we've been using. I already showed this to for the list type that we defined ourselves. Now here it is for the built in lists and this is very pleasant to read as well. Pattern match on x's, if it's empty, the result is y's. Otherwise it's the first element of x's comes on to the result of appending the rest of x's on to y's. Alight. So why do this? As I mentioned for options and it's the same for lists, you won't forget any cases, you'll never make the mistake of applying tail to the empty list that tl function and so on. Since I really want you to learn this the same way that on the first assignment I required you to use isSome vaOf NULL hd and tl. On the second homework I forbid you from doing so. Any time you want to access the thing under a some or any part of a list; anytime you want to see if a list is empty or see if option is non ifSome, you have to use case expressions. You have to use pattern matching because I want you to get used to them. Now there is a fair question here. If they're is so much better, why are null and tl and valOf and isSome predefined for us? I mean, after all then, if case expressions are so good, why would the makers of ML and providing the library even provide these little helper functions? Well, few reasons. First of all, they are useful sometimes as passing as arguments to other functions, and we will see that once we start talking about first class and higher order functions in the next section of the course. The second reason is- I will be honest with you- they are sometimes more convenient than putting a little case expression right where you need it, but for the sort of examples I've shown you here like some lists and append lists, that really is not the case. And the third reason is, they're easy to define. They're not a big deal. You could define them yourself, so the creators of ML thought this way by providing them to everyone will all kind of use consistent names for these little helper functions in the situations where people want to use them. So what we now see is that our language ML is actually getting smaller here. We didn't actually have to add options and list to the language. We have datatype bindings. They're just convenient useful ones that were predefined for us. And we'll see that we couldn't quite define lists and options the way I've shown them here ourselves, and I'll explain why that is in the next segment.
