Scale By The Bay 2020: Vlad Patryshev, Functional implementation of Finger Trees in JavaScript
[Music] okay so my name is vlad patricia the title was like on this announcement some somehow says i'm vlad contributor well maybe i'll take this uh to the emulator so anyway and what patricia and i'll talk about uh an implementation in javascript of fingertree i implemented it for my students when i was teaching uh them this year when i started teaching them sacp in javascript but this talk is more about like how our functional structure looks like and let me switch the screen so it's about finger trees in javascript and this is me and this is the link to this presentation and it's not slides it's a workbook in observable hq so what is finger finger tree it was invented like some time ago by ralph i believe hints and it's a very efficient data structure a lot of operations take amortized constant time and it's efficient specifically efficient if the data stored or the key of the data uh belongs to an ordered monoid so what is a tree maybe some people know what the tree is some not so this is like a tree is represented by a for by arborists so a tree has a trunk the tree has branches uh like a branch has laterals so like branches and branches the connection between the trunk and the branch is called scaffold and the top of the trunk is called leader and if you have like some additional stuff growing if you didn't trim it properly you'll have water sprouts and there are also circuits that you are supposed to trim away as soon as possible because they sucked the water the juice from the tree so we are programmers right so a programmer programmers usually represent trees as if like the trees are in australia and we are here in america so top uh on the bottom and bottom on the top so that's how we will look at it in haskell a finger tree looks like this so let's look at this data finger tree it's either empty so no data there or a single value there or it can consist some digits of type a and a finger tree in the middle and digits on the left digits on the left on the right and we wrap it all with we call it deep so what's a digit it either one value two values three values four values and also because the inner finger three contains nodes so now we have not like playing data a but node that contain either two values or three values so look at uh how finger tree looks finger trees look like empty finger tree a finger tree with just one value so single a finger tree was one value in the value in the middle four values in those digits on the left it's four and one value on the right if we have like one more value added so we suddenly have a node so here's the node in this single and it has two values if we add more so we'll have more nodes on the left on the right and eventually we can grow to something like this on the top we have like primitive values then we have nodes of the first degree then we have nodes now of the second degree those nodes of the third degree and they could be like either three so it's like two three trees a node can have two or three sub nodes or values so here's how it will grows if we add values so see we add values but there are no not more than four values on the right or on the left and if there's more we push them down there into the structure so this is like we removed it and then we are growing it again so that's how it looks like if we are throwing in data on the right and taking them away on the left and again like of course you can add data on the left add on the right or you can split the tree you can merge two trees these are the estimates of operations on finger trees compared to other structures like 233 it's all logarithm lists vectors hash tables which is basically some operation just don't apply because what's a split for hash table or split by measure i'll talk to you a little bit later but basically we have either logarithmic or constant complexity so we will improve if we don't have like anything uh if we don't know anything about the values we cannot be efficient enough but if we have an ordered monohyde so ordered monoid is a monog with like zero operation with the like merge operation and with the comparison so it's partial order or maybe linear linearly uh examples of uh ordered monoids are size of something like size of a tree maybe a size of a value priority like value priority so minus infinity the neutral element for max and we can compare strings with concatenation or like price of the values inside so if you stop them properly there will be really good like and operations will be uh will be pretty efficient so let's look again at haskell representation so we have finger tree which is uh empty or single or like a deeper tree with digits on the left uh like fingers on the left fingers on the right and a tree inside where values are already nodes so i won't be using the standard javascript like object oriented no i'll be using the kind of javascript that you can find in sacp book so here's a prototype that just represents the data so it's a structure that has like empty which contains no values single which contains a value 3 which can contains like like here left right and a finger 3 in the middle so it's a sub 3. and now what are the values digit 1 it just contains one value digit two contains two values digit four contains four values and no two takes two values and not three tricks of three values and what does it mean it means that we have to stuff in some operations here because otherwise okay so it swallowed the value and it doesn't do anything here but it's a function and at least we can build something so what we built first is serialization so let's introduce methods of those uh like uh different uh sorts of three different kinds of trees so empty string of empty will return just these angle brackets single will return will it will say single and the value of that a dollar by dollar uh yeah whatever uh so oh yeah yeah yeah this is uh formatting so this is uh observable hq uh like string interpreter interpolation so backtick you mean that well we'll stop the velvet there so three because the tree has left uh left branch right branch and the sub tree so to string will do uh what it will say three left branch sub three right branch digits are like i'll put them in square brackets so one value two values three values four values so now we do something with the value that we provide right and nodes and node can contain either two values or three values so we say node and then the values and those values they will be stringified so the string will be producing stuff like this so let's look at the an application right so because we created finger tree here so this is the object that produces this data type data structure so let's build a tree that can contain like digit two two values here 11 12 then a single in the middle and one digit on on the right so it's string representation would be well because it has two string right a string representation would be three and then this uh 11 12 in brackets and single and 13 brackets so you can see that it's something like this or something like this kind of structure if we throw any in more data like abc and ge and lgh so we'll have this kind of structure abc on the left and on the right that's the last one and in the middle we have a tree and this three contains a branch containing node e and another on the right it contains node it contains a branch with two figures node a ig and node klm and in the middle we have a single with node inside so that's how it works and we can make it like more and more uh we can go deeper and deeper infrastructure so but again this is the way we can build the data but maybe we throw in more operations we like said that ah cons is efficient so let's implement cons so here i pulled out the implementations from that structure that i returned right so all this empty single three digit one and so on they are defined here and because it's well because of javascript and because it's kind of primitive version of javascript so i have to declare those values but then i define them like single string is the same but cons so we have a single right if we add a value to single we'll have this three b on the left the one that we add and digit one on the right so let's let me show you the picture this is single and we add a value so that value would be will be on the left and this value goes on the right and the same like how do we add a value to an empty well basically we just call single how do we add a value to a tree from the left so we do constant a we do cons to the left branch and the left branch also we need subtree if if it wants to throw in some value inside in digit one we do a con so we add a b digit one already had an a so what did what it does given a sub three and a right well because it needs them to like return to three so we create a branch with two values on the left the same sub three and the same right so the same digit two we just add one more value c to this a b so we have digit three here we uh digit three we have we add one more value d a b c and then we produce d on top so digit four is trickier because we have four we cannot have five so we pass an e and what happens here we already had a b c d right so e is left with this a the leftmost element of the previous tree but the the rest goes down into sub 3. so we create a node of three values bcg that we had in this in this branch and we push it down into sub 3 and subtree that's the same cons so we don't know what it does it's a tree right so it does something it will probably do the same thing like take take it's left and try to push so and what about node we don't push anything to node we just build nodes so it doesn't nodes don't have the cons method so how does it work like here are two examples i wrote a method called uh build which takes like if uh build a tree of n values so if it's zero it's just an empty otherwise we do by recursion build from n minus one a and do comes with n and so let's let's run it yeah so this is how it does how it works i use promise to delay so so it will it's adding like four and we it it produces the same three oh see how it is it goes down then where i painted seven painting eight and then again push and then again and then again and again okay the like symmetrical uh like mirror like uh operation to con this knock just append uh on the right so in this piece of code i wrote snook but i didn't add cons because like in this example i we just didn't didn't need it so if we have a tree how do we how do we append an a on the right we append that a to the right one and we pass left and sub three to that right to build to produce a tree so if we have a single a not could be just creating like a single already already has a b a value b no it has a value a so if we push b we'll have a tree where a is on the left and b is on the right so digit one we just push uh the value digit two we push one more value so we had a b we add c digit three we had a b c we add g but digit four we push e but we push it on the right so we'll keep g on the right branch and create a node with abc and push it to subtree left left subtree is left intact so this is what we will have like empty then snug one will be single one snox two will be three consisting of one on the left two on the right then we push we push four push five and we push six five and six are left but node of two three four is inside inside that single okay so we grow grow we have eight now we push nine we create a node of five six seven and push it inside that single and that single you know how it grows it creates a tree with node with two nodes and empty in the middle so that's how it grows gradually to like snog of seven this is not exactly like very beautiful but i'll get a beautiful representation a little bit late so because this structure is symmetric we don't have to write like hold left fold right well i mean we can but it will be basically it will be looking the same so here how do we do fold on a tree we just scan the whole thing and go deeper and do the folding side so what does fault require it's a magnetic operation and we need a binary operation and we we need a neutral element z so this i defined it for like working with this with the values that don't belong to the tree so we have that value and if that value has folds for full glue hold left so we apply that fold left with the separation and neutral element otherwise we just do this operation on neutral element and the value so for instance we add numbers or whatever how do we do that for a tree consists of left branch right branch and the middle three so we fold the left branch no let's define a folder the the thing that does operation that that fold operation and then we do left sum the sum of left branch right sum the sum of right branch and the middle sum and we blend them all together left middle right and we assume that the monoid is associative so we know like we have to do it in this order but we could group it differently so single what do we do with single fold it just what it contains a value a so it could as well return a but for like for simplicity withdraw we rather do this folder and why because if the value is a primitive value then it's a but what if it's a node we have to do stuff in the node so digits it's obvious that if we have like a three uh digits with three values so we fold for each value and do the operation like blend them all together so what do we do with the node we have a and b so we fold the values inside and then apply this operation so that's eventually how we do a and we produce this here's an example here's an example we build a tree like this so given an n we build a tree that consists that has a b c and or all these values stored there okay so we have a tree that looks like this a b c d and then d p e f g and then d p h i g j and so on how do we like here's an example of uh summing summing up with some sum them up like this an empty string as a neutral element and just a concatenation with space between four values so we do that well we do some right so we fold the left and we'll have this a space b space c and why do i do i do three because on many occasions we'll have like a space somewhere on the right empty string so empty string with space it's an empty string i'd rather trim them so that's how we have this thing if you add instead like and run it yeah that's it's around so to improve performance we need something uh we need to know like the sizes of nodes so here let's introduce this size and suppose suppose each value has a size so if the value inside is primitive so it just its value is one otherwise it's the size of the node and now it contains like two or three sub-nodes those sub-nodes contain more so we just add the sizes so we cache the size like given a tree its size is the size of the left branch the size of right branch and the size of subtree so if i have like digit one the size of size of a otherwise it's the sum of sizes and so on and for nodes uh the same like we add the sizes so suppose we build these strings these this three again just in the opposite order like z y x and so on there's a uh in the beginning here a so if we check the size the size is returned because when we build this three of the three the tree has this size so once we create it the size is already cached so we don't we don't recount it again so it's 26. and if we have a size we can search by index so let's introduce a method called at so like given a value like it no let's do add something like at the digit right so we do at on that value so at like takes an index given a value it takes an index and try to find the value that is uh if the the if the index is below zero or bigger than the size away so it's it's not there if we are dealing with a part of a tree then we've applied that method at so that indexing in extraction by the index otherwise it's exactly the value no if i is zero so we'll find the value at a given index again how do we do it like for a tree we we try to find it on the left if not then try to find it in the middle and then we find to write it i find it on the right and because it's logarithmic so basically all search is logarithmic because the tree is exponential like what do we do with the node uh we try to find it in the left sub node or in the right sub node here's an example uh like i create a tree consisting of abcd and so on like this right and then i find elements sample at zero and then sample at one and so on and i push them into out string so that's that's what we find like at zero at one and so on and then i do the same in the opposite order so number 25 number 24 number 23 so number zero so that's how this find uh works well because that's in the that this index right but we don't have to work with just indexes we can instead we can introduce a measure here i create a tree that takes a measure function and what's a measure function it's a function that basically calculates a measure of a value so it applies to a value and it returns something about that value maybe like the length of a string if you store strings and characters inside the tree otherwise we call measure method of the thing like in a tree the measure of a tree is the sum of measures the measures of left the measure of middle and the measure of right and so on so it's the same as length except that we call a measurement so here's an example when we use measure as length so we create a finger tree with measure that is just the length and so we do the same like index find by measure is fine by index but in this example i create a tree consisting of this phrase from the raven once i put them upon a midnight dreary so i created this just to show like this is the index of each character but what we store in the tree is words so how do we find the word uh that can is summary like and given at a given position position 10 points to midnight that's a character number 10 in this stream position 41 is the word end so that's how we find it here i created this is just a show right but i call sample at 10 and because the measure is the position so this thing at 10 is the word the no the value at 10 is about midnight it's not like letter i because we stuff once upon the midnight really so that's what we do right like we create this thing by recursion okay so these are examples of operations that we could do but then actually i figured well that's that's not the right representation when we create a node right so we don't like uh we don't have uh we don't need references we have a node inside the node inside the node so it's like if you cut a trunk if you cut a bra if you cut a branch you'll see those like sub branches that grew there before so that's the idea behind a better graphic representation of finger trees let me see let me get there like here let me start the show we are adding things so see we take the three and we pull them into the next level so these are the nodes and i surround them because like that's what we get together and pushing to another node so that's how the things grow and you see it's more compact and it represents the idea of uh of the tree growth here so we are adding but then this is like carry it's like uh carrying i don't know impositional system of yeah i'm accelerating it because like there are so many letters in this world okay so we're done with romanian letters i believe romanians can correct me so that's how it is actually like the top level primitive values second level second order nodes third level third order nodes and nodes inside the nodes and primitive values inside and so on and because we were appending on the right the things are bigger on the right than on the left but it does make uh make it more complicated than winter search so that's how it is and also you'll you can see that all nodes are of level three there's no nothing that is of level two there's a reason for that actually two or three alternating it's good but here when we only appended on the on the right when we were doing snook so that's all we could produce so here's another another example when we append left and right so it's more symmetrical right that's how it grows i don't i'm not showing you the source code of this because it has like too much code uh dedicated to graphics to 3g so this this is how a tree looks like if we append alternatively alternating from on the left and from the right and i believe we also added more values no armenian letters yeah so that's what we have that's how it grow okay but i said that there are like efficient operations split and merge i wouldn't show you split but i'll show you how merge uh works like given choose three uh two trees how the step works so here are two uh trees and they're going to merge okay so how did we merge with start at the top pull away these branches and try to group them we have seven values okay two and then two that's where nodes of size two uh size two are coming into the game okay so next level they are of these things and we have at most like what 11 11 notes so we group them again and we push them down okay done but now there's nothing on the right so let's attach those nodes to the longer tree and then merge the trunks done we have two trees merged and you probably saw that it's logarithmic right so that's what it is and i'm done and here are the references here's also the link to this presentation it's also on the top and the presentation is observable hq dash slash at the patrick slash finger trees in jails so thank you and also thanks to lexi and oli and salar and all other organizers i don't think i know and special thanks to mike buster or it should be c right yeah i'll fix it for uh like producing this beautiful uh engine beautiful workbook engine where like we can use it so thank you any questions [Music] you