Okay. In this section, I want to talk about how you can define your own data types that are polymorphic. So the reason why I'm doing this is I've previously claimed that the options and lists in ML aren't particularly special. That they are themselves just data type bindings. And the only thing that's different that, is that lists have slightly special syntax where we have the colon, colon as s constructor in the middle, and bracket, bracket for the empty list. But that's not exactly true, compared to the data type bindings I've shown you so far. Because lists and options are things that take type parameters. So, list is not a type. It's int list that is a type or string list, or even int list, list which is list's who's elements are lists who's elements are ints. So, list and option are not types, they're type constructors, they're something that take type parameters to produce types. And we've also seen functions that may or may not be polymorphic. So, a function like sum list has to take a list of integers and add them all up to produce an int. But a function, like my favorite, append is something that works for any type alpha, and it takes a type alpha list, and another type alpha list, and returns an alpha list. And I just say alpha instead of quote A because that's the traditional way to pronounce that. So, it would be good language to design to not have built-in things like lists and options that can be polymorphic in this way, and then have data-type bindings that you can define that don't have this facility. So, it turns out that ML did the right thing, it lets you define your own. And this segment is going to show you how to do that. Now, this is optional in the sense of I wanted to show this to you for completeness, but the homework is not going to require you to do this, and I'm just doing this to finish the story of how lists and options are not particularly special. Okay. So, here's the syntax I haven't shown you yet. And that is that you can have one or more type parameters between the word datatype and the new type level binding your introducing. So this first line here on the slide is exactly how options are defined in ML before your program starts running. And it just says that option is not a type, it's something that given one type, alpha or quote A, produces a type. So int option is a type, string option is a type, and so on. And then, once we have that quote A, then we can use it in the types of data that our constructors carry. So, in particular, we can have some of alpha, some carries what ever type this particular kind of option carries as its parameter. Similarly, larly, if we wanted to define our own linked list, ignoring the special syntax in ML, we have one type parameter, alpha, and the cons case carries two pieces of data, an alpha and then another list. But you can't just write My List here, that's never a type. We say that the rest has to be another alpha My List, alright? So, you can even do things with multiple type parameters, so this last example here shows that. It defines a particular kind of tree where I have two constructors, internal nodes and leaves. And the leaves always carry something of type quote B or beta, the second Greek letter. And the internal nodes always carry something of type alpha and then two other alpha beta trees. So, this is going to be a binary tree where all of the internal nodes can carry data of one type and all the leaves can carry data of a possibly different type. Those two type parameters, alpha and beta, can be the same or they can be different. Alright, so that's how you do it. I have a bunch of code associated here that you can mostly look at on your own. So, I started by showing you some list in append over ML's built in lists. So some list here is going to have type int list arrow int. And the type checker will be able to figure that out because it sees that right here, you're taking an element of the list x, and you're adding it to something else. And so the elements must have type int. The result type must have type int both because we have an addition here and because we have a zero here in this other branch, and zero has type int. Append, on the other hand, the type checker can see that we don't need are list arguments, x's and y's, to have any particular type. They have to have the same type because if you take an element of one and cons it on to something that has to have the same type, because we return something that is wise, these two lists better have the same type because you can't mix and match elements of different types. And so, the type ends up being alpha list, arrow alpha list, arrow alpha list, which says that callers can use append with lists of any type. But the two types, the two arguments, x's and y's, have to be lists with the same element type. Alright. Then, I have the data type bindings I just showed you here on this slide. And then, down here using our own polymorphic data type, this alpha beta tree I showed you where the leaves have one type and the internal nodes have data of possibly a different type, I wrote three different functions. This first one, sum tree runs over the entire tree adding up everything at every position. So, if you have a leaf, we pattern match on that here and we just return the data there, this i. If we have an internal node we add i to the result of recursively summing the left child and recursively summing the right child, these left and right fields of the data. And so, everything has to have type int. And so, the type checker will indeed figure out, if you run this code, that the argument has to be an int comma int tree. That only trees where both alpha and beta are int can be legal to pass through the sum tree function and get a reasonable answer. This is a much more interesting function from the type perspective, although it's probably less useful. What it does is it also takes a tree, but it only adds up all of the integers at the leaves. So, if you look in the node case here, what the right hand side does is it just calls some leaves on left and some leaves of right. It doesn't actually use the data at that node. And so indeed, the type checker will notice that the legal types of trees you can pass the sum leaves are anything where the beta is int and the alpha can be anything. So, some leaves can be polymorphic. It works for any kind of tree where beta is int, and then it returns an int. And finally, if you did it something even more general like just count how many leaves a tree has. So now, we're not using any of the internal data. We're not using this i I and we're not using this i. We just count by in the base case returning one, and in the internal node case summing the number of leaves on the left and the number of leaves on the right. Now, any kind of tree is a legal argument, and indeed the type of num leaves will be alpha beta tree arrow int. Okay. So that's fairly fancy type system. As I mentioned, we're not going to get into our own polymorphic data types in homework two. But, it's interesting to notice that the way we used constructors and case expressions was exactly as usual. Nothing about the code we wrote was any different, nothing about the evaluation rules were any different. The only differences in the type checking were now the type checker has a much more interesting job of making sure that types are used consistently. So, even though a list or a tree may be polymorphic, you still have to, you can't mix element types in a particular data structure. And then, how polymorphic your functions are, how many of those quote A's as and quote B's appear in the type depend on how the data is used. And that's why we see things like summing the elements of a list requiring a list of ints, but something like append working for lists of any type.
