The purpose of this segment is to just give you an example of me writing a function like you might do on your homework. What I want to do is continue using this important data type binding we've introduced for arithmetic expressions where constructors are for constants, negations, additions and multiplications. And the function I want to write is max constant. It's going to have type exp arrow int and what it's supposed to do is find the largest constant contained anywhere in the expression. So on your homework, I would typically just ask a question like that - write max constant - and it's up to you to figure out what concepts from the course are relevant, how to use them, the difference between a solution that seems to work and is correct versus an elegant one that uses the concerts in the best possible way. So this example is going to show a number of concepts we've studied, nothing new; so in that sense it's review or it's optional. The entire rest of the segment will just be spent over in the Emax buffer as I try to write this with you. So I've got things started here in a short example file, I have the data type binding that we need. And I went ahead and wrote a test case here where I have a test expression and then I call max constant on it. Let's just emphasize that it's often good software engineering practice to write tests even before you've written your functions in order to understand what answer you expect and how the function should behave. And then I obviously still need to write the body of max constant. So let's just get started. The first thing that seems obvious is that we're going to need some sort of recursive function that uses a case expression. So I'm going to have the case on this and I'm going to have to think that if I have a constant, then the maximum constant in it is just I. That's a nice base case for my recursion. Otherwise, if I have a negate of some smaller expression, then I should just compute recursively the max constant in e2. So far, so good. Two cases down, two to go. If I have an add, I'm going to bind to two smaller variables, e1 and e2. And now, I have to figure out the max of each of them and take the bigger one. So what I might do is I might say if max constant of e1 is greater than max constant of e2, then return max constant of e1. This should probably be setting off some alarm bells, but that's okay, it's a fine first attempt. And if that looks okay, that's fine. And if anything seems sort of fishy about the style of that part, notice that now what I'm going to do is say that in multiply, it's really the exact same thing I need. So how about I just copy and paste the code down there? All right. So copy and paste is often a bad idea. We'll get back to that in just a second. But let's see if we have a working solution. So just go over here, try - use that XML - and sure enough, my test case passed. I have val 19 equals 19. And in fact, I'm not kidding you, this is actually a correct solution. I believe it will technically produce the correct answer for any X that you would pass to it unless I've made a mistake I don't realize here. But it fell into this trap of recomputing recursive results, which we know could lead to a very inefficient solution. We won't see that if we test it only with small expressions; but if you tested it with a very deep expression. With a somewhat large expression, you can see this problem come up pretty quickly. So we know how to fix that and that's with let binding. So what if we said let val m1 equals max constant of e1 and val m2 equal max constant of e2. And then just said if m1 is greater than m2 then m1 else m2. And that would be fine and never calls anything recursively more than once. And now, I could just paste that down for multiply because I still want to do the same thing there and I want to fix the same problem. So let's try that out. All right. Let's restart here and it works again. So this seems better. All right. And that's a perfectly good second solution. But now this cut and paste is really bothering me and it's not particularly good style to duplicate code like that. And we know how to avoid duplicating code; we could have a little helper function. We could have a little function up here that, say, took two expressions and returned the maximum constant in either of them. And it turns out e1 and e2. Now, it makes perfect sense to go ahead and cut this and paste it up here because it's exactly what we want for the body of this function. All right. And then we can use that here in add; we can say max_of_two(e1,e2). And now, yes, this is a little bit of cut and paste; but just to call a helper function, that is just fine. And we can delete this. And now we need an end to end the let that created our local function binding. And that is a solution I'm pretty proud of. All right. So let's go back over here and try that one out. It's still working, so let's hope it's still all correct. And now we're probably pretty good. Let me show you a couple more versions, though that I like. It turns out that this if m1 greater than m2 than m1 else m2 - it turns out if you knew a little bit more about the standard library in SML, there's a built-in function that computes the max of two integers and whenever there is a built-in function, it's usually easier to read. A reader of your code who knew there is an int dot max would probably be much happier to just see that than try to read your if then else and figure out what's going on. So that would be a perfectly good solution. And now, once we have that, believe it or not I'm going to start undoing some of the things I did before because now, these local variable bindings - there's nothing wrong with them if you find this easier to read, but I'm no longer risking with that if then else of computing the maximum of anything twice. I could go ahead and just write in here max constant of e1 and max constant of e2 and now I don't need this let and I don't need this in and I better get rid of the end. And that is because when you call a function like int dot max - int dot max is just a function - we evaluate the arguments to values before we call the function. So we're going to call max constant of e1 once, we're going to call max constant of e2 once, then we're going to pass those resulting numbers to int max, which is going to be implemented with an if then else and do the right thing. So this will be efficient; there's no concern about a very slow function. And let's make sure that this one is still working. I don't like to do too much work without checking my work. Okay, we're still good. And now, this local helper function that we wrote is so short that you could argue you don't need the style of a local helper function just to save this actually pretty small computation here. So now let's undo that local helper function as well. Take this. Paste it in here. And paste it in here. It's a little long for using twice, but not too long. It actually looks a little worse with the font blown up here so you can read it easily. It really does fit on one line. How about I move things over just a little bit here so you can see that all together? You would have more columns on your screen than I would. All right. And now we can get rid of this let in and this case and make sure it all still works. And it does. And this is actually pretty pleasant to read. To compute the max constant of an e, let's pattern match on e. If it's a constant, then just return it. If it's a negation, recursively compute the constant of e2. If it's an add, compute the max of the maximum constant of e1, the maximum constant in e2. And the same for multiply.
