[MUSIC] In this segment, I'm going to show you a third implementation of rational numbers that will be equivalent to our other two, as long as we keep the type abstract. And what I'm going to do here, is actually change the implementation of the type rational, in order to emphasize that when the type is abstract, an equivalent structure can go ahead and change how the type is implemented. So, given a signature that has an abstract type, different structures can have that signature while implementing the type in different ways. Those structures might or might, might not be equivalent. I'll show you an example where they are. So I'm about to show you a third implementation, rational 3 And in rational 3, the type rational is going to be implemented as a type synonym with int * int. So let's go over and see that. Here is my structure. You'll see I have a type synonym here, so in the rest of this module, rational and int * int are the same type. The outside world, however, doesn't have to know that. So before I show you these functions, how about I just show you, remind you, what the three signatures look like? Now signature RATIONAL_A requires the module to implement rational as this data type. Since our module does not, rational 3 does not have this signature. If we try to give it this signature, the type checker will reject it. But it does have this second signature, RATIONAL_B. As we'll see, we already saw it defines a type rational. It defines it to equal int * int. That's a fine way to implement a type rational. But, given that definition, it's going to have to have these three functions, where rational is int * int. The outside world, as usual, will not know that rational is int * int, and then for RATIONAL_C it can have this signature, provided it has everything it had before, as well as a function of type int arrow rational. And I'll show you that at the end. So, let's see how struct rational 3 is implemented and the fact that it can have type, the signature RATIONAL_B. So rationals are now just pairs of ints, in all cases. So here's make_frac. If the denominator is 0, raise an exception. If y less than 0, then produce (-x,-y). Just like before, but now it's just a pair of ints, there's no frac constructor involved. Otherwise return (x,y). Notice we're not treating whole numbers any differently. So if this denominator is 1, then we'll just, return (x,y). Okay? To add 2 fractions, well, add needs to take 2 rationals. And each rational is an int * int, so this pattern will do well. And, we're not going to reduce things. That's an orthogonal choice, but like Rational2, we're just going to wait until toString to reduce things. So we'll just return a*d + c*b in the first position, and b*d in the second position. And then finally, toString is a little more complicated, because we still want to return everything in reduced form and treat whole numbers specially here. So here's what you need to do, if x is 0, you have a numerator of 0, you better return the string 0. Otherwise We have some more work to do here with GCD and reduce. so here's a let fun gcd equal this in, let's convert to a string the numerator concatenated with if the denominator is one then don't do anything. Else, a slash, and then to string of the denominator. So, I didn't empahasize this. Up here, I've computed the num and the denominator, by dividing both by the gcd, of the absolute value of x and y. So, a bunch of arithmetic, but the point is, to not print the denominator, if the, if the numerator is 0, or if the denominator is 1. And so overall, if we go back up here to the signature RATIONAL_B, we've provided everything at the right type, make_frac returned an int * int, add took two int * ints and returned an int * int. And toString took and int * int and returned a string. And then the outside world does not know that rational is int star int. Now, if we want to implement Rational3, we also need a function, of type int arrow rational. This was this cute thing where, for our other structures, the data type binding was providing this function, and then we are exposing just that part of the data type binding to the outside world. Now, in our new structure we don't have a data type binding, we don't have such a function being defined by it, but we can still implement this signature provided we have this function. And so, again, it's a little cute, but down here at the bottom, I just defined a function whole, you're allowed to start functions with a capital letter if you want to, that just takes in an i and returns this rational, this int * int of (i,1), and it works great. So, that is our third implementation. I want to emphasize, that when we do signature matching of this structure, against either RATIONAL_B or RATIONAL_C, a couple of interesting things are going on. So let me emphasize those for you. the first is make_frac internally has type int * int arrow int * int. And so that does match a signature where we're exploding, exporting it as int * int arrow rational, because rational is int * int. And the client will never be able to tell that we're actually returning something of the same type we're taking in, because the client doesn't know those are the same types. Now what's interesting, is we could If we went back here to RATIONAL_B, we could say that make_frac, instead of being int*int arrow rational, it's actually rational arrow rational. Now this is a very bad signature. The structure has this signature. The type checker will accept it. But, the structure will be useless. Because if all the outside world knows is that it can use these bindings, it's never going to be able to call make_frac, add or toString, because it can never get its first rational to get started. There's no way it can call any of these functions. So there are programs out there that type check and are not useful. Okay? So we really want to expose here that make_frac does take 2 ints as arguments. So that's the first interesting thing. The second interesting thing is this function, whole. So let me go back and show that to you here at the bottom. Based on what we know from type inference, this is going to have type alpha arrow alpha * int. And that is indeed what the type checker will give this function internally, when it goes to type check it. But in our signature in RATIONAL_C, we said this had to have type int arrow rational. And so somehow, the type checker, which is fairly sophisticated and fairly smart, has to get from this first type to this second type legally, and it turns out it can, because the rules of signature matching let you take a polymorphic function and instantiate it to a non-polymorphic function. So the first thing the type checker has to figure out to do, for signature matching, is to realize that alpha can be int, and therefore, this could also have typed the less flexible type, int arrow int * int. We have to replace all the alphas consistently, and now we see, that indeed, since rational inside the module is int * int, we can, as we usually do, match this type against this type in the signature, and its pretty neat that ML does that for us. Notice that this does not have something like the type, alpha arrow int * int, or you know, int arrow alpha * int. When you take a generic type, a polymorphic type and make it less general, you have to replace all the alphas with another type. The, this function hold does not have these bottom two types, that doesn't make any sense. It is not the case, that if you called whole with a string, you would get back an int * int, so these types are just wrong and I will delete them. It is interesting to me that inside this module, we actually could call whole with a string for i, but outside the module, because of what the signature says, we can only call it with an int, and therefore it will return irrational. Okay? So, that is the more sophisticated and interesting details of this third structure. But the high level point is that under RATIONAL_B or RATIONAL_C, this structure is equivalent to our other two structures, even though it implements the type rational and in, and in an entirely different way.
