scala.bythebay.io: Rob Norris, Pure Functional Database Programming with Fixpoint Types
Recording: scala.bythebay.io: Rob Norris, Pure Functional Database Programming with Fixpoint Types
yeah one of the problems with speaking like on the third day of a conference especially one like of this quality is that I'm like gets so much inspiration and talked to so many people that I have all these ideas about making my talk better so I keep changing it so hopefully I'll be able to get through it without without stumbling we'll see what happens also very sleepy so yeah my name is Rob I work for the Gemini 8 meter observatory so we have two telescopes that are very big ones in Hawaii and was in Chile I write software that helps scientists use them to do science so it's it's fun work I also work on some open source projects including some of them that we're going to talk about today you can't hear me all right so um how many of you if you don't mind saying have used either scholars at or cats Oh quite a few oh that's great um where any of you in John de gAHS talk about Co free or Greg's talk about much rush good ok good so some of this stuff is gonna seem familiar probably so that'll make it a little bit easier so today I kind of want to just talk about some odds and ends that I think are interesting and we'll see if you find them interesting too so our goals for the talk the big one is to start kind of developing an intuition for fixed point types this stuff is pretty well known in the Haskell community but not so much among scholar programmers and these are really interesting general-purpose data types that I think we should know more about because they're they're really useful oh we'll learn a little bit about Dubey which is a database library that I work on it's a pure functional interface for writing JDBC programs gain some confidence pushing on code so this is something that I that I mention a lot when I'm giving talks and people don't know what I'm talking about so I'm gonna try and illustrate what I mean by pushing code around and and importantly don't don't panic ok so so everyone who's a functional programmer can remember when they were having trouble learning recursion it's it's hard it's a mind-blowing thing learning recruits functions inductive datatypes and what we're going to be talking about today is doing these sorts of things at the type level and it is hard and if you're confused and struggling a little bit that's okay and I promise I will try to try to reel you back in and and and and make sure it's understandable I've been I have been told to hold this in my hand all right okay so let's get started let let's look at a recursive data type okay so here is a simple recursive data type and the idea is these are University professors and their PhD students who also became professors so we have a case class we have a name and we have the year they got their PhD just so we'll have some some data and then the students are a list of professors so it's a recursive data type and if you look down at the bottom there is an example there's david hilbert with three of his students and and Wael and MacLean have a couple students down there as well so they kind of invented sort of the the example that I want to work through is taking a structure like this and trying to map it to a relational database in a natural way and then read it back and we'll we'll we'll use that example to develop some ideas so if you are going to store this kind of thing in a relational database this is probably what you would do you would have a I have to take out my glasses because I I can see my screen or you the natural sequel representation is going to be a table you can have some generated identifier you will have the name and the year as columns and then you'll have this parent column that's a pointer that goes the other way the children reference their parents so the relationship that's natural in the database is sort of inverted from the natural relationship that you have in your Scala data type so we'll have to figure out how to deal with that distinction but the first thing I want to do is talk about what we're going to do with that database ID that's we got to figure out how to represent that on the skull it's aside so here's one way we might do it I just add an int field can anybody see any issues with doing it that way anyone yeah repetition well the I guess the problem that I see with it is when you just construct one of these things and it hasn't been in the database you don't have an ID right so you need some out-of-band value there so a negative one or something but that we use types for that kind of thing in Scala otherwise you're going to be constantly checking to see if it's a real idea or not so so we might do this and use an option event is that any better it's a little better right but but I I think this representation is still pretty irritating because you really have three cases right either you've just constructed it and you know that it's new and it has no ID or you just pulled it from the database and you know that it does have an ID and you still have to check the case where it might be missing which is irritating and then you might be doing some sort of computation over the structure displaying it for the user or something where you don't care about the IDS and you have this cruft from the database there's sort of infected your datatype so I think this isn't a very good encoding either so one way we might do it is try and externalize the ID and have something like this so we have a type alias for ID prof is a pair of the ID and the prof okay can anyone see a problem with this representation okay so well what about the students the students don't have IDs so we have to do this right so the end is back into our into our case class again which defeats the purpose so so here's where we're gonna kind of make a leap and I'll show you the this is the one trick basically the one trick in this presentation so we don't know what type to put there so I'm just going to introduce a type parameter and you may start to feel uncomfortable from this point on but I'll try to I'll try to try to pull you back okay all right so now our data structure is no longer recursive okay a prof and I've renamed it prof F just to distinguish it from our original prof data type and the students the children are a list of anything at all okay so now what we can try to do is say okay well our profit i p-- is a profit whose children are also profits okay and the ID prof is a pair of an int and a prof f whose children are pairs of int and prof f and what is the problem with that prof F needs a type argument right so if you actually want to write this out correctly you end up with that okay so it doesn't work right because the types are infinite so we can try something else we can do that so we can say alright prof is a prof F of prof. right so we're referring back to the type alias so we're going to try and tie the knot that way and the same thing with ID profits a pair of int and a profit F of ID prof which is itself a pair of knit and a profit effect and does that work that does not work because price type aliases cannot be self referential in Scala but we can do it with a class classes or so it can be self referential so what about that so we've just turned it into a case class in both cases and that compiles and that works okay so now we have a single representative prof F and two different representations of it we have sort of the flat tree with no database artifact and then we have the one with the IDS associated with it and that works that compiles and we could claim victory and just be done but this is functional programming it's Scala and we like to generalize things so let's push on this a little bit and see what happens so we'll notice that improv and ID prof. there's nothing in the implementation that is specific to prof F it could just be any unary type constructor so we can factor that out right and on the right-hand side the recursive case the profs need to take an F is a type argument okay so we've just factored out prof F and then also an ID prof there's nothing specific to ID being an int so we can just make that any type a and then again the a has to repeat up here on the self referential portion over on the right okay so so this is interesting we have something that's absolutely generic there's nothing specific to our domain here anymore both of these things are potentially very useful because they have solved a concrete problem for us so that that always makes me very skeptical anything I invent that is sufficiently polymorphic and possibly useful probably is already a thing right and it's probably a thing in cats or scholars ed or both or or some FP library so I am not clever enough to invent something that is as useful as what we just did and it turns out that both of these types are in fact very well known okay the first one is called fix okay that gives us a fixed point for any functor f it lets us write that infinite type in a finite way okay the second one is called Co free okay it does the same thing but at each node in this structure you have an arbitrary annotation okay and if you saw John's talk yesterday or the day before whenever it was you have some idea of what a cool cool type that is and we'll explore it a little bit well I'm here I'll mention one other data type and you can guess what it is so Co free is an A and an F and the seller type is an A or an F does anyone know what this type is called it's very good that's free okay so so Co free gives us structure with labels at each node okay and free gives you an equivalent structure with labels with with values down at the leaves and that's that's kind of it's okay free is commonly called the free monad because if F is a function free is a monad with Co free if F is a function n Co free is a comonad okay so it's worth pointing out that the implementations of free and Co free in cats and scholars that are much more complicated than this right if you've ever looked at them there are two reasons for that the first one is you want to be able to define these things so that they're arbitrarily large or maybe even infinite so they have to be lazy you can't evaluate them strictly like this does and you also need a way to traverse these very large things without blowing the stack so you have to have machinery that allows you to do that so those are the sources of complexity in cats and scholars it but it and it's unfortunate because they're really very simple fundamentally but it's hard to know that just looking at the implementations in there in the FP libraries I think it's a really fun exercise to take this definition of free and build it out define map define flat map to define flat map you will discover that has to be a functor and you can build it out so that you can write little D s l's and interpreters and interpret them it'll be strict and it will be finite but it will work and it'll give you a good intuition about how all this stuff fits together if you've just been using this free pattern mechanically like I did for a long time ok so I wanna point out a few more things before you move on if we have so if we have a Co free we can always get an F out of it so we can always take a layer off but we can't do that with free because there might not be an F in there you might you might get an a out and then if we have an F we can always construct a free but we can't do that with Co free because you also need an a so on that basis on the basis of that distinction we can define recursive and Co recursive types and abstract over them and that's something that matreshka does for you and just for free you get this huge just explosion of operations that you can perform on types that are like this so there's some really nice general stuff going on so if you saw Gregg stock on matroyshka you'll have some inkling about that sort of stuff in this talk I'm going to build everything from scratch so some of the things I'm going to show you you would get for free with matreshka and I'll try to point that out the last thing I want to point out before you leave before you continue is that both Co free and free our fixed point types so if we look we see that each reference themselves in the same way that prof did and we can apply the same trick we can just add a type parameter and now we have Co free F where we just introduced a B for the recursive part and the same thing with free F and now we can define Co free and free as fixed points of those new functors that we've defined so that's just to show you that there's something really general going on here which is which is kind of interesting okay so enough of that so now we know the general types and we can define a profit ID profit really all right so profit is just fixed the prof F ID profit is Co free of profit profit annotated with with integers okay let's see if I can put this thing back so I think I may have I may have lost some people at this point some of that ran back up and try and make this list less scary if possible so here is our original data type right and here's the construction that maps to the tree down to the bottom so take a look at that and and be become confident that you understand how that fits together okay so now let's look at the fixed version boom okay it's the same structure all we're doing is wrapping it an extra constructor there's nothing mysterious about it it's just a construction okay and then the co free case same thing it's just like fix just like the original one it's the same structure except at each value we also associate an annotation okay so this is just data right we can construct it we can pattern match on it there's nothing mysterious about it the the the types are kind of intimidating and the names are kind of intimidating but it's just data just like anything else so please don't don't be scared of it okay so before we get back to the database problem I want to do some programming with these types it's just in a pure context that doesn't have any database in the i/o fx2 to worry about because that'll make it a little more complicated so let's write some parsers okay so here we have a we have some data it's a tree structure and we use indentation to indicate the nesting so you might recognize some of those names so what we want to do is parse this into our fixed point types so here's one way we could do it this is using a parsing library called add oh but it would look the same using Howie's quick parse library or really any other monadic parsing library so what are we gonna do we're gonna this the idea here is this will parse a fix of prof F at some given indentation so we're gonna skip skip the initial indentation we're gonna read the name and then skip the comma in the space read the Year skip a new line and then the magic part is we will call ourselves recursively and read many of these things at an increased indentation so now we have what we need we have the name of the year and the children and we can yield the fix of pro/5 and and that works the to string is not very useful so I I wrote a method we'll draw it out and I'm not going to show it to you but it's in the example code okay and it works so so we've got the the prop F structure the fix of the profit structure bag and let's see what we can do it with Co free so here's our fixed parser just with some extra extra lines in it and here's one with Co free and it's a little bit different so look at the look at the change right it's same structure we just have a couple extra things happening so what we're gonna do is read the parse position in and then do what we just did and then read the parse position when we're done and then what we're going to yield is a KO free that's annotated with the starting and ending position okay and that works and what we get back is this we get back the tree where each prophet F is annotated with its position in the input string which i think is really cool so our original reason for doing this is so we could annotate these things with database IDs but we can use that slot for anything so here we're using it for parse positions you can see how this structure would be really useful for doing something like a programming language where your your functor is a is some ast for your programming language and then you can parse it in and then you can annotate it with source positions and inferred types or do strictness analysis whatever all sorts of stuff and none of those annotations muck around with your ast representation so if you have a separation of concerns and you have a really simple data type and something else is is is giving the annotations for you it's actually nice okay so before we get back to the database program I want to explain something you might have been wondering about which is which is where did the F come from so turns out prof F is a function and this means we can map over it now if if you follow this design pattern it's always going to be a functor and in fact it's called a pattern functor so prof F is the pattern functor for profit for ID Pro they differ they differ in their recursive structure that we're applying externally but it's the same underlying functor so in any case the a only appears in the students so we can just kind of delegate to map to the map operation on the students member so if we look down the bottom we have a profit a profit F of string and it doesn't mean anything to us but it's okay it's a valid type and if we map to S dot length we get a profit of n back so that's fairly straightforward it turns out we can do better than that prop F is a traversable functor so that's even better that means we can sequence it so if we have a profit off of G of a we can turn that into a G of prof F of a if G is an applicative functor so don't don't worry about the implementation look at look down at the bottom and just look at the types so we have a profit of option int and when we sequence it we get an option of profit event okay so it flips those out are type constructors that's a really useful thing to do it happens all the time in monadic programming so if you don't know about traversable and applicative functors it's something you should learn about because you really can't do monadic programming without these things okay so we defined this Traverse operation up here but what we called down here was sequence so I want to show you what the relationship is okay so the definition of Traverse tells you that map F followed by sequence is the same thing as Traverse okay and that's just by definition and from that we can we can use equational reasoning to find another identity so FA is the same thing as F a map identity which is the functor law if a dot sequence was so we'll just sequence both sides of that so that has to be the same but we know map identity followed by sequence is the same thing as Traverse identity so we now know that FFA dot sequence is the same thing as FA Traverse identity so when you're programming with these things it's good to know the relationship at the top and at the bottom because depending on what's more performant or more more convenient you can just swap one for the other all right so let's talk about database programming let's talk about do be so do B is a pure functional database layer for Scala or in particular JDBC layer it's it's very specific to you sitting there are no side effects do B programs are values it's built for scholars ed and for cats as of the most recent milestones this is this is a new thing it's a type level project that I'm very proud of and I do have stickers for do B and other type of projects if anyone's interested I had 10 slides in my presentation to try and explain this explain how do B works and I think it's not enough if you don't understand programming with free monads and it's too much if you do understand it so what I'm going to do is kind of give you an executive summary of how WB works and then if you find yourself confused at some point later and they talk just stop you know and I'll explain I think there's a there's a the documentation for do B is good and there's some other presentations on YouTube that you can you can watch about it ok so the ingredients of do B so we have algebra is for all the operations for all the JDBC types so result sets connections things like that and those that defines the primitive operations that we can use we have the free monads of those and that gives us 16 little languages with a thousand operations that we can perform on them and that gives us composition that lets that gives us a way to take these atomic operations and build programs with them we have lipped lifting operations that let you combine programs that are written in these different languages so you can have a connection program and a prepared statement program and you can embed one in the other and then there are some built-in interpreters that will take you from these dooby types into something like scala said task or monix task or something like that io like data types so this stuff is all very low-level this lets you write JDBC level programming programs in a functional style which is very low level it's not very convenient so there's some higher level stuff as well so there's some constructors that let you get away from the integer constants and thing and irritating things like that the JDBC gives you so we have proper enumerations and that sort of thing they're resource safe constructors that let you say okay if I've constructed a prepared statement I don't actually get to see the prepared statement I can give you a prepared statement program that will handle it for me and execute it and and that prevents you from being able to leak these things you can't leak a connection or a result set or anything because the type never appears anywhere when you use this API that you don't you can't get a handle to the thing that you might want to leak there is a type mapping that allows you to allows you to read things out of a column and map them to a data type and then a new thing that I'm working on is compiled time checking of sequel literals and we'll see a little bit of that in a minute ok here we go so let's insert a tree so recall our prophesied type so the first thing we're going to do is make a program that inserts a prof F just ignoring the children and returning the generated ID so this insert node method takes an optional parent ID and then the prof that we want to insert and what we're going to what this constructs is a program that will do something with a database connection and give us an end back so what we have here is a sequel literal it uses some Postgres specific stuff to do an insert and then return the ID which is nice we support all of that stuff the interpolated arguments are not an injection risk this thing gets turned into a program that prepares the statement and does the properly setting set stirring said you had a different different indices so that so that's safe and then the unique int says okay we expect exactly one row back and one column that will contain an int which is what we want okay yes right now we're just doing the flat insert and we're going to come back and do the students later okay so I'm gonna get rid of this profit effing ition that makes one room okay so here is the method that inserts the fix of profit and returns an equivalent tree okay so this takes an optional parent and it takes this fix of prof F which is you recall it's just the flat structure just this nested structure with no annotations and what we're going to do is go to the database insert that thing into ensuring the equivalent tree that has the idea I the annotated nodes with the IDs on them so we take again an optional parent and the fix so we don't know how to do anything other than insert the nodes so we'll do that that gives us a connection i/o event and we need to return the connection I have something else so we're going to flatmap so we're doing this in a and a for comprehension so we get the prof F we recursively map the children over this insert tree operation that gives us a prof of connection i/o of cofee or FF at the end which is that almost the type we want but not quite we need the type constructors to be swapped so we call sequence so that gives us the head and the tail that we need to construct the Co free okay so intuitively really all we're doing is we're we're just trying to do a we're mapping this operation over the children you just need to use traverse in a Mon ahead context so recall that map followed by sequence is just Traverse so we can simplify that okay so we can generalize this a little bit more with matreshka you could you could do this with a Co algebra without a recursive call but we're just gonna leave it here for now yes unfix yeah so if we go back to the definition of fix where is that sorry that's way back here okay so fix one fix just gets the member out that's all I guess okay where are we insert the tree okay good so that's our insert tree program and it works so we are going to parse that data back like we did before and I'm going to call insert tree on it with no parent and then transact xa that's something I'm not going to show you that just associates this operation with a database pool and what we get back is an i/o an i/o program that we can actually execute so I'm flat mapping that into another program that I'm not going to show you that draws the cofre in the i/o mo net for us when we run that it goes up to the database and inserts everything and then returns it with the annotations okay and the reason the numbers are so high is because I've been compiling these slides over and over and over and over in there a bunch of cut a bunch of copies of this thing in the database okay so that's the hard part so now let's talk about reading it back so here's read node and what it does is it takes an ID and it returns a program that will read a prof whose children are its so what does that mean all right so that's that's a prof F whose children are database IDs so a way to think about this is we have one node in the graph and if we want to step off the graph we got to go back to the database and fetch more okay now I'm gonna acknowledge this is a very inefficient way to do this we're doing two selects for each element the way you'd really want to do it is load everything in memory and unfolded in memory but then I would be just be talking about sequel and it's not very interesting so in the in the example code I showed so what are we doing so we are going to get kind of the data we're gonna get the name of the year for the road we've asked for and then we're gonna get the IDS of all the children that are associated with it so we're gonna get a unique pair of string and end for D and then a list of N or SS and that's all we need to construct the prof F okay so that gives us sort of 1 local node in this tree what if we wanted two levels or if you want to be able to take a step before we go back to the database we can we can define that so we can read one who's and we get something whose children are IDs and then we can do it again on the children by traversing and now we get a prof F a prof F event so that means we can sort of take one step and get another profile and then take another step and we've got an E and have to go back to the database and we can you know we can do three if we want to we can actually generalize over that with a by indexing this operation on a type level natural number we can we can say okay I want to read ten and then terminate with an end that's in the sample code if you want to see it so this is this is an interesting thing you might want to do if you have a graph and you want to show it to the user but you only want them to see part of it you don't want to load the whole thing from the database you just want to load sort of a little local region this would allow you to do that and the types keep track of where you are which is kind of nice now we could load just sort of an arbitrary sub graph where where each child is either an ID or it's a node it's one one thing or the other does anyone know what type we might use to do that that's free all right so now free pops out this is this is kind of contrived but this just reads a tree it'll stop whenever it hits an even-numbered database ID so it's it's loading an arbitrary region of this graph out of the database which can be useful because you can decide kind of on the fly whether you want to keep going or stop with an ID and force the the user to hit the database again if they want to go farther so I'm not gonna I'm not going to take this apart you can look at it from the sample code if you want to but so really what we wanted to be doing is just read the whole thing back with the annotations that's the problem we're trying to solve so let's get back to that ok so here we go this is easier than what we did before so we have the ID so we're going to read note we're gonna say read node which gives us a connection I oh that gives us the prof evidence OPI is profit event we need a connection IO so we've got a flat map so now we're gonna map over the children with read tree that's our recursive call and then we'll sequence it to flip the type constructors and then we have everything we need to construct the co free so we'll map and construct it so we know map followed by sequences traverse so we can simplify that so that's a pretty compact little little method so I want to take a minute and look at this method more closely and see if we can generalize it a little bit this works but I there's something more general here so let's factor out the call to read node because that is specific to our problem domain so we'll just pass in some F that gives us an int to a connection I of professor event F gives us a connection I go back but the only thing we're ever doing with it is calling flat map and then map so it'll work with any monad right so we can factor that out and now we get an M of prof F int but the only thing we're doing with prof F of end is call traverse on it so we can factor out prof F it's just any traversable functor right and and we've got this int that we're taking but the only thing we ever do is pass it to F so we can so we can factor that out to okay so we this is the same thing that happened before we have something that's totally generic and it's useful right and we're not clever enough to invent it ourselves so this is this is just the effect full unfold for Co free okay and what it does is it says if you give me some seed value and a way to unfold it I'll just continue unfolding it forever until I get to the end okay and you would get this for free if you're using matroyshka this is another thing that you just get from the library if it's there it's not in Scala set or or cats I think it probably should be so but but even so I think I think going through an exercise like this is helpful because you know even if you're only calling this method one time in your program it's worth generalizing like this because the more polymorphic your method is more polymorphic your code is the fewer ways there are to write it okay which means the fewer ways you have to write it incorrectly okay so you can save yourself from making a lot of dumb mistakes by by going through this exercise when you can okay so in any case now that we have this our read tree method is trivial we just delegate to read note and we're done and does it work it works so I'm a little embarrassed by this because I as I said I've been inserting so many copies of this tree I actually have to find an ID and there are a lot of them so I find one one ID that matches hilberg so that's what that first program does it's not very interesting and then I flat map it into read tree and then I print it out and it does work so I fetched out Hilbert's sub tree and printed it out so that kind of ties them out and everything and everything works okay so I I want to point out that that I think it's really cool that we're doing this just totally generic monadic unfold and we're not thinking about database operations in our code right we haven't talked about threading a connection through or iterating of result sets or doing any of this stuff we're programming with these database operations just like any other kind of data which is what you want which is what you want everything works the way you would expect all right so let's review a little bit what are we saying so we learned about some fixed point types okay so fix and Co free popped out pretty fast free came along a little bit later and we've got we got two by pushing on our model and not really that hard these are natural things that are useful then we should learn how to use them and we use them to represent the same data-type in a bunch of different ways right Kofi was really awesome so we have a simple recursive type we have sort of an isolated node with no child information we have a tree annotated with parse positions with nodes with database references we have partial deserialized graphs and then of course we have the full graph with the database ids which is the last thing we built and we get all of that with the same definition of prof f we never change that after whatever select River it up here slide three or something and we pushed our code around you see what I mean you you can you can generalize generalize generalize and sometimes you you wind up with something that's interesting and hopefully you all survived I know this stuff is hard the sample code has a lot more examples and there are a lot of comments in it so if you look at that and review the slides and just contact me if you have questions I'm very easy to find and hopefully you'll find a way to use this in your programs and that's all I got thank you very much okay let me let me point out if you look on github Mico free repo has all this stuff in it if you're interested in recursion schemes look at a slam data matroyshka and sell out recursion scheme you talk it has a lot of great stuff in it if you're interested in Dubey there's a lot of good stuff on the website and i wanted to point out that 47° put in a they made a Scala exercises module for Dubey if you want to play around with it online it's really cool I think I have time for half a question anyone what I don't have time dance for that okay I don't know about that possibly I mean it's it's an example I mean yeah you could I mean you could you could say okay well it's just a rosetree and pull out and pull out the it's it's it's Co free of list and the annotation is the name and the year and that structure is just a list that gets unfolded over and over yeah so you could generalize it if you wanted to I mean at that point it might not be very convenient but you can there are some more fit you can turn one into the other yeah good question okay we're out of time thank you [Applause]