scala.bythebay.io: Greg Pfeil, This programmer modeled his code after wooden nesting dolls
so so yeah I used the BuzzFeed title here but I forgot to do a control talk to see how the crowds turned out so I don't know if this is actually effective but um in any case uh if you don't know what these wooden nesting dolls I'm referring to are they matosas um Russian nesting right stacking dolls you get a bunch of them um and so I use this as a metaphor for uh for recursion um so there's a matoska library uh written by me and other people in my company uh slam data uh or the company I work at um and then this talk is also is available um at this repository and there's other versions of this talk from conferences I've spoken up before also there um so yeah so I've been talking about this recursion scheme stuff for uh this year a lot uh and what it's about is basically separation of concerns which you may have have heard mentioned in other contexts as well in this case it's separating recursion from all your business logic and stuff like that and so you don't Implement um recursive functions all the time you basically defer to this library to add recursion to your to your programs so we talk about how to do that um the name atosa is meant to invoke the idea of finite nesting right there's only like seven or eight of these dolls that stack up you don't have infinite recursion and stack overflows and stuff like that the idea is that um it models a finite um terminating recursion however there is a duel to that which is um um co-induction so induction and co-induction which if you were at John deo's talk um yesterday you might have heard some stuff about that um and that is basically a way of modeling infinite recursion uh in a way that is productive uh where you're producing something at every step uh and also avoids uh it's a way of modeling event Loops um without worrying about things like stack overflows and things like that so matoska models both of these um versions of recursion and co- recursion so recursion schemes is a pretty big topic um the library itself implements some portion of that uh and is increasing in how much it implements uh this talk talks about a fairly small piece of metosa and um Sor oh far away from the mic yeah sorry um so is this good yeah okay um so yeah matoska implements a small or some portion of recurent schemes and is is growing in in what it implements uh this talk kind of covers a small part of that and also a bit of uh if we get to it um the future of of where moska will grow to um but isn't yet covered and then tomorrow Rob Nars is giving a talk um that uses recursion schemes uh and some database stuff that that he's working on and he has a really great uh motivating example and stuff I really encourage people to to see that um and so yeah so that's kind of the what I'm covering here um I always forget this part so I wanted to put it up front um I didn't invent any of this stuff this is you know like me reading papers and talking to people and stuff and this is sort of a list of the biggest uh influences uh Ed KT and Patrick bar both have very good hascal um versions of recursion schemes implemented um Patrick Thompson has written a bunch of uh introductory BL posts and explanations and also given some talks on recursion schemes uh that are very helpful uh there's a ton of papers on recursion schemes two of the the biggest ones are uh are this functional programming with bananas lenses envelopes and barbed wire uh which these are not the lenses of Optics if you're familiar with Optics it's just uh specific to recursion schemes um and that's by Eric Meyer and others uh yeah anyway so and then finally um type level which this is a type level incubator project um the type level Community has been awesome and they're very supportive and very explanatory uh they they're happy to discuss things and tell you like you know or uh explain how how to approach different problems and a lot of this wouldn't have been possible with uh without uh learning from various people there about how to solve different things I run into so I want to shout out to them um so we'll start here with a simple simple as um and this is a recursive as you can see uh here you know so it's this expression right this abstract class expression um and in in one of its case classes that extends it it refers to itself right so you're basically creating a recursive structure here with um some number of multiplications containing uh numbers at the leaves right of this this tree of operations and you might have some evaluation um function that takes your expression and then returns an in right evaluates that that thing if you hit a number node it just returns that value uh if you hit a multiplication node it recursively um calls evaluate on each of the two arguments to that um does that make sense that's pretty that's the kind of starting point for all this stuff um so um from here what we like what I mentioned is what we want to do is uh is separate recursion from our code so we don't have to think about recursion and things we do um there's a great talk by Steven comple called um add a type parameter uh and uh and that's what we're going to do here so we we add a type parameter and so now where we previously had recursively referred to exper in these cases we now just refer to a our new type parameter right so so we have an exp per a which is now a functor um and you know num doesn't actually use a it just still has its int but in the recursive cases we're now referring to a right um and so here's our new evaluator although it's kind of odd it just says like oh well if the a is an INT we can just like you know just multiply those inss but I mean how do how do we end up with a you know with your a being an in we want some recursive structure here we don't want to this so we'll figure out how we can get to a point where this is this is actually implementable um so you know we have to get we have to reintroduce recursion somehow right we we've pulled it out now of our data structure but how do we say we want to use something in a recursive context you well you know previously that a was just expert so we can just you know expert of expert that that well that doesn't work because takes the type parameter and so you end up an expert of expert of expert of expert of expert just recursively right now this this actually would work um if you wanted to make something that was no more than five levels deep right just like as long as it fits within those first five levels you can you can write your exper um and if you wanted to have one four levels or you could actually um yeah have it no more than this and it would still as long as you hit with the leaf nose it would terminate anything up to five levels deep but of course this stuff isn't isn't really what we're trying to get to um so uh there's this nice little uh type called Fix which itself is recursive um and this is basically like the Y combinator but applied at the type level um so basically fix of some functor which in our case was exper right so fix of exper um holds a value that is a exper containing recursively a fix of expert so this is your way of of tying that knot of of saying exper exper exper exper exper as deeply as I need right without without having to to be explicit about that level of depth or anything so now we have this type that that tells us that uh we we have a recursive structure here of experts and that's what that's what this is indicating um so I mentioned fix there's two other ones uh I'll use all three of them in the talk as I go through um fix is defined as I as I showed here very very simply very directly it's I feel like it's really good for explanation um mu and new are are more complicated definitions but they're meant to model explicitly the inductive and coinductive data structures I mentioned before so like finite structures like a list and then new would model infinite potentially infinite structures like a stream uh things like that so so depending on um on which of these things you use you kind of have different performance and and behavioral properties um but again you can like kind of put them all in the same position you could have fix of exper mu of expert new of expert and it does change some ways in how they behave in recursive situations but um but all represent a recursive structure of exper in that case um so since we have a bunch of them we can we'll make a type class right and so now we can say like oh okay all these things can have the same behaviors how we can Define that type class uh the type class is for some type uh and so I have an instance here to show you with fix um for some type fix of f there is What's called the base or pattern functor uh in in the case of these types that's just actually F itself right so fix of F and this so in the if you had a fix of of exper your base would be exper in that case um and uh and then there's a single uh operation you have to implement uh abstract def which is uh project which basically takes your um you know your recursive structure and unwraps one level so now what you have is that exper right which is the structure you like to think about containing recursive expers right so this project basically unwraps it from that structure and in the case of fix let go back to see here um you know fix just has a field unfixed which is that structure so it's very simple you just access the data that fixes holding uh and again with mu and new it's a little more complicated but um they do effectively the same thing they all can implement this this project um and now so this can really model basically any recursive structure you can see we basically here we um we reimplement lists right so we we Define a funter for lists uh just as we did one for expert right so normally this takes one type parameter now it takes two B being the recursive one um so in the case of nil you don't use either of them but in the case of cons instead of the tail being list of a uh since it's recursive you just use that recursive type parameter um there for your tail so you actually now just have two type parameters you can either get the head of a which is a or the tail which is B um and so now the type list is isomorphic to this mu of um the list funter and uh and this other type coist the Dual of list is new as I mentioned the MU is inductive and the new is coinductive so potentially infinite so this is how you model a stream uh there's a reason I didn't call it stream I'll get to that in in a little bit but this is the common kind of model of stream right where you can have a potentially infinite list effectively um but again notice that like there's just the one functor uh when you define type classes on this funter like by Traverse or other type classes um you get to take advantage of those in as if you had done both of these data types right you don't have to reimplement everything for stream that you had implemented for list or anything like that you basically just say oh I want this structure to be potentially infinite in this context so you get to defer that decision as to like what is the the shape of this basically or what is the um behavior of this until uh until you actually need it with only defining this you know one shared functor um but it turns out you don't actually have to replicate lists you can actually Define a recursive in this instance of this recursive type class on list directly so you can just say that list of a right is recursive you still have to give it tell it what the fun is and that's actually why it's defin in this particular way with the fix Point types before did I go I went back too far with the fix Point types Before It's seems kind of silly to not just make at least I thought so initially um to not just make recursive take this fix type and and not have an F here and just make the F happen in the in the operations as a type parameter at this level um but the problem is with when you start dealing with things like lists or co- free or other other data structures um that no longer holds so here in the case of list a or of list uh you have to um say that the functor is this list F which you clearly can't just like automatically derive from you know this type or I mean like you know the you couldn't do a type class where you had like some list that takes some parameters and then that parameter is filled by list F so anyway here you've mapped you know this is your recursive type and you say like okay the funter for it is this and then again you just have to Define project which Maps the nodes of a normal list um to your functors so now you have an instance of of list being a recursive structure right um there's actually a basically like I mentioned before basically any recursive structure there's the three um true fixo ones that are um that just take some arbitrary funter uh list and code list as I mentioned both take um both use list f as their um as their functor and this is why I didn't call it Stream So stream here uh it's fun it's just a tupal So it's b this is like just think of where this question mark is uh this is just kind projector if people are familiar for yes what is exactly implementation of um I can show you the implementation of yes CU that one's easy to show is a yeah there is um here let me I can see here make this a little bit bigger um so here you can see Mew uh it's again a case class um and it takes um this what's called an algebra um so it is basically T it is basically implemented as a fold itself um and so this is the m structure and then the uh the new structure uh oops hold on a sec there you go um the new structure which I also make uh is effect is very similar uh but instead of taking an algebra structure so this this is just a uh just add a comment here that says that this is actually a function from a to F of a um this is what's called a coalgebra and so new is Define using uh this coalgebra as it as its basis yeah they are very very different yeah yeah fun some properties have to rine for point different um no you don't um there well so in the library you'll see there's there's a bunch of uh of sort of for free type classes you get when you have um recursive some recursive instance and then when the base funter on it has by Traverse or B foldable or s or or monad or other things like that um so so just by the combination of your um type classes on the funter and typee classes the recursive type class uh those properties fall out um so and I am happy to take questions during the talk so I'm I'm glad somebody did a couple people have and um yeah um so uh I was getting to stream here um and so so oh I mentioned that the question marks are from kind projector this is basically like a partially applied type right we're just saying we're turning this into a functor of a type Constructor of one parameter by specifying one but not specifying the other um which is what all these the shape that all these have to have um so in the case of stream uh the funter is just a tupal where a is the value type of the stream and then the question mark is or can be represented by recursive versions of this same structure right so you basically just get a a a a a so the difference between a well I'll call it a true stream and coist is this is always infinite it has no end right it will just continue to generate values indefinitely it is whereas coist can be terminated uh and that's that's why I made that distinction earlier not calling this stream although stream is the common uh commonly used terminology for it um other structures uh I I thought I eliminated all mentions of free and co- free from my talk Rob but apparently this this stayed in there uh so these this is the environment Transformer uh Kad uh and this turns out which it's it's a useful type on its own uh but it turns out to be the pattern funter for for k- free uh free which is the Dual of cofree um Nat right so just a natural number uh turns out is just the fix point of option none is zero and sum is you know successor uh and then for any arbitrary type you can get a funter from it um just using const and so you can get uh if you if for some reason you want to use some Nona recursive type in a in a context where you need recursive type you can um take advantage of this instance oh I'm not plugged in is there a there is a plug thank you for that all right so that that recursive type class I showed you um we had one yeah there's an instance of it here right where we Define the project it has a duel so we reverse the arrows right miles um so uh in its duel it also has the same base functor uh in the actual Library this is this funter is pulled out into its own uh super class of co- recursive and recursive I don't know if it's worth actually keeping it that way but it is a some shared aspect of the two uh and then the Duel of project which unwraps one level is is this embed operation uh which takes I'll look at the implementation because the implementation for fix is often clearer than the the type class specification um so it takes some unwrapped one right where you have a x say expert of fix of exper and it wraps it back up so you go you go back to that um that recursive structure uh so that's the Duel of um and this type class is the Dual of recursive so we'll see that everything that you can do with the recursive type class has some corresponding operation in the cor recursive type class um so what kind of thing can we do with this so um so here's one of the other operations in that type class which is already implemented um although some of the instances like me and new override it to take advantage of their their particular structures um but a catamorphism is a uh is a fold which basically takes a function from some funter of a to a which you'll notice matches the evaluation thing we showed earlier an exper of int to int where we basically assume that the nodes of you know the recursive things are not actually recursive but just have already calculated values in them and so we only have to calculate one level here uh and so basically takes a function of this shape and applies it across an entire recursive structure so you can go from uh T can be fix of uh fix of F and can it applies it recursive applies a recursion for you and so you get the final a value which in this case would be int uh and the way it works is it basically takes your recursive structure does the project unwraps at one level right then recursively calls itself so it keeps basically just goes all the way through your tree unwrapping one level one level one level and um and then finally and then once it's done you know each call returns uh applying this operation so when you're actually at the leaf nodes of numb right those are that's like a terminating case you just um you just get the int back and then now you have ins in those places where you call mole uh we can see I think here as an example of like here's some recursive structure right so it'll it'll Traverse through pop pop pop like unwrapping all those things projecting them all out then when it hits a numb it'll just replace that with two replace that with two with two with three and then it'll say okay now I have a mole with just an INT two and an INT three it'll turn that into a six and so on and eventually it'll evaluate to to 48 applying that recursion through your whole system um and uh there's again there's this dual uh this dual notion anamorphism um which does the opposite it takes some value and recursively applies the Dual of the opposite of this right where this is f of a to a this is a to F of a uh and so it it applies that repeatedly to this single value to get some recursive structure so we'll see that here where you can say call Anna uh with some function that says like does prime factorization which whenever you hit like say if you hit a composite number it just somehow breaks it down into two components and it will continue to break those down recursively and you would end up with some kind of tree sort of like this where you see like at at the end you end up with mole of num mole of num mole of num mole of num and num right and so you would have your now recursive tree that would have all that stuff so you can you can build recursive structures from from seed values um and here's implementation of fold right um using this so so Kata is a generalization of fold right uh you think of foldable as a generalization of uh you know as a as a generalization of like kind of fold right on list but actually what foldable does is it makes you think of your data structure as a list right it throws away all the other information your data structure whereas this allows you to say like well depending on which the ACT what the actual shape is I can do different things so if you do a catamorphism you know as we did here on uh with the evaluation you're you're matching on numb and mole it's not just like you have one uh piece at a time you can do arbitr comp complex things related to your data structure um so this gets more generalized um all the stuff can be C I'm not going to mention that Rob talks a little bit about that stuff um because recursion is not always simple right you often want to like short circuit or do other things I'm almost out of time time so I just want to uh I won't go too much into details but basically all of your folds all the recursive operations can be generalized over some konad um in this case a tuple that carries the original structure with it as you fold so you can always look back and use um deeper parts of the original structure to inform the decisions you're making now and again all these things have a duel so whereas uh in the folds you have an arbitrary comonad in the unfolds you have an arbitrary monad and uh and that so in this case we have a disjunction where uh when you're unfolding you can decide that when you hit a certain point I don't want to keep recursing down that structure I just want to say like oh here's the the rest of this Branch right now just recurs over the other you know branches from this thing but this branch is now done and so that's what this particular thing is but again can we generalized to arbitrary monad and comonad so there's lots of variation in what the behavior can get out of this um so here is a cheat sheet which I don't expect anybody to actually look at but um this is some of the more popular ones in their names uh because before people actually generalized it they were like oh here's one case oh here's one case and then somebody noticed a pattern and said like oh we can just uh generalize these but but there's a lot of them and there's tons of different variations you get like that uh I have to switch back to this um so yeah there's you know there's a ton of benefits you get from this like so as uh Patrick Thompson paraphrased his paraphrase is much better than original I say Myer at all go so far as to condemn functional programming without recursion schemes as morally equivalent to imperative programming with go-to so hopefully that chastises everybody into into looking into uh separating the recursion from their business logic uh it might be a little strong I feel like there's still a lot of cases where um it's not obvious how to map these things although there you know there's always more research in this stuff um you can do interesting stuff like annotating um arbitrary Tre trees without having to create new structures uh Rob will talk about that in his talk tomorrow I think right uh and then some other benefits you get is uh these these structures these algebras uh are composable in various ways like you can zip them together right so you have one algebra that evaluates and one that like pretty prints your whatever your language or structure is uh and uh and you can zip them and so now you do one traversal of your data structure right one one traversal and uh and it gives you both values back so you don't have to do multiple passes over your data uh and there's composition you can you know apply these things one after the other um whereas the anamorphism applies things kind of you know from the base to until you get to Leaf nodes and then like wraps that as you go and then you can unwrap and and apply um some fold to get some some V value uh this you actually get what's called a um Fusion uh where there's an operation like this where you never actually build a recursive data structure in the middle uh it can apply one operation basically pulling apart your pieces and then a separate operation folding it back down without ever build that intermediate structure so you can um the these compose very efficiently uh and you can you can get some good performance gains of doing that um so uh The Next Step which I do not think I have time to really cover is mutual recursion which lets you not just have a single say functor that like oh here I can have any of these nodes any of these nodes it allows you to to use gads to categorize and say like in this particular context I can only have a node that has Type int and uh so like in the ad node and you can here cons has Type int and AD also has uh type INT in this position and so basically only those nodes could be used in this position here whereas like this one requires a tupal one which is generated by this pair thing at at this point has that same tupal shape so basically this allows you to to restrict and uh and use uh different pieces so I won't get into the future work stuff um but yeah uh any questions h [Applause]