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.