SBTB 2015: Bill Venners, Scalactic EquaSets: Sets with a Different Idea of Equality
Recording: SBTB 2015: Bill Venners, Scalactic EquaSets: Sets with a Different Idea of Equality
thank you any questions actually I only have 20 minutes so I'm going to zip through this this is about an experiment that is a work in progress and it's there's a branch in the Scala test repo which has scholastic in it called feature equi sets that's where all this stuff examples coming from and it didn't start out this way but sort of ended up being a project that is attempting to explore ways we could simplify the standard collections library in Scala so originally the driving use case was that I came up with this thing called equality force galactic because people wanted to do custom equality in their tests and in their production code and there so I had that that came out in 20 and there was one use case that involved collections that was every now and then you would like to have a set of objects where you want to use a different quality than the one provided by dot equal so for example you might want to have a set of strings where you don't care about case right most of times you the dot equals method is fine I think and that's what you get with skulls standard library sets and just like most of times when you want to compare equality you actually that's Betsey quality that you want but sometimes you want to customize it so the way that I've done that when I needed to is i just made a wrapper class so what this shows is an example of a little wrapper class that will ignore case so I put a string inside something called case-insensitive string or CIS and all it does is hold on to that string and then it has an equals and hashcode that doesn't care about case and so if I put it in a set what you can see is I i put in lowercase hi uppercase high and high with two spaces around it and down here what actually stays in the set is lowercase high and high with two spaces around it because it it sees high with uppercase as the same or equal to high with lowercase right and then this other here's another one which is a whitespace insensitive string I just trim both sides and so when you put the same things in a white space set white space and sensitive set I keep the lower case high in the upper case high but I don't have the high with spaces around it because it trimmed out and sees that as the same as the first one so that's not too difficult that's what people do it's a little bit of boilerplate because you got to wrap it every time but what's nice about it is that if you try an Union two sets that are have compatible notions of equality you get an answer so in the top line i took a the sea i said i made in the previous page and I union with another set of C is case-insensitive strings and I get the union right and then second line I I do the same kind of thing with white space and sensitive sets I can Union them and get an answer that makes sense but if i try to union two different sets with custom ii qualities that are incompatible it doesn't compile right and i think that makes sense so what that's what i wanted to have for this class that i was originally calling equi set which is a set with a custom equality it was that sort of behavior that you could you could Union it on things that were compatible had compatible notions of equality but if you tried to sort of use these set operations unit intersect and diff on something that wasn't the same notion of quality wouldn't compile and there was this in the scholars e issues a few years back now Daniel Spiewak suggested they do that kind of thing with I said I said is I think the I stands for invariant but anyway the that's like a set that has an order and what that the way that set works is is the order which is the has a notion of equality in it because order says less than greater than or equal right that gets passed to every method on set but you don't capture one right so what Daniel was saying is if you you're assuming basically there's only one order for any type like if you have an order a string of you set of strings there's only one order of string so probably forward order but you couldn't have a reverse order one and that's called type class coherence it's something that Haskell has kind of baked into it that for every type there's only one instance of a type class and what Pascal does because sometimes you might want to order strings backwards or order strings for words but ignore case that kind of thing is you make a new type like we wrapped string with CIS that's a different type so they can have an order of that type and it could be different so I always felt that was backwards that that it just makes more sense that there's one string and you have a custom order or a custom equality and that's sort of what people ask for in Scala tests and so that's what I put into school actic so what I wanted to do was kind of what and it was asking for but didn't get in Scala Z and one of the things I had a hard time figuring out was what why people like psych class coherence and it took me actually a lot of asking different people why do you like that they could really explain it to me until I saw this talk as ed permit gave a talk called type classes vs the world where he gives a really nice he explained explains the answer that question is why they like it and but he talks about the trade-off there's there's pluses and minuses but they're genuine pluses that I would point you to this talk if you're curious why that's a good thing but what I'm trying to do is go in the other direction all right so there's pluses and minuses my direction and I hadn't actually had gotten around to trying it yet and i'm martin or dare says play a year ago he came to visit and we were driving up Mount Diablo and I kinda was tell him I want to try this and he said well you know the way I do that and so he sort of planted the seed in the brain of using a path dependent type right so the way it works is that you this orange object here over here is kind of like a you make an instance of that and that captures the equality so that's where you capture it and then that's why I have a little arrow pointing to this equality object up here that's the equality of e whatever e is it could be an equality of string equality of ant equality of fruit whatever you have and then the set is actually like an inner class inside elections so when you create an instance of set you have to create it from the path of to the collections object so if i have this val see I which is a reference to that orange object I can say see I dot set and I'll get a set that has it this like it has an enclosing reference to its enclosing object its outer object and that set is also got a type parameter so at first I didn't have that one because if you create a collections of string then I don't need to say string down here again but I know four or five months ago I realized that actually that could be a subtype of that other one so now there's there's two types there's the Equality type that's in the collections object and there's the element type that's in the actual set or map or C and originally it was just sets because that's have a notion of equality baked into them but then there's also maps have a set of keys so there's sort of a notion of quality there and and later so we actually made a deco map also but later I realized that seek has four methods that have a notion of quality baked into them distinct which says if I have one one one two two two three three three dot distinct will give you a list of one two three just gives you the distinct ones based on that all those ones equal to each other and also there's a union an intersect and a diff method on seek which is multi set Union so it's like a bag it's like sort of like poor man's bag or poor man's multi set in Scala those also have a notion of equality so it ended up not being about sets which one I actually wrote the thing for this talk i called it about sets but it's really about collections and ended up being a sort of a an experiment to see you know what what what collections look like if they did this right okay so i'll just do a demo at the end but basically i import galactic and string normalizations string normalizations has things like lower case that is a way to normalize strings by lower casing them it has trimmed moment I strings by trimming off the white space off the ends and I can convert that to a hashing equality which I need for the collections object in for because in a set you need a hashcode right and the hashcode has to be consistent with the Equality so you need a hashing equality there's also a orderid equality for sorted sets and sort of maps but so I create an instance of collections and I say there this is going to be a collection of what CI points to is a an object that sort of defines a family of collections where they're always going to be strings that's what you can put in there and they will ignore case and so like if you make a list in there if you said called dot distinct it would make that distinct by ignoring case right there always use that equality that's captured the second one is WI that points to a collections object that defines a family of collections that will not care about white space at the ends and when it's determining a quality right so then I can just say see I dot set and here I say hi hi hi where that because this is case insensitive if you look at the what you get you get it doesn't take the capital H I because it sees that is equal to the lowercase H I just unlike the previous example and then I do with wi dot set it takes the lowercase hi uppercase high but doesn't take the high with spaces around because it sees that is equal to the first guy right so that's that's actually what I was originally trying to get to it's just a little less boilerplate but what's nice is that I can Union two sets with the same notion of equality right this is the same example I take a CI set at that old see I said that I made before and I unit with a new CI dots it but with ha right and I get high high haha right i don't get the capital ones when a union to wi sets together i get the lower case in the upper case but don't get the ones with space right and if i try to union two sets of strings from different families that have different notions of equality it doesn't compile you they type here so that's that WI dot said the WI part is the path that's one of those path dependent types and Scala and that's the part that doesn't match up so it's using the path dependent type to get that compiler we need a union differ intersect okay so that's that's part one and one of the things that I did is I didn't just do that I started like thinking about well what else could we do I mean what what would make the standard library simpler and I'm not I don't know how we would get there but so this is just kind of an experiment though it will be working code people could use if they want but I think most of time people need to use a standard library so this is more like an experiment to try ideas out one of the things that I found was back up to my picture here I put a little plus sign there that means sets are covariance so I made sets covariant which is the opposite direction that a lot of people want to go in Scala lists are covariant and sets are invariant and so if I say this is just regular Scala collections if I create a list of oranges you can see that first line makes a list of orange and then I try to constant Apple in front of it then it will infer the least common super type of those two which is fruit so I'm going to back up one page and I'll show you the hierarchy here at the top is fruit and then there's a subclass orange and a subclass apple and then subclass of orange called Valencia right so so when I have a list of orange and I const a list of apple into it it found the least common super type which is free right so I get list of fruit which is kind of nice right but then the problem is the last one when I can't 88 in front of orange lace I I get a list with 88 and two oranges in it and that's a list of any which is probably a bug so usually when we infer any it's probably a bug so this doesn't catch the bug right but it does allow us to the second line i think is something we probably do what that's probably okay so scala sets are invariant and the reason they were invariant but what I had to do to make them covariant is pull out that they extend function one and that's mixing two different notions of set one notion of said is extensional which means I list all the elements the other notion is intentional which is I give a function that says to false is this a member and sort of combined them and when you do that you the way the types lineup you have to make it invariant so by pulling that out and I have a separate class called membership which sort of is the intentional set the function one and then the regular set it can now be covariant because then it's consistent so when we teach Scala people understand that you know covariance of lists that if you ask for a list of fruit and I give you a list of apple it should work because the list of apple is a list of fruit conceptually and they don't understand why sets are invariant that I always ask about that so I thought it'd be better simpler if it was consistent so this is wrecked I went but here's Scala sets if you make a set of orange if i try to content apple I can't because it because it's invariant you have to it has to be a set of apple or a set of fruit already so what I'm going to have to do is actually a map at this is how you do it I map the set of the set of orange to set of fruit right here and all I have to do is take each element and say oh this is a fruit which it is right so all I'm doing really is copying the app the oranges over here to over here in memory its exact same oranges but now it's a set of fruit and then i can i can add apple into it right and that's a bit of code I mean this code that you have to do but it's also if you have a million oranges like you're doing big data and you need it to be you're gonna have to actually copy a million over to another rimbor like ocean just to get to be fruit it's kind of it seems wrong so so anyway what it turned out is that the methods like plus that has or contains it has this this type bound that says it needs to be a the element type or some super type in these collections it also has an upper bound which is the equality because if i have a collections of fruit i only know how to do equality for free so you can only have fruits in that family of collection collections of fruit in that family so that that actually has sort of a bound to the this problem of inference so i'll show you an example if i create a collections of fruit now i have fr is this refers to this orange object that is defines a family of fruit collections and if I create a set of Valencia in there so it's under that path so it's it's a fruit dot set or FR debt set of Valencia if i put in orange you get a set of orange so it goes up you know goes up the hierarchy in ferns the supertype if i put in an apple it goes up the fruit right but what's nice is if i put in 88 it doesn't compile so so that goes up to the place you like but doesn't go to where you don't like alright so it's an upper bound for that kind of problem so what I had done last year or like the last couple conferences ago I showed you can use static analysis to find these any inferences and like contains checks these things that that have this problem of inferring any and actually masking bugs you can find it with static analysis but this is you know partly in a type system you get it within that the family that you have but you don't get it above that so that's that's just all in the type system okay so that was nice so that's just it's this guy right here that's what the type bound looks like you as the new type that's inferred when I plus something into a set or call dot contains right t is the element type so it has to be at the element type or a supertype so if you're Orange it has to be either an orange or a super type of orange which is fruit or super type of oranges Annie right so that actually any works for that but it has to be a subtype of equality type so since we have an equality of fruit then that's the top that's as high as it can go ok so and then there's something called cult default which is gives you I just say collections that default I get a collections of any and so if I import that it really feels like you're using Scala standard library because that's what that's what this does is it uses default equality force galactic which is always dot equals except for arrays it calls d so the only difference between this and standard elections well as far as what the how the quality works is arrays you get structural quality raised if you put two arrays in to ask Allah set that have one two three and them they'll actually stay too because it thinks they're different because they're different instances if you put in a galactic set default set it will just have one because they have the same structure same elements okay and it will and for any right because now the top is any so it will actually go all with top just like the standard library so so basically that is my my talk there are a couple other things that it didn't have time in 20 minutes to talk about but any questions we talked about questions yes Eric yes and it and that's that's one of things I didn't have time to talk about but I can demo it I'll show you let me grab these guys I guess can you see that yep so I have that WI set let's map it to something I don't know wi sit dot map underscore dot plus space Eric I got any spell I never know how you spell it hi Eric hi Eric yes so just say darling and what the key here is that business in a set its it already is lazy right so the reason I did this wasn't one thing is you can make there's some performance in sometimes you can make things perform better by analyzing these these lazily chain things but the real reason the main reason I did that was to because I think can build from is nice and makes things nice but it's just too much in everybody's face and if you make map lazy it doesn't need can build from anymore they're the only place you need can built ramin don't even eat it on sets either is here when I force it I'll have to force it into a set of ant which I don't have let me do the other one if I force this into a said event let's say Val SS equals and SS that force back into the best put it in the w I said well put in a different one okay let's put it into is not see i said i need to put it into WI I have to put into the family and get rid of that guy so basically when you force it you have to thats when you tell it what family you're going to and that's when it does the weird thing but that you don't need a functor for that so so you can get a functor for this set just fine and what I did differently to it in the standard library is if you look at this set this view it actually forces it actually the times you want to look at the two string is rebel test failure log message debug message and you always want to see what's in it so the standard libraries views don't won't show you what's in it because why their views you know but that's that's I think that makes it harder to use because when I show map when you teach people map if they need to see what happens so that's that's another difference there's a bunch of stuff in there like that that I didn't have time to talk about but I think if you look at the the Scala doc it's just really clean there's no can build from but it's still like if you have map it could still do the thing where if you map it to another tuple to you you get a new map but if your map it to an ant you get a iterable whatever you can still do that same trick you by yes yeah because that returns a hashing quality of string yeah yep anybody else yes um well I mean people aren't used to it so when I saw path-dependent types I didn't know what to do with them and then over the years we've found things and I think this is a pretty good use case for them and what what I what I think is I mean I can show you if I just import collections default I'm going to hide these other ones underscore it's just like using Scala code it's very I mean this is collected collections you can see the type it types kind of hairy right you have the path in it collections is actually an object the non sorry default collections that default is an object that's like a vowel and that's your path and then got immutable that inhabited so that's another thing I put in is that for immutable collections you can it's in the type that it's not empty if it is if it's provable I think that's useful and simple so that's where that inhabit it comes from if i subtract something out of here like to then I can't prove any more that it's not empty so that part goes away but if I add something that I I know it's not empty so that comes back that kind of thing so anybody else going once going twice gone all right thank you