[MUSIC] In this optional segment I'm going to show you one more closure idiom, that's significantly more advanced, combines a number of the fancier features we've seen, but no new language constructs and we're going to do something pretty neat. So, what we're going to do is implement an abstract data type that's going to feel a lot like an object in an object oriented record. What we're going to do is implement, actually, a set of integers, just to keep the example simple. But what we're going to do is have a record of functions. So, a set is going to be represented by that record. The only thing in the fields of the records are functions. So the only thing clients of our abstraction are going to be able to do is caller functions. But because those functions are closures, they're going to have access to private data. And in fact, we're going to set this whole thing up so that all the functions in the record have access to the same private data. And that's how they're going to be able to work together to implement an abstraction with multiple operations, like inserting into a set and finding out if something is in a set. Now, we could have made that private data mutable or immutable. It actually would have been a little simpler if we had made it mutable. But I want to encourage more function-able programming style. So were not going to do it in a mutable way, we'll do it immutable. And, in fact, so if you insert anything into a set of integers, that doesn't change the set you did insert on, it returns a new set that has another element in it, if that element was not already in the set. So the goal here is to make it feel a bit like object oriented programming. This will be the first time in the course that I give you a hint that OOP and functional programming actually have deep similarities, but even if you're not familiar with OOP, it's just a closure example. I admit this is advanced and clever, but it's a good way to put together a lot of stuff we've seen. Lexical scope, data types, record and closures, and even those the implementation of the abstraction is bit sophisticated, using it from the client side, once I show you how to do it, isn't going to be so tough. So, we'll do the rest of the segment in the code where I'll just show you what we've got. So I'm going to start with a type definition. Now, I'm going to put this back to how it is in just a second. But this is the type I would like to implement. I would like to say that a set, just to find a nice type synonym here, is this record type. So remember records are just things with fields. You write colon, and you write the type of the field. And there's no reason why fields can't hold functions, or things of function type. So the insert field would hold a closure of type int arrow set it may enter to give you back a new possibly different set that contains that int. Member of type int arrow bool for is the int unit set and how about size which takes no argument and tells you it how many element are in the set. Now, unfortunately this won't quite work because in ML type synonyms can't be recursive. So this use of set is not going to work. So that's why I'm doing this ML-specific thing of let's make it a datatype binding. Of course, datatypes need constructors and of, so this is actually a reasonable use of a A data type binding that only has one constructor. I'm only using data type for the purpose of being able to mention set in the definition of set. The same way we mentioned list in the definition of list. Okay. So now I'm going to have this type, this s constructor is going to be a bit of a pain. But we'll be able to use pattern matching to get rid of it when we need to, and so on. So, the next easiest thing to show you is to keep this type in mind. In fact, why don't I make a copy of it so we'll be able to see it. I need to put this in a comment, and bring it down with me to show you a client. Okay. So I'm going to copy this down here is an example client. Just little function use sets of type I think unit arrow int. So we don't know how this set is implemented but we do know its type. We know it has, it's a record with fields, insert member and size, each of which are functions. So, lets just start with the empty set. Oh, I should have emphasized that, the only public value that's going to be available to us, is empty set of type set. And I'll show you how we implement that later. and so we are going to have to build our set starting from the empty set. So, I have this empty set value, and I'm going to be able to say, let val essentially s1=empty_set. I'm putting a constructor here to pattern match away the constructor Don't worry about that. I don't want to focus on that, but you do need this because otherwise this s1 would not be a record of functions. It would be s and then we'd have to pattern match later. So s1 is now this record of functions. So what I can do is take s1, read out the insert field, that will get me back an int arrow set function. So I could call it with 34 and I get back a set. I can then strip of the s constrictor of that and have a new record of 3 functions. So I really like this because you might be in other languages more used to writing something like insert 34 but you know, your way my way, it's just rearranging the same ideas. You can't really argue one is more complicated than the other. So I could then take that s2, insert again. the same number, 34. So, it would not actually add it, because that's not how sets work. So, sets don't have duplicates, so that would produce s3. And then s3, I could insert again and have 19. And so, this would logically be the set holding 19 and 34. but rec, represented in s4, is just a record holding 3 functions. So then, down here, I could use the member function. I could take s4 and I say, if 42 is a member of that set, then 99. it's not else if member s4 19. 19 is a nautset. I could say 17 plus the size of s3, and I believe therefore, this whole thing will valuate to 19. It's a silly client, but it shows that once I'm given this abstraction, using it, as a set, is pretty much like we would want to program with sets. We just use the functions that are provided to us. Okay. so that was actually easy part. That's what clients would do. We always want the client to be easier than the library, because we only what to implement the library once. So now let me show you that fanciness. All we have to do is implement empty set. But we've to do that in a way that's actually correct, that when we call insert, we will get back something that you know, will then act as an appropriate set. That is not empty. So there's a lot of ways to do this. I think this is a short and elegant way, though I don't claim it's particularly easy to understand. So I'm defining a vowel empty set. Alright, what I'm going to do is I've this little helper function that I'm going to use. And what this helper function does is it takes a list of elements It assumes that list does not have duplicates, but it's a local helper function so that's a reasonable assumption. And then, what we just return for empty set is make_set of the empty list. All right? So now, all we have to do is understand make_set And we're done. So let's understand mixed set. It has this little helper function that we'll explain in a minute. But fundamentally what it returns is this record wrapped in the s-constructor. So all we have to do is return a record, where insert does the right thing for a set contains the numbers and xs, member does the right thing, and size does the right thing. So, let's work bottom up, which is from easier to more difficult. So, remember, we know that xs has no duplicates in it. That's an invariant we're going to make, maintain here and so all we have to do is just take the length of that list. So size is a record field that contains this anonymous function of type unit arrow int which is exactly what we need for the size field and it does the right thing. Notice we're using private data here. We're returning a record that is using xs which is in scope right here, alright? For member, well we just need to go down this list and see if there's anything in the list that equals the number we're looking for. So I actually, for reasons we'll see in a minute, I have put this in a helper function here contains. So contains take a, takes a number i and returns true if i is in xs. So again I can use private data here I can use xs, I can use a nice library function List.exists, which works just like the exists function I wrote for you a few segments ago. It's curried, I pass in this predicate function that says for each element in the list j, does i equal j, and then, this is a perfectly good function of type int arrow bool. So, that's exactly the function that I want to put in the member field of the record I am returning. Okay, now all we have to do is insert. The tricky thing about insert, is that it is going to use make set, recursively. And that does make sense. Since, when you insert an element into a set, you make a new set. Alright? So insert has the type, have type int arrow set. So here's an anonymous function that does what we need. Takes in that integer i. If i is contained in xs. So there's my second use of my helper function contains, which is why I made a helper function. For it. Well, if I already have it, then I want to return the same set I already have, but there's no harm in making a new set, and the easiest way here, is just call make set with the same list xs. Alright, and that will work fine. Otherwise, make_set with i;;xs. And that's it. You can look at this, you can stare at this, and see that the three functions I put in here Do exactly the right thing in the case that xs are the elements we want in our set. The trickiness is that make_set is recursive and that we provide the empty_set where we make_set of the empty list and the recursion of make_set takes care of the rest. So I have this all compiled over here, you'll see that we defined our type definition for sets. empty_set is just something of type set. It is a record of 3 functions wrapped with this s constructor, and then our example client is something that just read out the fields of the record and used them in various ways, and if I call it, I actually get back 18. Earlier, I said it was 19. I must have been misreading the code. I'm sure the compiler is right, so let's flip back here to the file. And look down here at the client and sure enough 17 plus the size of s3, I think I thought we were taking the side of S4 you see here that s3 is this one that only has one element in it, 34, because we don't put duplicate in there and so 17 + 1 is 18. Alright? So that's our implementation, our client, and our testing code. And we really have implemented an abstraction using nothing except data types, recursion, closures, and records.
