Unzipping Immutability

scala.bythebay.io: Nick Stanchenko, Unzipping Immutability

Recording: scala.bythebay.io: Nick Stanchenko, Unzipping Immutability

and we'll be talking about immutability so thanks a lot for coming I know this is the last talk of the day aside from the panel and I know you guys are pretty exhausted but you know what you made the right choice well mostly just look at some hopefully pretty pictures so it'll be like walk in the park so I'd like to start with the couple of words about my employer design which is the biggest word on the slide so we are a fraud prevention company based in Portugal and the US and one other countries and everyday we are processing several billion of dollars worth of financial transactions to identify fraudulent patterns using big data and machine learning and Scala so if any of that sounds interesting to you please get in touch with me so aside from that this slide that you see here is the most important slide you will see in this talk because the only slide that I've got so the talk will be entirely life coded this means that if you are quite far from the from the screen I advise you to move a bit closer so that you can see well also it means that I would prefer to take questions in the middle rather than at the end because it will be really hard for me to backtrack so if you guys want to ask me something or you want me to run some command and see the output just say so I will repeat your question on the mic for it together on the recording and finally this link that you have to on the on the slide you can take a picture of that basically there you will find all the materials for the talk including links to extra resources like for reading and stuff and you will also have a full transcript of the talk so you will be able to read it and follow on and even run the same command the same commands that I am going to run so we then in mind let me ask you who has never used immutable data structures or has no understanding of what it is one person great so let me see is this okay is that big enough so I think we'll start with a small motivating example just to remind you how it is to work with mutable data structures and then we'll proceed to the mutant ones and we'll see how that works so I'm just starting yeah yes the recording is rolling so here I'm starting the ammonite shell which some of you might be familiar with I think this is the best out of your cells that we have in Scala so let's let's start with a simple example like an array of two numbers one and two and let's say we want to create another array that has this numbers two and two so with mutable data structures the way to go about it is you just say 2 2 equals 1/2 and then we'll say 2 to the first element we change it to 2 so that's great we have a new array that has 2 and 2 but what we just did is we completely ruined the first array that we had see it says 1 2 but it's actually 2 2 and this is one of the problems that you get into with mutable data structures because when you start mutating them it's kind of hard to track where the changes are coming from especially if it's from different threads and basically you can just easily ruin the data that some thread is holding to by mutating it in another thread and of course the correct way to do this is if you want for example 3 2 you can say 1 2 that clone and then you can modify it all you want and it will not affect the original array so we place this kind of simpler so Scala lists are immutable which means that you can't do this kind of in place mutation that we did but this brains the question is it actually copying the entire data structure every time we make change because that wouldn't really be efficient and to kind of get a hands-on approach to this and see what is happening behind the scenes in my spare time I made a tool that allows us to visualize these data structures and see them in action so let's start with creating a simple list like list of 1 2 3 and we'll say render list and here on the right I'm just having I just have an image viewer that will display a file that I'll be updating throughout the talk and this is a basic representation of our list so you can see that list consists of a few cells which are historical called con cells so the first cell holds the number 1 and the reference to the next cell and the next cell has the number 2 and the reference to the Excel and then finally the last cell points to the Neal which is the empty list so this is pretty straightforward I'm pretty sure most people are familiar with this one thing that we can try to do is we can say with two equals let's say we pretend the number 0 to our list and then we want to see both lists and list 2 and this is the kind of thing that we get so what we can see here is that list you just added one more cell but it's reusing the entire structure from the previous list so we didn't have to copy anything anything we just shared it so and this allows us to use memory in a more efficient way and really the reason this works is exactly because list is immutable because if the list was mutable we could just mutate this blue part and the green list would be screwed up we would modify the contents of the green list so the fact that the data structures can't be mutated leads us to do these optimizations where we can share entire pieces of these data structures and this is really the crucial trick to immutable data structures so another thing that we can do it very easily is remove elements from the top of the waist or from the front of the list so you see if you want to create a narrow list that just has the rest of this list with least detail again it will share what is already there so we didn't have to to put any effort into this and also you will notice that adding elements and removing elements from the head of the list is a constant time operation because we just have to create one cell or we have to dereference one pointer so this is great actually one thing that I found using this visualization tool is that some operations on Scylla collections don't do exactly what you expect so let me elaborate imagine that we wanted to do the same thing we did with the array which is remove the first element and replace it with an arrow element so one way to do this would be to do it like so so we'll say to concatenate with less detail and yet another way to do it is to say list updated at index zero and replace it with element 2 which is supposedly the same thing at least they yield the same results right but actually if you look at them you will find that I'll throw a list in the mix as well you will find that the actual creation is very different so with this tree we use list detail and we are in a head element and with updated it just created a whole new list so this operation is actually not optimized for lists instead of just keeping the part of the list that is unchanged it rebuilds the whole list so this is one of the things that I found well anyway lists are pretty cool if you want to add elements or remove elements from the front but if you want to add things to the back things get really bad so let's look at least ten least gloves for what happens here is that to Adam and one to the end of the list we have to build an entirely new list why is that because the final cell of the list that we had is already pointing to the empty list and we can't change it so we can't point it to our new element thus we have to rebuild the entire thing and just as a curiosity I made some simple animations so this is appending elements to the front of the list and it's working pretty smooth we are not wasting any memory and then if we look at appending things at the end it looks more like this so every time the append happens we have to create an entirely new list which is not great so one day is structured that solves this problem is called the Q and the Q is meant for adding things on both sides so let's go ahead and create a Q now this queue that exists in Schuyler dot collection that immutable is called the bankers queue and basically what it is it's a class with two lists one list for the front of the queue and one list for the back of the queue this way you can put things on the front in constant time and you can put things on the back in constant time so for example if we have Q and Q plus four so this is a bit hard to grasp because of all the arrows that are intersecting each other but basically Q plus four is reusing the same front list which is one two three and it has another list for the back of the queue which has the number four and if we go further and we add one more element you will see that the list that represents the back of the queue is actually reversed so it has first number five and then nine before does anyone know why that is sorry yeah exactly yes so it's so that attending elements is efficient now the question is it's all well and good we can add elements on both sides but what about removing elements in particular what happens if we remove elements from the front and the front list is empty so I have this animation that will guide us through this process so we start with the queue with number is one two three and we all do this we'll add two numbers to the end so five and four and then we'll remove two numbers from the front so let's add two more six and seven now this is the interesting part so we can remove one element three and now we are about to remove an element and there is none so basically what the key will do is it will take the back list and it will reverse it and put in the front and this is obviously one operation that is very efficient because to rebuild the entire list you need to spend at least an operations where and is the number of things in the list but luckily if your usage pattern for the queue is that you keep adding elements to one side and remove it from the other side and you average the complexity of all operations on average you actually good that you actually get a pretty good performance so it works now one problem with the with the queue is that it's not really that easy to get an element by index so if you want to go somewhere in the middle of a queue let's say at an element number five you would have to traverse the queue from the beginning or from the end and you have to go through all the links to get to the element that you want and obviously queue is not a data structure that you want to use if you want to access by index and the way this is solved in in Scala is with the structure called vector that I think is also shared in with closure so closure has pretty much the same type of structure and let's go ahead and create a vector and see how it looks so I'll just say 1 to 10 vector and render vector so this Factory is pretty basic it's not interesting yet what it's doing it's using an array but it doesn't explode it expose it to the outside so you can't actually mutate that array so it still provides you with the immutable interface and if we were to add an element to this vector again nothing exciting will happen basically what it does it just duplicate the entire array so clearly that's that's not something that we wanted to see but things get more interesting where you have bigger vectors so and by bigger I mean more than 32 elements because these up these arrays have 32 elements so if we say 1 2 42 vector this is just big enough to to become interesting so what you will see here is that it's using an array of arrays and that way you can represent at most 1024 elements and you will notice that there are some cells which are empty at the end basically those are additional layers so you can have arrays of arrays of arrays or arrays of arrays of 4s and so on and essentially this is enough to hold as many elements as you can hold in a java collection because the size of a collection is an int so with 6 or 7 layers that's enough for all reasonable purposes and the thing is that to get to an element at any particular index you just have to do at most six points or two references because you have to go through six layers so for all intents and purposes this is constant time because it's at most six so that's really great and another thing is obviously since this vector this vector E is big enough to have two layers if we add an element 8 plus 1000 for example we are now able to share in blocks of 32 and if you have three layers you're eight to share in blocks of 100 1,024 so the bigger the victories the more you can share and we can save the memory in that way so that's vectoring the non show and that is also the conclusion of the first part so this would be a very good moment to ask questions if you have any about data structures yes that's a very good question yes so I am abusing method that exists on the JVM which allows you to get an identity from the object and that way I can determine that the same object is the same object and I assured them on the graphic yes so that's completely automatic and that way you can explore the sharing part on your own and see what is sharing and what isn't yes that's another very good question so I'm using a I mean as much as I preferred this to look like magic to you I will I will tell you so I'm using a library that is called source code and it allows you to capture the source of the argument that you're accepting in your method and that just works automatically except when it doesn't so one thing that I that I try really hard not to do by accident is this sort of thing if you use operators that end with : which are actually applied on the right argument that messes up the positions because of the sugar ring and basically this doesn't work so that's a known downside of that library there's an open bug for that hopefully when we have scout meta I think Eugene is in this room when we have scholar meta obvious hopefully we'll have a reliable way to extract the source of an expression to here but yeah more questions alright so in a second part I wanted to talk a bit more but I'm more a bit more about the main object so data structures are great but most of the time we can just reuse what is already existing but we really want to build our own domain models based on our business logic and and whatnot and if we choose to implement them in an immutable way there is a certain effort we have to put in it if we want to modify these objects and I will illustrate in a bit so imagine we have a simple case class like like this employee class it has a name which is a string and he has a salary which is a long in some currency and we can use again we can use my library to to take a look at this employee so again this is an employee here we have the stream Michael which is the name and we here we have 4,000 which is the salary now if this was our domain model I think one pretty common or not depending on your business operation that we would need to do is give the employee a raise so the way these girls in Scala because we have the compliment method defined on case classes we would say raised is employee dot copy salary equals employee not salary plus 10 so that's a small raise and now if we render both the employee in the raised employee will see that they share the same name obviously and they have different salaries so that's great now we imagine we have an entire startup so I'll show it to you but let me just cheat a bit and remove a bit of boilerplate from civilization so let's say we have an entire startup and I just simply find the visualization just to remove some visual noise so we all know now how a list works right so I'll just say list and it will have a bunch of things inside but you know that it's a sequence of consoles just for the sake of simplicity so again in this startup we have the employee Michael which is now the founder of this startup and we have the name of the startup and we have a team of four employees that work under Michael and now we imagine we wanted to do the same thing which is to to give a raise to the founder of the startup so we would say raise founder equals startup dot copy founder equals startup dot founder dot copy salary equals startup the founder the salary plus ten I hope that's correct yeah well you see the problem right that's clearly not the way to go about it and a concept that was invented in functional programming just to deal with this particular situation of updating nested immutable data is called the once so in a natural lens is something that focuses on a part of the data and you can use the lens to update that particular part of the data and while I'm showing it like this but we'll see in a few in a few minutes that it can actually be different pieces of data fragmented across the data structure but let's keep it simple for now so I'll use this library called Monaco which is self advertised as an optics library for skull and it it includes things like prisms and traversals so we'll use that to create a couple of lenses and then I'll show them and explain how they work so we'll have a severally celery lens which is a lens from an employee to their celery and we all have a name lens which is a lens from an employee to their name now obviously there has to be some way to to visualize it and the way that I came up with this like this so we'll say render the focus of the lens called salary lens and we'll focus it on the employee and it looks like this so it kind of highlights the celery part of the employee and the same way if we replace it with the name lands it focuses on the name so so far it's not very obvious how this is useful of course we can showcase the API that it provides so we can say celery lens modify whatever was there plus ten and apply to the employee and it gives us a result 37 which is Michael with the hire celery and again if we show this will have basically the same thing that we achieved with the copy method but with much more boilerplate but the crucial thing about lenses is that you can compose them so imagine if we have another ones which is a founder lens and it's a lens from a start-up to a founder of the startup then we can compose the ones the founder lens and the celery lens to form a lens from the startup to the celery of the startup and it goes like this so founders salary lands equals founder lens compose lands celery lens right so this is like dominos you have pieces of Domino's that have the same number and you can kind of concatenate them and it just works so if we render lens focus of founders Lance and let's say startup so inside into our startup it focuses just on one thing the most important thing the celery of the founder and of course we can use this lens to modify the celery much like we did before so we can say modify whatever was there plus ten of startup and it does the same thing so you know I told you that there was a problem with copy methods that it was very boilerplate e and then I just introduced a bunch of other things but actually this can be greatly simplified if you just want to update data and you don't want to go around creating lenses there is another library which is called quick lens and it's kind of operating with lenses but boiled down to the essentials so you would just say startup modify founder that's celery using whatever was there plus ten that's it so we don't need to create anything I really advise this library I think for working with case classes this is a lifesaver I mean this looks almost as concise as if we were using immutable data and in fact we can go even further so we can modify everything not just founders celebrate let's say the startup is having a good time we want to give everyone a raise we can say team page celery and this updates the celery of everyone now this is like going into entirely different dimension I mean this is not even this is not just concise this is very powerful and we can express things that are probably not as easy to express with mutable data so by using this Lance abstraction we can achieve a lot of things and everything that I wanted to show to you is that so far we've been focusing on the fields they're kind of essential part of the data like the fields that we have defined on the case classes but actually we can focus on literally anything inside latent so here's a another kind of optics that is called the traversal and it focuses on all bubbles in a string so let's say when I render lens focus of the wall traversal and what's a Michael so in Michaels name it focuses just on il and E because those are the vowels there and this is pretty powerful because then we can build a traversal that goes from a start up to fall walls in the founders name just like that so it's a founder foul glance traversal equals founder lens compose lands name lands compose traversal and then we can render this and it works great so from the interest started we focus just on the vowels in the in the father's name and we can use this traversal to do all kinds of funny things like you can say modify and just change all vowels to uppercase and here it is so that's pretty much the conclusion of the second part so if you have any questions about lenses traversals quick lens this would be a very good moment to ask yes yep yeah so so each is a kind of synthetic sugar that the library introduces and you can use it on option lists or basically any functor so if you have a list of things you can modify each element of the list so if you have a list of a and you provide a modification function from a to a it will be applied to every element of the list so in this case we had team dot each dot celery and team was a list of employees so it will basically modify the salary of each employee and the same thing you can modify things inside options so if the option is defined it will modify if it's not define it or not do anything yeah well quick glance has its own functor trait that it defined because the author didn't feel like bringing the entire scalzi or caste just for that and it's it has instances for scenario collections I think there are more interesting things going on there in quick glance i really suggest checking it out there is at which you can use for map keys so you can modify things at certain keys in the map there is a support for Co traits of case classes that I contributed where you can have if you have a trait with a field that is defined on the trade and case classes each of which defines that field you can modify that field on the tray and it will go through all the cases and modify accordingly there is support for what monaco calls prisons so prism is a lens that is only applicable to some types some subtypes of the type you're operating on so I'd say if you have a type animal that has cat and dog has subtypes something yet would only act on dogs and don't touch guess that would be a prism so in quick clients you can also say when you modify you can say when and certain subclass and it will only act on that sub question there is a lot of features that you can explore if you're just into you know just getting the job done I really suggest it but Monaco is also an excellent piece of engineering if you need some more abstraction I would be all for monocle actually the library that I have here for facilitate visualizing stuff use this monocle very happily so it's kind of dog fooding it's built on the principles that I explained in the talk more questions alright so for the final or almost final part I wanted to talk about recursive data structures so to to give you an example let's say our startup grew and now we have an entire company so it looks a bit like this we have the Acme Corp Michael is still in the lead but now we have several hierarchies of employees so we have Adam waiting two other guys and we have Bella waiting two other guys so the company has a hierarchy which is recursive data type because it's references itself so inside every department you would have a lead of the head of the department and you have sub departments which are here expressed with the hierarchy type so I can show you the definition of this so you have hierarchy which is which has an employee the weight of the department and then you have the team which is a list of hierarchies and then you have company which has a name and the hierarchy so one thing that that you can do with companies as obviously add new employees and if we were to add a new employee right about here at the very bottom right of this tree of hire of departments we could use lenses like we did before but it's not really that elegant and one two or data structure that was invented for this sort of thing for dealing with recursive data structures is called the zipper and first I will illustrate how this would work in terms of the API and then I will explain how it actually works inside so I wrote this very small zipper library and it's based in the paper from I think 97 it's pretty vanilla is just one file I think but it's already pretty powerful so we would just say zipper company hierarchy now this is where to type so then we can say move down right move down right insert right a new higher commit and that's it so this is called result 51 and if we render what was there before and you think you'll see that it did exactly what we aim to do so it went all the way to the far right and it added this guy Burt with very low salary so another thing that is great about zippers is that since we are working on recursive data we often want to express our recreation operations in a recursive way so one thing that you can do is actually write loops in a very straightforward manner so instead of saying move down write move down write move down right until you reach the end you can just say cycle try move down right and that basically gives the same results so it will continue going down right until it can't and then it will do the next operation so just to illustrate how zippers actually work I made a very simple three data structure so we are back to numbers I think this is a bit easier to grok so we have a tree that has number one and it has a bunch of children two three four and five which in turn has six and seven as children and we are going to use a zipper to go inside that tree and make modifications and we'll also see why it's actually called a zipper so what's great one and let's look at so as of now this is not very exciting basically it's just pointing to the tree and just like with lenses I did think here with highlighting so one thing that zipper has is called the focus and currently it's focused on the root of the tree because we just created it and zipper has three other fields which are the left siblings of the focus which is this first field then we have focus as I said and then we have the right siblings of the focus again currently there are none because we are focused on the root of the tree and then there is a possibly a link to the parent zipper and we'll see that in a few moments so again nothing is nothing interesting is happening we can of course use the zipper to perform modifications so you can just set the focus to a completely different three three and we can commit and we get a new tree because we just modified the the root of the tree but interesting things start to happen when we move down the zipper so if we were to visualize simple tree zipper and zipper move down left for example and bear with me there there is a lot of visual noise here but we'll cut it down just in a few moments so in green we have the first zipper that we had and it's still pointing to the root of the tree but now in red we have the second zipper which is pointing to the first leftmost child of the root which is exactly what we told it to do we tell it to go down left and it's also pointing to its parent zipper which is our previous zipper and as RIE siblings it has almost three four and five and just to help you see this I will remove the first zipper from the picture so again we have our tree in blue and we have the zipper in green which is focusing on number two and in right siblings we have three four five six seven I'll simplify this further by removing the tree so that we can just see the zipper so essentially this is a pretty straightforward data structure if we start moving right we'll see that now number three is in focus and number two is in the waste of flap siblings and numbers four and five are in the list of right siblings and since these are lists we can easily add elements of on top of them so that we can add elements on the left or on the right of the current focus so we can say for example insert left three of twenty-three let's say and here it appears and again since this is a list it's inverted so that we can add elements on the head very efficiently in the same way we can add things on the right so insert right so now it appears here we can of course replace the entire focus we can delete elements and then we move left or right wherever you desire anything that we can do is we can go all the way to the right so wine right I think that's what they call it there's Moses to the right most three which has the number five and now if we move down let's say I move down right so now we are just focusing on the children of the of that tree that had the number five so there are six and seven and let's say we insert some tree here so insert right three of let's say eight so it appears on the right siblings and now what happens when we move up and this is actually what gave the zipper its name basically what we are going to do is we have this current layer which has the left siblings the focus and the right siblings and we are just going to zip them together so we take left siblings the focus the right siblings we merge them and we update the layer of the tree so move up and now here we have 6 7 & 8 which were comprised of the yellowness that we have in the previous table and this way we can continue to go up the tree and it was if two layers back and eventually we end up with our original tree but with the new element inserted and that's why it's called the zipper and also you can guess that that commit operation that I demonstrated before it just goes all the way up and then it gives you the current focus which will be the root of the tree so this gives us the updated tree that has 6 7 and 8 and I have I think I have an animation of this yeah so on this one I have both zipper for a certain tree the same one actually and the tree and as the zipper is moving you can track the current focus both on the original tree and on the zipper and you can see how it kind of most very gracefully so this is the conclusion of the third part of the talk and if you have any questions about zippers this would be a great moment to ask them yes I guess yeah that would be fair so a zipper kind of has two properties that I really liked one property is that you can navigate and modify things and another property is that it actually gives you a focus in the tree so this can be used for various purposes like if you have some kind of interactive editor and you want to keep track of where in the tree you are and you want to keep that position to edit this is also a good data structure too to keep that position so you can kind of memorize where in the tree you are I think that's pretty unique quality of this data structure more questions on the efficiency of the zipper yeah so as I already mentioned the left siblings and the right siblings are lists so when you move left or move right it's basically taking an element from the head of the list putting it in the focus and putting the previous focus on top of the air list so moving left and right is constant time now when you go down a zipper you have to if you go down left you have to deconstruct the list into the focus and right siblings so that's also constant time if you go down right you have to deconstruct the list into the last element and in it of the list so that's a bit more expensive that's n operations going up the zipper not sure what the exact number is but basically you have to merge two lists which basically means that you need to rebuild the list from scratch so this will probably take as many steps as there are elements on the current layer so that's pretty much the complexity characteristics of the zipper well this one is actually a tree so so I can speak about a bit about this particular zipper implementation so it works basically on any I can show you the definition of simple tree for starters so I define it like so so it has X which is the data in the tree and then it has a list of children which is a list of tree and this particular zipper implementation happens to work with anything that has a single recursive field that is a list of the same class or if you add a bit more boilerplate it can be effect or any other collection but for this particular case class where you just have one field that is a list of the same case class it just works automatically so it uses shapeless to ought to derive all the necessary machinery and then it just works more questions all right so just to to wrap it up I thought I would share some visualizations that I made just for fun and to make it even better I thought I would do a small quiz where I would show you animations of adding lots of elements to a certain data structure and you have to guess which one it is so let's start with this one which is pretty obscure I would be very happy if someone guesses what it is let's see how it goes so the elements being added are powers of two for all cases and you just get to see how it grows and based on that you have to find out what which one it is the question is what is the data structure that you're seeing any guesses it looks like Alice right yeah but what sort of sequence I mean it can be a list a red black tree it can be anything no no it is a tree I give you that sorry no it's not a try nope nope yes it is the finger tree yes so this is one of the more obscure structures but there is a paper in it and you can find it in the materials for the talk I really advise it it's a really good read and this structure is just really beautiful I really like it so next one this one should be a simple guess sorry mmm nope what is the second one like sorry wait I think I sorry good you're right no I don't think so yes it is a hashmap yeah you can see lots of all it's kind of very flat but for some elements where you get the same prefix of the hash they get grouped into things and that's not really how lot of elements but with enough elements you can get it to grow to more layers and anything that is always interesting to see but which I don't have here is collisions so I advise you to play with it and if you want to know which arm is great collisions I have a pair of numbers that I memorized you can talk to me and I'll talk and this is the last one should be also a simple guess it should grow yep so that's a bit of entry that highlight it's well yeah it is a kind of a binary tree yes but which one it is a red black yes I didn't hear who said that but it's particularly interesting one because it's rebalancing and I just have I just happen to have 15 elements here so we have to see it become a fully fully initialized tree yep so that's pretty much it if you have questions about anything this is your last chance thank you [Applause]