Scale By The Bay 2019: Oli Makhasoeva & Andy Scott, Recursion schemes with Higherkindness

Scale By The Bay 2019: Oli Makhasoeva & Andy Scott, Recursion schemes with Higherkindness

Recording: Scale By The Bay 2019: Oli Makhasoeva & Andy Scott, Recursion schemes with Higherkindness

[Music] hello everyone welcome to our session I'm only I'm solutions architect at 47 degrees and I have a couple of podcasts about Scala and we're presenting today with Andy so welcome and hi I'm Andy I work on the Scala team at stripe where we're responsible for builds and infrastructure for our scholar repositories mostly used for data and data processing yeah so we we have one mic and I guess we're gonna be talking over each other while the other persons types so we'll see how this goes okay we don't have any slides whatsoever and we're really like let's figure out cross that everything will go fine because we're gonna use skocy and rely on this fantastic internet here and let's start a new snippet so we're gonna talk about recursion schemes and Andy let's start with your motivation why is it important so I like recursion schemes because they give us a really expressive way to build up or teardown data structures and they allow you to really focus on your business logic yeah so that's the main reason it allows you to express really powerful algorithms with really really simple steps with a really simple encoding it also lets you operate over many different kinds of data structures using the same code which is something that we often like to do as functional programmers yes to give you a simple example we wanted to talk about skew Murph the library open source library that we're building at 47 degrees but unfortunately I don't think we will have time today but usually when you're working with some kind of protocol for example prod above or average you're building your own data structure and that data structure needs to be traversed at some point you need to make some computation based on that and recursion scheme is a technique which allows you to be focused on your business logic and avoid boilerplate almost completely no internet you kiddin me well while we're trying to find a connection and can connect to something we can use Xfinity we can okay we can talk about the most popular recursion schemes that data structure which everyone uses at every project I bet you any ideas it's a list guys it's just a list so what are we gonna to do a little bit of foreshadowing of what we're going to talk about today we're gonna grab two functions from standard color libraries library it's cool we don't have slides but we have cats so our presentation is allegedly cute because of that so we're gonna talk about least and the first thing that we want to do is just grab two signatures from Scala standard library fold right and unfold okay this is unfold as you can see this is just a standard I find what can go wrong when you are doing live code independent on internet right so many things yeah so many things your keyboard doesn't work okay let's start with it and fold right this is also a member of list so the first thing that we want to do with this is to clean up it a little bit meaning that we want to rename some type parameters and also we want to pass lists inside a full rat because it's no longer member of but we need to operate on something you want a bigger yes it's bigger okay so let's possibly since act and let's rename it a little bit we want to have an e-type parameter because it stands for like element of a list it will make more sense later on let's rename that for unfelt too so we will have e and a this function are pretty similar and this rhenium will allow us to show that in a more detail so in order to implement that the first thing that we can do the only thing that we can really do it's a pattern match on the initial parameter because that what would compile right in if we have an empty list we return the initial value otherwise we need to call our operation and call recursively our same function with tail and posi and all right let's give an example and show how it works so we will try to write a product function and yes this is just a multiplication of two integers and then let's call this fold right with that function so we pass an initial list which is 1 and 20 with the initial value 1 presumably that will return 200 because while multiply terminals but 20 is 200 yeah cool now do you wanna refactor this or implement unfold okay let's implement unfold again using closer look technique the only thing that we can do here we can call F with an initial parameter and then pair match on the result so in case we have no results from our computation and knowing that we need to build some kind of list which is return an empty list in case we have an element which is concatenate that with the recursion call you are typing too fast of our function so let's give an example again and make sure it works as expected so what do we want to build is the ranch function which will generate a list of numbers going from ten to one in this case so we just got two in two integers no this is given one integer will we can return two values or no value at all so that can be implemented pretty easy yeah so let's see if it works my job that uh okay cool so now as you can see in each of this function fold ride and unfold we can do a little bit of cleanup so that we could get rid of passing Z and up over and over again or F in case of unfold again so let's do that by moving the list parameter to the return part so that the function would return the function yes in this case we just use the kernel and instead of full drag on tail and passing Z and now we can just called kernel until and remove this part yes yes we need to change how we call our product operation because now list is the last parameter right but otherwise it does essentially the same thing nothing has changed tremendously same 200 I guess oops yes okay and same thing for unfold we passed the initial parameter into return in value and write a function anonymous function was the kernel again to get rid of passing this F around yes just instead of unfold called kernel on a yes this is the first step of our refactor and you already can see that unfold and fold dried are kind of similar functions but going further we'll want to do more refactoring and change the signature of fold right yeah so what we're gonna do here is fold right takes two parameters and unfold takes one it's possible for us to combine the two parameters of fold right to get two functions now that look much much much more similar so a first thing we can note is that we can produce this Z value using or excuse me a B value using this Z constant or we can use our binary operator that takes an e and it be a tuple EB and produces a B so you can think of Z as a function from unit to B and you can think of the binary operator already is a function you could also join those together and think of it as a single function that takes an either so on the left-hand side you're going to produce that initial Z value on the right-hand side you're going to call it you're gonna use the binary operator right and so if you have an either with a unit on the left you can more cleanly express that as an option of whatever was on the right you can just discard that unit value and what we wind up with here is the exact or rather the the dual of the air the the function that we have from unfold so instead of going to the option of the tuple we are starting with the option of the tuple and going to a single result so we're starting to make these two functions fold right and unfold look really really similar or much more structurally similar right and to refactor to use that single arguments just a simple replacement and then making sure that we pass in and sum and the appropriate appropriate spots also we have to refactor the product opt because a product op because now that also includes our initial value it includes everything about our computation still the same full right from before computes the same result so little bit less efficient we're not really worried about efficiency right now we're just trying to show that these are the same great so that should work cool copy-paste these before we refactor like say fold rate and save unfold cool so what we want to do now is we want to really think about what these two functions are doing and kind of compare the two of them and what we're altom utley gonna do is we're going to take list our data structure we're going to pull that out of our fold right and from our unfold so we're gonna abstract over our data structure and get a generic fold right or generic fold and a generic unfold and to do that we're going to look at the function first our implementation rather and we want to identify everything that is specific to our list everything that's recursion related and then really anything else and we're gonna identify three steps the first step is we're unpacking or projecting our list and you can see that because we met pattern match on our initial list value so we break apart our list the second thing is that when we're at recursive points which there's only one in our list it's the tail we're gonna call ourselves we're going to call kernel and then the third and final bit is we actually do a computation which in our example is computing a product so we have these three steps we break apart the list we do recursion and then we do our computation and if we do that same analysis on unfold we wind up with almost exactly the reverse the first thing we do is we do our computation that's going to produce this option of tuple results we're going to inspect that and do some recursion when our computation says we need to do recursion which corresponds to the tail of our list and then finally we're gonna repack or embed back into a list so we're gonna smash things back into a list so same three steps just well almost the same three steps but done in reverse order in one case you're breaking something apart and another case you're bringing it back together cool so what we want to do and we don't have time to go through every step super slow we're gonna kind of make some jumps here for you and if you want to go through this slowly we plan on doing an unconference later so you also come to that where we can just work through it real real slow oh wait wait undo undo cap no it's save fold so you ready copy paste it cool all right all right cool so what we're gonna do is it turns out that option of tuple that carries all the information about our list through the computation if you dive into recursion schemes that's often called the pattern functor but basically we can use that to interface between our three different steps so we can unpack our list into this option of tuple we can do our recursion in the opposite of option of tuple and then we can do our final computation using that option of tuple it just kind of threads its way all the way through are all through our code and so always doing here is she's stepping out all three of those methods we'll implement them quickly and then we're gonna take the apply method from our fold rights and just call step one two and three in the correct order and it's just gonna work well hopefully we got the types right and then it works right so if we implement these methods then we just call step one first we pass that to step two and then we call step three and this should compile is just going to throw an exception if we run it so we need to implement implement these methods now we're removing step three because step three is simply calling our computation so we're just going to call that directly I don't need to have an additional function there great this is the one time we actually want an error of that shape so it worked let's go ahead and implement step one and step two for step one we need to unpack our list so we're starting with that list we're gonna pattern match on it there's not much we can do other than just stick the results in this option of tuple important to note that that recursive point the tail of our list gets stuck in the second item or the right side of our tuple right so that second element under a tuple correspond to the tail of our list the first item in our tuple corresponds to the first item in our list so that option of tuple captures everything about our list right so we pattern match o step 2 the perils of using ska ste so for step 2 there's we're calling recursion only for the recursive points in our list and so we've put that in the the second item of our tuple so if we get some of a tuple we're just going to call kernel for that second element in the tuple so just calling the recursion only for the spots in a projection of our data where we need to and if we do this correctly it should compile I think it compiled it produced a result so that works right we just took it's ugly it's inefficient but we just took fold right and we split apart the what seems like a really simple implementation we split it into three separate steps to isolate data from recursion from computation so what we're gonna do now is we're gonna pull all this out and before we do that we're going to first introduce some type aliases one because we need them and two because it's pretty obnoxious to type option of to pull over and over again so we're gonna introduce type F of P and that's going to be option of tuple with that right side kind of varying depending on what we're doing because that's that recursive point in our list and we're also introducing a type s I think of this as structure and this is our list of some elements and we're just going to replace all these parts throughout our code Oh oh you're gonna add the bracket yeah and the one at the end cool that should work great and we get the same result this is the same code so now what we can do and I think we might switch here but what we can do oh we have a little more cleanup to do step two it's taking an F of s then going to an F of OB if you're familiar with cats or just familiar with Scala in general that looks a lot like a map on some kind of a structure because it is so we can if we have a functor for our F then we can just call map right we can call map and pass in Colonel so we can map over our structure and call Colonel recursively at this wherever it needs to be called so we can replace step two with just a functor F map and we're gonna use cats for that which we've already added to the project this part is not particularly clean just because we're using an option of a tuple but we need a functor for an option of a tuple so we're gonna leverage some functionality and cats to build up a composed functor across those two structures so we're asking for functor option composed with tuple to give us a function for functor for the whole structure right and so this should work step two can now be replaced with an F map over colonel and this should compile it should get the same result we have the same signature from before we've just kind of filled with all the bits inside our implementation great and step two we don't actually need it a separate step we can just call F map directly in our implementation same thing great so yeah we're going to switch what we're going to do next is we want to pull out all of these types and as we do that we're gonna wind up with a completely absent full that operates over any data structure and always going to walk me through that so okay as you can see the only thing that is tied to this type that is here is the step one we still do pattern matching on our data structure and what we really want is to have a generic function which can be passed inside our fold right so that for your specific data structure you could provide how you're gonna project how you're gonna be unpacking it okay let's pull as out first probably or lets us do that in whatever order you want yeah so lists eaten our signature a full draw doesn't make sense anymore we're not tied to the list so let's just say that it is some kind of structure that what S stands for then we can get rid of option as well because this is let's let's add functor instead of having it inside yes so and we got rid of option as well because this is a specific pattern no Parton Panther pattern for list so now let's move project out of here project yes Rick shall I still need this implicit right we need to simplicity for a functor okay so maybe let's introduce the project front or type about this we could type this whole thing out we could type this whole thing out we're just expanding our types or we could introduce some more type aliases to make life a little easier like I could expand está lista v I could expand the F to the option but instead okay so now we have a project list so you can implement that for any recursive data structure and then just pass that inside fold right and that would work just just fine so you could get rid of boilerplate and you don't need to write this folds right yourself you can use library like droste or matryoshka what did you do I just okay we don't need so now we just need to pass project in now let's pass project in and make sure that we still get the same result do we yeah gotta help Scala we were really running out of time works okay it works so now if we look at full dried its we can just say that it's no longer fold right its mas its cotta and our F is not F actually we can give it name finally right it's our algebra and we could do the same refactoring for unfold we don't have time to go through the full refactoring for unfold so if you have to believe if you do you wind up with the exact same result just with the reverse ordering and the reverse computation for everything so I'll go ahead and do that now and then we can kind of just look at the two but you get the same results just the inverse okay so you just need your call jabrai you need f as a function say that it's functor yes and the yeah turns our vests then you need embed function which girls from FS to as and then three implement apply oh yeah I mean that's returned us you know the first thing you do is call algebra or our computation than mapping our work and then embedded that into your data structure and this is anamorphisms so earlier we took the project's list and we pulled it out of our implementation and made it more a little bit more generic when we refactored to get an a' we needed to do the same thing and we would wind up with embed lists which also just looks like the dual of projecting so we need to go ahead and do that now so you can see they're pretty similar so we could think about like how to get rid of recursion in you in your data structure and how to project or embed how to have this option in fact contains two parts how you break down your data structure you have an element for your current step and you have the rest detail for further steps same thing for your custom data structure you need to have like parts how you break down the what you do on the next step of your recursion so here we have cat and animal fees and yes finally we've got all our pieces together and now guess what we want to do right really we need to do that so basically we definitely have time let's do so if you think about computing the range and then continue the product over all the results of that range you wind up with factorial so let's fuse these together and you get a high level morphism so we unfold we don't actually save it to a list and then we immediately fold it back down and so if you look at the signatures for Anna and cata they look exactly the same because they wind up being exactly the same so we can refactor a little bit rename it and we can come up with a really clean and fun factorial implementation I want to put emphasis again on the fact that Halle allows you not to save memory by not creating the list as an intermediate step you just go exactly from values from unfolding it to folding it without creating idiot step which doesn't necessarily mean that for Carson schemes is the most performance way to build your application but who we also could have built like quicksort for example using highlight as well we're not going to do that right now but it's possible so factorial of 4 is 24 cool I think that's mostly it but we'd love to show more recursion scheme stuff if you want to come to an unconference later you can do it more advanced stuff like fusing more of these algebras and Corral tripperz together to do multiple computations in one pass and other really fun stuff but that was it yeah I also wanted to mention that initially I wanted to talk about skeuomorph the library so if you are going to unconference please join us I will show how to use another data structure and apply an amorphous man Casimir fees man how to actually use that in practice and how we use that in production all right great can we give them a round of applause and thank you guys very much that's a really tough to do that [Music]