All About a Fold

SF Scala: Gabriel Claramunt, All about a Fold

Recording: SF Scala: Gabriel Claramunt, All about a Fold

[Music] well my talk basic is how about fault and I promise that everything about that fault with the disclaimer that is not actually everything because we're going to spend too much time on that but yeah I I've been in the I've been working with Scala she's a lost time I think it started in 2008 and I really got fascinated by the virtual outside so I started to try to learn a lot of thought so I banged my head against the wall trying to understand complex stuff sometimes I I had sausage sometimes I fell but I kind of I like to try to tell everybody about what else whether the problems I had and what I what I discovered in the way um so basically this talk is youkali you could have a mental force right do you use false it makes me deeper arms Cara yeah cool I like it it's good D is false well I want usually do you form most of the times at least yeah I mean that's kind of what the problem starts but it's amazing I mean I started with learning Scala level about falling in the list and is amazing you have a whole list of things you put a couple of functions forth and you get that resolved you don't need to iterate checks check index whatever it's just very easy and the day you had to remember for awhile for rightful left which one is strike safe which one is doesn't work and then I started learning more stuff and this kind of can affect false is not that just an interesting function to use we have some kind of background that understanding that allows you to get a better understanding of how forwards and why can be useful use usefully another place but but let's try to reinvent the wheel so we can learn something in the way basically very simple problem how to sum all the elements of a list you have a list of numbers you want to write this function right how do you will in implement that yesterday somebody told me okay you put nums dot some yeah but that work obviously we are not going into that the ID X because we are trying to build from functional programming principles we got to use recursion and pattern matching as the basic tools this is an amazing book I really like it love it when I did the little schemer that covers a lot of ground in like this I don't know 100 pages it is it takes you in a tour for the whole computer science thing but you start building all your problems pearls in scheme using recursion and pattern matching and we have to try to use that so list in Scala this this is the how we declare list but basically we are building you remember what are the components of the list yeah it's kind of you have a ahem I mean this the color column that you put together an element and a list and is the empty list that is near so you want to use recursion of pattern matching within a case for for those two options right so if you want to get the sum of the list what we put in the first the first line exactly that's good yeah zero not in the second line yeah exactly the first value plus the recursive call of some that's a good one yeah you made it okay that's a good one this we're kind of using only basic functional perming things but our matching recursion okay let's try this the same exercise again but with strings we want to convert the list to ally just a long string right again what we use for the V is the same thing we use pattern matching we know that at least at the knee case and the cons actually in Scala we have this normally that is known as the cons list the least you prepend elements before so we have the the case of the hair on the tails we would the first case empty string and the second case kind of here we are going to abuse just a little of Scala we use like this basically we concatenate the two strings one thing I would like to have done is to be more explicit you believe X dot T string just to be sure because int is not the strings but yeah we're going to let's Cal I convert that to string automatically so again we got they took the the basic the empty case which is the empty string the case with the head of the tails is their head converted to a string concatenated with the recursive call that's good we have to course that looks pretty much the same we're going to try once again the same list but right now wait was a little more a little more complex we're going to use generics we want to check boolean property we want to check that the whole list complies with a 450 property so again we use para matching what we'll use in the first case true yeah somebody yesterday say false and it was interesting but it well it will really work but yeah basically you can prove anything for the empty list right so now more interesting for the second case when you have the header details again so we're somewhere we had to do the recursive call because we're already going doing the recursive you know the other places so what you will put here sorry yeah we use it true for the empty case in the head tales case we use okay this is the element the element we have in the head matches the property and the rest of the list matches the property so to summarize how we did precaution we have a one definition for the empty case I want to finish them for the head and Tails case if you remember how they what is called the cons list that immutable list in scholarworks that's kind of we are doing recursion in the structure of the list the empty list is our base case in the recursion and we have the help a case when we do something with the with they have and we record on the on the tail that is important because one problem with general recursion is lag is it's not guaranteed to terminate right if you just do a recursive call you don't three know if you go to terminate or not but if you know and even if you are more formal you can prove that you're doing record structure a precaution you know that your program will terminate that's kind of an important thing because otherwise we blow styles itself sorry so but we have these three pieces of code that looks similar I mean they do different stuff but they look pretty similar right so I mean once it's okay twice okay but right I want to refactor and make it more general so here there are three functions and I put colors to make it more evident well we are doing right we have in green the the empty case the case for an empty list in the case with the head on tails we do something with the head and we combine it the blue is a combination with with the result of the recursive call that I put in my room something because it is Scala we can ascribe that we can pass functions around we can make this call more generally basically we need one value for the empty case and one function that culminates the value with the recursive call right yeah I just put whatever I just say in the slide so this is kind of my proposal for the recursive recursion of our list you have a value for the empty case that we use here and a function that takes a name of the list of a value B that will be the result of the recursive call and yeah the list and returns a B right Z is the body for the empty list and basically we have a function that takes an element and the result of the recursive call and I'm missing a parenthesis here do you agree with this okay except the location of the lease parameter this function designer - did reminds you something exactly alright so we're kind of derived or own fall right you know the retail version of this talk was in Haskell mmm I'm not an actor of all in Haskell obviously but I write everything and then I wrote this discord in the cumulative this code in Haskell and I went today like the standard library of Haskell I look at the definition of fall and it was exactly that so it's kind of we were right we it was it was just step of just a generalization of some of the steps getting something generic of that and basically we have fall there is one little detail but yeah sadly how we write it basically for righties it's not that recursive because you had to apply a function after doing the recursive call you have to gather resolved first so you cannot really do a take all of the mutation of that and then able to be proved wrong on that well yeah usually so if you like I'm from in formally defined form i know i but one of the things i came up to my head is like given a function that combines an element with accumulation and an initial value start with the initial value traverse the list backwards because we go in fall right from the right apply the function to build a single result the only with a deflation of fault is kind of i tried to make create some explanation that based on what I know at the time the kind of important thing is like the result is basically this you have a list of a 1 a 2 a n and the result of the form is basically putting all this together oh yeah again this is no time because him so far so good we create our own right fall for list mmm what about other data types we are really useful for right or less for this doesn't make sense to fault other types we're going to do it basically we were to start doing the same kind of exercise we did for list but let's try we have a binary tree I just make up a binary tree we have a branch that takes two trees I create a new tree and the leaf that how about you we go to the ripe or own fault for that time also let's see about what happened with that either option there are not least the demon they're all demon recursive data types that grow there are so like a fixed number of elements but say we stick up for that I'm basically by repeating the same thing we do we need to figure out how to let's try to do the same exercise let's get the sum of all the elements of a tree if we do the same as we did for a list where we put here you do pattern match and least we do pattern match on the empty list and the cons here what we have yeah basically your data type has only to go so that we have the branch and the leaf so we're the bottom match orbit we can be either a branch or a leaf we're at the bottom edge from that so we have a case for the leaf with an element and the case for a branch with the left tree and the right tree if you get that if you want to get this son let's say the simple case that we put on the leaf hmm yeah exactly basically if you know that the tree has integers this a is an integer we can just return that in the case of the list please have any value so we just return zero a little more dressing while we put the branch yeah we basically we do we do a recursive call on the left branch and we do a recursive call in the right branch and basically we sum together those two results yeah that's when we get the sum of the tree we're not going to do for the properties but let's write the same thing with the with it's a string again we do pattern matching with the branch and the leaf what we put in the leaf this is yet a two string because even this one we are using generics if you have in and here here with the yeah the recursive call of the string of the left side concatenated with a casa call of three on the right side cool yeah that will allow us give us a tree I'll return a whole string coordinating everything so if we do the same exercise we take those two functions sum of a tree and the string of the tree we generalize it and basically we need a function that takes two results of recursive calls and combine it into one we need a function that takes value from the tree returns one value that compares basically the value in the tree into something we want to use the array with this generalization like it you want to improve it I just write it based on what we already have I try to refactor generalize and get this but now it gets interesting right let's compare the two things together and we try to get to what is really a fault so we have the list that basically is accounts of a head and the rest of the list basically basically prepares an element into a list and we catch the case of the empty list actually if you were to two Scala is object nothing but just for the sake of making things a little more consistent let me use nil a so this is our basically type constructors and our recursion or fold it goes takes a function that takes an element and a result and returns a result or and also we have a function value for the empty case that we saw for the gate case and then without with those two functions we fall the list in get a bit final result the interesting thing is if you see if you take the initial list that is one two three we if you use this list in the the Scala this is the same but this is kind of easier to write we have the cons one cons to cons free and the empty and if we apply default we get this F of 1 and F of 2 and F of 3 and theta and Z there is some kind of similar structure there right and if you see if we go to trees we see something similar or tree was either a branch of two trees or an or a leaf with a value and the recursion or fault recursion of the tree was something that combines two results in the world result or takes value from a leaf or returns a result so again if we have our tree written like this like a branch branch leaf leaf and leave and we followed over it we get F of F of G 1 and G 1 2 G on 3 and then that is again a similarity of the data type and how the functions get applied so that's basically what fog does replace data type constructors if you think of the data type type constructors as a functions for replace that with the French as you give that's why that's why here in the case of the tree you have an F and G and you replace branch with F and leave with G in the in the list you replace cons with an F and Neil with a Z really to see more things but it's kind of the most important point of a of the talk fault really what you get with folding is replacing the data constructors with your the functions you provide and that's really how it works how you would think four different times so since we are here and now that you know what we are doing I want somebody who'd some who tell me they going to tell me designer to rough the fault of option [Music] we have basically two cases one of known that doesn't have any input value so here is a very similar case as the list right here we just need a function that takes one by new converts to our result so here known will get a B and some will get an A and we need a function that from an A gives you a B we can do the same here if you think these functions here we need them like a new letter suppose that we solve this are the type of the result these are basically mmm you have a constructor that basically takes one type a type of a and you need a return basically if you think like instructors has functions here you have a function that takes an A our returns the left of a B and here you have a question at X a B or it was the right of a B and the way we were doing false based on the Constructors we need to replace this with a function that takes a name I give us our result and here we need to replace right with the function that takes a B now returns our results that's how they the kind of type replacement works based on what we saw this what I wrote right in the case of option we have a value of type B for the case known function that takes in a or returns a B for the case of some and all that the whole thing becomes a be the same thing 4/4 or neither we have a Tex ABC we have a function that takes an a it turns the C for the left case and a function that takes a be a little sassy for the right case and everything with also see sorry so basically this we wrote this based on what we saw and what we're trying to do and actually after writing this I went to the Scala documentation and basically if you see this is that the sign that yourself alt on option on the fault on either here if you see here this missing the the actual option you have to convert because it's actually here in the dot it would our value dot four and you give these two functions same year so we kind of we derive based on what we were doing we derive the signatures and it gives you things that were already there we're kind of the right track [Music] so finally after all this what is really a for what is why is colorful fall really transform the input into something else following the structure of the data type because all the function we give follow the kind of the inputs and outputs of the other type we create and you will sit mentioning the technicality to cut a morphisms cut a morphism other generalization of a fall that comes basically the world kata means don't world or according to basically you is a collapse you have a whole structure you collapse into a single value it's kind of a shock there is a marvelous explanation in category theory for all this but this is lines narutimate asa are going to do it what we are going to see a little I'm going to try to explain because in my case I I think it I not even get the total explanation but I will see how it shows just a little how are you doing so far questions complains tomatoes with something cool once ago yeah that's does this light is just here as a kind of a mmm never a joke but this is kind of get hairy will I I try to explain but basically got a morphism are the channel a civilization of the form in functional programming cat amorphous the constructs the data structure in with a net algebra with this underlying funter that all this what the hell that means okay this is a very solution of a fault we the constructor part we get it because we have all the pieces we collapse into one value but then now comes the will stuff the F algebra you know this is a tricky thing you start reading stuff or especially at Haskell man whatever people keep saying algebra and I don't know does anybody have a good explanation for an algebra yeah I try to I try to get something good I couldn't really find basically because everything I think it comes from abstract mathematics and everything but when it's a good algebra is when you have combination of stuff you have rules to combine things right here or if you are talking about recursive types or constructors tell us the rules of how to build stuff basically you're saying for all if you want to create lists you either have an empty list or you combine a value with a another list if you have a tree you either have a leaf or you have two trees and I tell you how to combine that's that's where I got the idea of constructors because this you have different ways of combine stuff to great new stuff start with salvage stuff yeah and then on the lion filter do you know what is font or function is mission a lot because it is basically one of the basic stuff was group of category theory but in Premiere improving language means just means something with the map function in category theory means something that allows you to move from one category to another but in programming we are not going from one category to another you have we have talked it about code what happen is then it comes another word strange word that is in the font or every and some functional products about a folder is actually saying in the founder is trying to trick you into thinking that is talking about genetic factors but it's no there and the Fantas that means factors that move from one category to the same category because we are still talking about code and basically what it really means a filter is data type constructor because even if you have another type of structure you're creating new objects you can't really derive a generic a map for that so that's why but this is all category theories that's why they say contours and basically because a function has map and to have a map he needs a parameter right we have the least the least a generic basically if you look into Scala anything that has a type parameter like generic as as Java is a isn't and in the filter and you have a map function and because we are using type constructors we have the underlying front row that's a lot of food stuff and the way those category terrorists no have to say about forth is like okay you have a filter that creates a type basically this is the I don't know the the three core structure that x2 trees are returns a new tree or the function that the constructor that takes a list with a value or returns a new list right and this is the our case the I think when you're working in on the list and you take the result of operating in to list or rito-san a new result or combining the two elements the two results of working on the tree I'll return a final result of the combination there are some I haven't seen it really yeah do I have to be honest but the whole point of that is like this arrow this combination of powers are unique so very data type there is one form that is unique there's a unique form this one way there is only one way to replace that credit mentions in F in F is called the initial algebra okay we go to that initial algebra is in this case is the algebra that creates all the other types right we have basically again is a very complicated way I'm from our way to say that's how you describe your data types with the start of the three yes okay you get two trees put it together again another tree or we we have one value and put that and with a leaf and you get a tree again that's the initial algebra and then what is saying is the fault is the unique way to go from that initial algebra and any other algebra replace the constructions with the functions in the algebra and finally that means that fall corresponds to the definitions of recursion of structural recursion over the type but going here basically what we are saying the that fall is the unique way to go from here to here that's a whole theoretical explanation of saying there is only one way to go from here to here here again this will be the initial algebra because a combination of type of structures this is a another algebra Burgas is a combination of other functions do you guys get lost I don't blame you I almost get lost okay this is kind of stepping boy this is a way to basically make these things a little less scary because there's a lot of very interesting results from this because obviously those category theories are not happy with only one level of abstraction so there is a way you have the initial algebra that describe how you create the other types but then that's so you can't generalize over that sorry you have different except every we see here every other type constructor defines an algebra but also if you extract about that you have one initial algebra that generates other type of Gibran's that's kind of too much for me but since you know how to fall algebras I know there are unique you have this algebra that abstract over any types and you know how to fold that and the result that means like you have only one fold for any kind of other type we only want piece of code you can follow our list of our trees our any other thing you can describe in an algebra and not actually what is called recursion schemes if you go this a library now called Matushka that uses all the kind of stuff to create genetic code it's interesting I mean right now I don't know how it really how much how much practicalities but it's really thick because is with only one piece of code you are kind of really ready to tackle any kind of data types I mean there is one just one way - I don't know - transform like you you're doing false but if you want together I don't know yeah the sum of all elements of other type you can have a son that works either with trees with lease you can't have a serializing code that it doesn't depend on the type you're passing just works on any any type you don't need to write again realization code if you have a new data type if you have a new type of customer whatever you don't need to write new sir realization code and that's kind of an interesting promise but yeah this is just just joking around with category theory actually there's a paper that described a lot of stuff that is mentioned it's called this was another funniest name I heard it's called functional programming with the lessons bananas envelopes and Barbara Dwyer I try to rate that read that paper I couldn't get anything until yeah until as I started learning category theory now stuff I took a course about genetic programming and that's where ice it doesn't make any sense to me yet but at least I can understand what they are talking about so I mean a is not critical but it's a interesting thing to to know when where things could go with a interesting results combining with with practical libraries we got get weight even way better code that we do now obviously we will write excellent code everybody does it right but I mean there is even more things more interesting things to do so next party when somebody asked about you about false you can say after all unfold this you're it originated by the unique Alma Murphy's that exists between the initial algebra any other observer that's the problem I I can guarantee that you will be the star of the party with that well it's like it has some disclaimers anyway okay so far so good don't worry about the categories most mostly as a joke in the talk but yeah this a couple of things interesting this kind of interesting to try using the repo I don't have it right now but we can do it mentally or if you have a computer you can do it okay you have the list one two three what happens if we form a passing Neal basically the cons operator yeah yeah I mean you can see it even if you remember that when you have a replace calls with F and Z the Neil with Z basically replace deal with Neil and cons with cons you get the same list that's kind of useful I don't know but based on that let's do an extra step we got this function that I call F F F F F F that takes a list falls over the list gives a for the Neil case gives Neil's again but when I get to the gauls case I had I have the hell the head I have the tails but I've when I'm combining I put f of X and combine it with the rest yeah that's actually this function is map if you try with this multiply by 2 the result is you get the first element multiplied by 2 let's take on element multiplied by 2 and the third element multiplied by 2 that means once you have 4 right you can do a lot of operations based on that I mean you can read Matt yeah flat map I think I don't remember exactly but even in functional programming in Scala the book one of the exercises is derive a lot of the normal collection functions using only four right we go for this basically one of the fundamental operations of at least over data structures yeah that's kind of the point of the tag don't usually you won't get focusing on fault is from least for this a lot more than just least yeah if you ask category theories about this oh did you oh yeah for this is a combination of map it's a combination of a cuttlefish with the type fonder and once you get that try two dishes that basically means the type font er is the photo that creates the the least that the photo like ratio type so basically is a function applying into the Constructors but yeah is so yeah that's what I have to say thank you for being here her question complains I usually ramble about many things in Twitter or if a question send it you can send it in an email yeah feel free to ask questions to play it or whatever thank you thank you questions yeah all right so this one same page here right so all right so so we we have we have our initial algebra and we have Yes Mother I was right and we had to the pasture hunters what this means yeah this kind of is the transformation of this algebra into this algebra and that is kind of a little not easy to visualize I don't know the check the details but if you follow this Vicki this is the this means this is kind of the algebra of Falls it's really weird and it's a transformation between this font or of types into another font or of results actually this part is not really used practically because a fold is just a combination of these that's kind of that's wise we're I mean you need in category theory everything is very sound okay make the diagrams commute means basically you have usually good for this square and this the direction of the arrows so you can say okay this part is a given to this part and this part is how if this part is kind of the equivalent of how you do it with recursion and this part is how we do it with the form that's why but you don't know get done go grab on that I wanted to look at the details of that the goal of our concern here is just belong and school yeah I think the point is this part is it's kind of is more difficult to generalize and this kind you can write like a generic code for that that's why you have one for function but yeah I mean somebody's even harder for me I can I promise I can check the the the the the material phenomena from I get that and get back the exact answer for that but right now is kind of I forgot about that yeah I'm wondering about about four left so you put this on Fulbright because in business this pattern of replaced exactly and yeah this we I forgot that and it's a very interesting question I don't have anything to type but do you remember the signature of fall left [Music] there is one thing basically the main question is what happened with four left because we are saying false matches for match the shape the of the Constructors replacing constructor with functions but for left it looks like it works at least we have the the empty case but the function is kind of backwards and basically also we should say that there's only one form for each other type everything no but the list has to the recent racing edition for that would you like a weight yeah or I can use I know I can type something in there because this is a really dressing problem let's go backwards right we let's find out the senator of fall left and the see where our bottom means no yeah yeah cool okay yeah all left for left does anybody remember the signature of this yeah let's assume let me write in the way we have a of the elements of the list B we have a an empty case site B now is the difference is here right you had the F with that is a function in front right we have a function a b2b right but in fault left we have a function B and a to be right so far so good cool I'll say okay so if we we already say that fall replaced constructions with functions so what will be the constructors of this list we have this one this one is easy he's the same as as the other list is new no the same nil but something for the empty list the same kind of this something to say that it's not disabled Neal saline Neal one well we did they are they are constructor we have in the ER least we have cons that takes in a and a list right and this is kind of that what matches that here or constructor how it will look like yeah something that takes a list and the nay and returns a new list okay Oh writing is horrible but if you see in something that takes an empty list or some list and start adding elements at the end it's kind of the normal list is the cons list it's a prepared list the functional the most kind of popular list using a firebombing but this one is kind of four at least but goes to the opposite side goes with a pen at the end and that's kind of a will and actually that look it after reading all this i did the same the same a concise and say that lease exists whatever i just i type it and it turns out this one is called as not least basic because this is the reverse of course and it was in exist and it was something they didn't it was kind of our enforcing way of we are kind of the right track basically based on we did reverse the right way we know that fall replaced constructors so we figure out how they construct those will be we found out that is something that really already been invented obviously what happen is really if you have least one two three is really a key one into either consoles nuke is still a list of elements with repair maintains the sequence what really just a matter of like order an effective execution of some operations so basically you can say probably you can say that the two lists are isomorphic isomorphic but basically they're this kind of this have the same value same order everything just like they have a different structure that's why for at least it doesn't really matter and basically we use for word for performance it works better even if you go to Scala the definition of phone right uses fall left the star reverse and uses for list and for left is doing is using a while but it's just all for performance recent formally that's kind of their what happened but this is a really good question what happened with the for life and why when I started reading about this he said yeah but for this doesn't make any sense so I stopped when I did this iPhone oh that was really funny you have another question right are you going to good it you have a question right I mean my memory of this is that on the backside of the initial algebra a secret of it is that that in half that was actually invertible and so the way that you define fold on the bottom is by Ferdinand ik going around the top and then at football is like this perhaps map it makes a lot of sense I mean probably I don't get to repeat everything for you should have a give you a microphone actually you should do that yeah yeah you get okay get the mic and I'll do that oh yeah but you can just but the secret are there there's the business part of it right now and so this is this diagram here's the recursive definition where my fold is going around the other way and like this is math and like I do going the other way killed off one layer about true yeah therefore this yeah you can reverse this basically you to get this you travel this I get the result yeah yeah yeah and this is map true yeah excellent thank you I love that having people that knows more than me cool more questions example you have one person called every time you occurs in the tree exactly or two energy pulse is there a library installer that can capture those I think he's in matryoshka haven't read it and I will go in I had some very smallest foundation of that but it was really weird I mean I don't know just totally understand the the dandelion theory to the chattering of my professor but yeah and that's kind of the trick the whole trick about that I'm going to use this again here again it goes back to algebras it keeps digging into algebras basically you serve for at least you have nil or cons that take this a list constitutes an element and a list right we have a trees for binary trees you have leaf that takes an A and takes or the branch that takes two trees right let's say I don't know another will data structure you want to add well maybe two three trees well we can have a leaf with a value a two branch with two trees I don't know that is the three branch that takes one two and three that's this is going to get weird so let's say this one let's forget about the names I look about the look the parameters this one is something that takes no parameters another one that takes value and the list this one is either of those this one takes a value or two trees and this one takes either evalu to trees or three trees so basically the elements here are nothing values think things are recursive because here we're seeing a list is again what we're building so it's a recursion a recursive type here again we have values and putting together to the things running here we have value two things on three things going together I don't know the whole point of saying algebra of types algebraic data types is the way you can combine it combine them and in category theory alternative alternative of stuff is called basically some because basic ho-ho golf is algebra and the definition of how categories go with algebra but basically when we have one thing or the other we call it sum when we have two things put together we can think this is a kind of a topo and in category theory at Apple is represented by a product [Music] values we need something to hold values because values are really not we are dealing we are kind of focusing on re recursive types values we are going to use a kind of a constant to hold them and a recursion once that get move into a category let's put that this is recursion but here what I'm going to say is here we're building trees so if really am building drinks on here I need trees basically this is an identity because I have a tree and I apply a function I get the tree again so it's identity and what else do I need I think so far I have almost everything the empty case is represented with one because is just a kind of a genetic object doesn't have anybody doesn't have anything so that's that's some kind of very higher view and I'm just kind of skimming over everything but basically with this kind of I'm creating an algebra to describe any other type so with this the list and if you start seeing things it will be kind of almost familiar at least is either nothing or a combination of an element that's what Kay with another list and identity tree is either an element or the combination of two trees so I read this and again this tree will be either a value or two branches two identities or again three identities so this is a way to describe any kind of recursive data type with this algebra and that means these are type of structures in a kind of way so I define a fall for this kind of constructors so suppose I want to get the sum I need to define how the sound will work for that and how the sound will work for that how we work for that and this will be kind of a recursive call so if we do the pattern matching for the sum in the case of the nothing it will return 0 in the case of in the case of the constant the constant is often a value I will just return the value in the case of the product I will just return the product is the product of two things and let's say the length on the right I will just return the sum of the rest of the right and missing something in the case of in the case of plus again I need to do kind of pattern matching if I have the left side of the plus I will just return the left side and if I have the right side or just return the right side and this one is kind of my genetic fault for this if I have a list if I apply this basically or least least one two three we get translated into welcome back combining things basically okay the one with K of 2 with until using top of but this is the kind of multiplication and K of 3 and the last one that is one so using these we translate that they have zero this is a multiplication proud so it's a with some 4k we have yeah we extract the value we have three same thing okay - we have extract the value have two and again this one so basically in F I can because I can describe the tree with the same kind of algebraic constructors I can use exactly the same rules for the tree so that's and that can be that can be writing in written in code that there's kind of the basic of recursion schemes they have actually have one experimental library that tries to do this in a weird way is not really finished it works it does really finish because I have some places that have to use a ICAST because the way I'd like to write its callate system saying okay you're crazy this is any I have this um no I know that is an int but yeah I mean that's why I'm not totally happy with that but it's an interesting experiment and then that's I don't know for me this is this is amazing it's a really good convoluted but on the other hand you can be see if you write a macro that looks at the RET of the constructor you can write this automatically and you have that translation your fault we work or even without the macros suppose you have a new data type and you basically say okay my data type in algebra is described like like this and it will work for the fault you don't have to write the code again well that's agreeable for only one question sorry about that yeah yeah yeah yeah but think you have to basically the trick is looking because I have looked into matreshka and I understand half of that I'm doing something with this with my professor I'm trying to basic that's right he has a Haskell code that this automatically I just I went crazy I said let me try to do that in Scala so that's why where I get is any and you need to really I know I I discover that I don't know enough Scala to do that I trying and trying but and and he saw me oh I told him yeah at least this library looks similar to what we are doing and he look into it and say yeah this one we're doing the trick is this one it's a recursive call here I put it identity but it's basically it's called fix because there is the recursive call on types is look at the fixed type and you will start this is kind of the basic of matryoshka and in the blazes banana pramik Willis's banana assemble open bar my again it goes kind of nothing does the same thing but it grows in this direction that's I don't know if you have a direct translation I can point you also to to buy paper that grows through this all these you many more question on there good really yeah that simple right seemingly there she's Haskell yeah a little business just work is excessive yeah [Music] yeah I think that the problem with the the problem is Haskell will list it's like they're actually lying to you and there are lists or streams because there is no infinite list for money use either a list or a stream if you have infinite elements it's not the least it's a stream but yeah to be safe you because you never know with this infinite or not is safer to use for right because it always replace everything and because of laziness laziness you don't care if you never finishes just take the first ten elements and the rest is just generators of work but yeah it's color because only Starfy need finished list you release if you put four from performance to one side there yeah equivalent and basically because you can go from a cons list to us not least go back a form with just one transformation so really is equivalent yeah it's only one there except I say the versus Street since you applied the brake it's folded over keep it there right the problem is and that's kind of a tricky part you don't you never fall down a stream once well let me because the stream is a generator yeah one second let me go back actually a stream is actually a none fault you start from you got usually you do the opposite stream actually is starting from a set of values and generate an infinite stream of values so but actually you come for that so that's interesting but it's a little tricky yeah but actually I think yeah there's actually a scale is kind of just you don't care because you can always have the infinite list around and take something even if you fold over everything you take the the first ten elements that's why if you fall the other way around if you start from the end and go to the beginning it will never end you do fall left will not work I mean you get stuck above it in the list that reminds me about four thousand fold actually there is waste the good thing is all these explanations are ready to apply results this kind of things that are called deforestation when you combine either for the map or fog falls and that combines you do only one fault it tells you how to go from a combination of faults and for maps into one only one form without generating all the extra steps and you have a fault that takes a structure and collapse it you have a known fault that is the reverse operation that takes a set of values and generates in case stream and actually it's a lot of elements and then you have something that's called if I regard correctly hilar morphism because you have the cat amorphous in that is the fall they earn a morphism that is the arm form and you something is called the high Lama facilities combination of both because of fortune on everything you have something that from one value expand that and the fault collapses that but the fusion of those two allows you to do the operation without generating all the intermediate values and that's kind of what some of the decisions take advantage of that yeah I think he's I forgot about that there was there were some examples about that I think the kind of the there is one search I Gordon I think I don't remember it was quicksort or whatever that you can see as like a highly Murphy's saying like you take a list you generate the search three of the list and then you collapse searching on the tree because it is a combination of unfold and a fourth you can accommodate that without generate basically you do the same we don't generate in the tree this kind of horror like a like quicksort on one of those such a nagger it works it conceptually yeah questions more questions okay cool thank you hope you have fun [Applause] [Music]