I programmed in TypeScript like in Haskell (Lazy Evaluation)

who knows what is lazy evaluation who knows what it is so lazy evaluation hmm yes a good dog actually is pretty close it's a basically is when expression is evaluated when it's actually needed what is that supposed to mean let's take a look at lazy evaluation a little bit further so today I'm gonna use typescript for all of my explanations because I found that you know things like JavaScript are quite easier to understand for younger developers because that's what they work with and since JavaScript has like more or less function programming capabilities it's it's kind of easy to explain functional programming pure function programming using that language but I'm not going to use JavaScript I'm gonna use typescript for the reasons that will be clear a little bit later well the main reason is that while working with my examples it will be quite easy to make a mistake of passing a wrong value and all my examples may fall apart because of that and it was spend a lot of time troubleshooting them so we can utilize the type system of typescript to help us a little bit and I would like to make a small disclaimer saying that I do not recommend developing software in JavaScript or typescript in the fashion that I'm gonna show today because I'm not a professional JavaScript developer and I don't even know performance implications that this approach may have in that specific language if you want to have like a proper lazy evaluation I would recommend using languages that supports like that or at least libraries that were developed by people who know what they're doing so everything I'm gonna show today is purely for educational purpose just to show you the idea how lazy evaluation looks like especially in languages like Haskell in Haskell you you may hear if you heard a little bit about Haskell you probably know that everything in Haskell is lazy the entire language is lazy and today we're going to explore what is that supposed to mean okay here we go let's go to our folder where we keep all of our projects and let's create a project called lazy so typescript is a superset of JavaScript that was developed by Microsoft and you can find the implementation here but we're not going to use these typescript today because setting up their screen is kind of tiring in kind of cucumber some in some way because you have to install it through NPM and stuff like that you have to set up the project I'm gonna go a way easier route today how many of you heard well I mean my dad probably heard about it about a thing called dinner or dinner I think it's supposed to be pronounced like Dino ah yes this one it's a secure runtime for JavaScript and typescript basically it's like not j/s but with typescript the and the cool feature of this particular thing is going to be is going to be clear once we download it let's actually go ahead and download it of course they are suggestion to use their shell scripts I mean come on like I don't even understand why you need to do that like let's just download the latest release and and everything is going to clear seriously like I don't understand why you need all of these shell scripts and stuff like that I just don't understand that like oh let's open release this the ladies review this and we have Linux x64 I still know this thing and let's actually put it some way here yeah I think it's good enough think it's a good enough and look at that take a closer look at this file do you notice anything weird it's not tgz and not tar.gz it's not a tar ball it is not a tar ball let's unzip it okay 57 megabyte what the hell is this file a 64 bit LSB shared object its executable a single executable the whole interpreter why not GS is not that why do we need all this weird different structure why not GS is not that I don't understand like something went horribly wrong when we started to go into web development like something went horribly wrong I guess here it is and on top of that it supports static typing because it's not using javascript by default it's using type scape and this is the thing that we're gonna use today so it showed some kind of an error before I didn't even know what it showed their main panicked unwrapped error valid to blah blah blah I think I tried to evaluate it in the weird environment I think I tried to eval I can run it like that it panicked for the first time with the rust error if it compiles it works am i right anyway so let's go into yeah another interesting thing instead of like a c c++ they use in rust so yeah this is sort of main selling point of this thing they are single executable they're using typescript instead of javascript and division rust and I know exactly what happened there but if it compiles it works let's create the lazy dot T as file and let's start exploring what what Emacs is telling me something so couldn't like it project with folder with TS configure jason ah this is probably my Emacs extension trying to run typescript server or something like that let's ignore it for now let's listen to it okay so let's actually and take a look at a very simple function that takes two numbers this is type screed by the way it's just like JavaScript but with types that's why it's probably called typescript all right and now we should be able to do something like that a boom it compiled it and it didn't print anything because we never actually call this function console a log some 10 20 and there we go here we go here's our Sun but this Sun is written in how some people will say very eager style it is in a very eager style so basically if I add 5 here the end result is going to be 35 but the most important part here is going to be that this sum will be executed before we go inside of this function right in lazy evaluated language that sum is not going to be evaluated and it's needed it's not going to be evaluated until it's needed so and it's going to be evaluated only inside of this function how can you achieve that how do you generally postpone execution or any kind of computation in any language how do you postpone execution so you have some code but you don't want to execute it you want to postpone it well somebody actually was extremely close you wrap all of that in the functions so now these values are not executed until you actually ask them to execute so let's actually create like a separate separate function let's call it lazy sum and the way this sum is going to actually take things like that so you see every value is lazy now and so to go to extract the values from a and B you have to call them and then if you run it like that it will fail with a compilation error because I forgot to wrap it with another function because you see this is also function and this is exactly the reason why I'm using typescript because we're gonna use sort of eager values like immediate values like that and lazy values right in the function a lot and interchangeably throughout the examples and without Apps Script I have no idea how I will be able to actually properly show all of that like because it's so easy in JavaScript to make a mistake and forget to wrap it something into a function what's interesting is that in Haskell you may think of the whole language where all every time is wrapped into such function automatically it's everywhere that's why you never have to actually explicitly say that so the Haskell will automatically wrap everything into a function and um wrap and call that function when when needed but it's pretty sure it's not implemented in terms of functions it has probably some kind of more efficient way of representing all of that but you can think of it like that too you know to make it a little bit easier for yourself okay and to actually call these things you have to wrap them like that and then the result of this function also has to be called and there we go here is the eager sum and here is the lazy summer I think it would be actually pretty great to mark them somehow to label them somehow so this is eager sum and this is gonna be lazy sum okay so this is basically how lazy evaluation feels like in Haskell in languages like Haskell so in this particular situation ten plus five is not a bit as good is not it going to be competed outside of the function it's going to be completed inside of the function exactly when it's needed the question is why the hell would you need something like that why would you want a program in a style where everything is sort of wrapped in the function and postponed until it's actually needed what's the benefit of this kind of style of development like why would you do that and even on top of that create a whole language that you know that enforces this kind of style so interesting thing you don't evaluate something that you don't need so if you have a big operation a very heavy operation that you're never gonna need it's never going to become calculated so you may have in some situation performance benefits how about that so okay to make our life a little bit easier let's actually introduce a new type that represents the lazy type in typescript if I remember correctly you can introduce type synonyms or type alias as I don't even know how they are called and on top of that the alias can be generic and generics work very similarly to Java generics so yes they got the idea from all sorts of different languages so what you can do you can define the type lazy C and make it equal to function that doesn't take any argument and returns T so after that it should be quite easy to do something like a boom boom and as you can see so now at the type level we can clearly see where when a value is lazy and when it is not lazy so it's it's a little bit easier to read it like that I think in my opinion so we explicitly marking a value as lazy yeah and everything seems to be okay so what's like a actually take a look at the example when you can avoid a pretty heavy computation using lazy evaluation so the famous example I think is something along the line so let me actually type some some kind of like a separator here this was some sort of introduction in introduction and here's avoiding big computations that are not needed alright so imagine that you have not only a big computation but the competition that never actually ends so something for example like hang right so hand function believe it or not hangs so and to make it applicable to any kind of type we're going to make a generic right so it always return T so you can assign it to any type and once you will try to compute this kind of function it will hang immediately and consider the following the following function what's called first it takes two arguments a and B and returns a guess which one it returns it returns the first one it returns the first one so if you assign something like 10 hang what will this function return let's let's find out well it didn't really hang but it actually exceeded it so you know the the stack limit so we could have actually put some kind of like an infinite loop there inside of a function but I just decided to go with the recursion because we're so sort of sort of developing everything in the functional style that's why I'm using a recursion a lot but anyway but what if the function first was lazy right what if it to use lazy type let's find out let's introduce a lazy first and this one is gonna be lazing this one can be lazy and the result is also gonna be lazy and we'll use a lazy first if you try to run something like that it will tell you that you forgot to wrap this thing in a function to actually make it lazy you see how typescript actually helps us to find errors yes static typing by the way no it does not limit your career you know it does not force you type redundant things it helps you it helps you okay and let's put something like lazy first there we go and what's funny is that this is where it didn't really help us because console.log is a very dynamic function that basically inherits his behavior from JavaScript yeah but at least we can see the error here in the in the output and we can actually force it so yeah it returned ten despite having an infinite computation in one of its parameters but since we never used that parameter it never actually hang what is the past of Hank I don't know but you get the idea hanged regular verbs Trinis them hyung hyung okay thank you and how would something like that work in husky for example as already said in Haskell everything is lazy automatically you don't have to do any of this stuff it's by default lazy if you open HCI and you define a function first like it takes a and B and returns a so if you do something like that it will return you ten so and you can also define function hang it's actually super easy to defined you make it equal to itself and then when you run it it hangs it just hands and you will control C it and if you do something like ten hang it will be still there but if you swap the arguments here if you put Hank as the first at ten is the second it will never finish because now you put the infinite computation to the argument where it's actually needed and it Hank so you see in asking it's automatically like that the language is lazy by default always but here in typescript we always have to mark it like that anyway so cool you can avoid big computations what else well something like short-circuit evaluation it's called in other languages not functions on the lazy languages it's called short-circuit evaluation happens naturally what is a short-circuit evaluation our computation I don't know exactly remember what was the last part of it who knows what it is what is short-circuit evaluation of short-circuit computation shirt sir kids computation I think it's evaluation is to see when it does evaluate the right side of the expression it doesn't matter yes it is related to boolean operations and let's actually Google that shirt circuit evaluation or maybe computation I don't know help me out there they go oh yeah I was right it's evaluation would you look at saint would you look at that so yeah the idea is take take a look at end operation right take a look at end operations if first operand of end is false it doesn't matter what's the second one it just doesn't matter because the whole result is going to be false anyway and the second argument is never evaluated so what's funny is that in majority of the moral languages is if the right expression has side effects they also will be not will be not happening Oh in Nahas children kajillion just coming back I have no idea I kind of you know they kind of start feeling repetitive so I stopped doing them so maybe I just need to find like a difficult and interesting task and maybe then I can make another episode I'll think about it thank you for bringing that so yeah it's very close to lazy evaluation as you can see it's very close to lazy evaluation it just has a different name it's almost like in you know in computer science people are inventing the same thing the same thing in in parallel independent of each other like anywhere else I guess so in lazy evaluated language that thing happens naturally let's find out how let's find out how so let's define a function and and it takes two arguments a and B and all of them are lazy billions are lazy balloons so how would you implement something like advanced without using this separator by the way so to make it you know the actual implementation we should not use this thing because I mean it's already implemented so it's cheating it's cheating basically we're gonna do if a is false well it's always false it doesn't matter what's B is if it's not false well that means the the result of the whole expression is going to be B because it will just depend on B if B is false then the whole thing is false if it's true and H is true well that means everything is true and on top of that we have to return this thing as lazy can you already see why this function will have short-circuit evaluation behavior because if this thing is false we're gonna fall inside of this branch and we'll never even call B and we'll never even call B let's actually try to test this assumption and see if it's true or not let's do a like a truth table for for our function so we're gonna have four parameters I think false false true false true true and false true false true so what we're gonna do here we're gonna use a little bit of Emacs magic by wrapping these things in functions making them lazy as you can see Emacs is very very stable in that sense and then once we call call them on these parameters we have to evaluate those things and let's actually print all of that so we're gonna use console.log yeah I'm gonna put this thing here replace this thing with this kind of stuff not not this one but rather this one equal so let's verify that this conjunction works correctly let's verify that so we'd also like to separate you know this particular output from the rest of the output so it's a little bit easier for us to read yeah why not what's used equals so is it correct okay it is only true when both of the arguments are true if any of them is false the whole thing is false okay but how can we know that the second argument is never evaluated when the first one is false how can we verify that experimentally is there any way to verify that experimentally we can do that with logging so let's introduce a very interesting function called trace it's a generic function and it takes a lazy generic value and returns another lazy generically it acts like ID basically it doesn't modify the will it just returns the well you but on top of that will you it's also going to take a message not lazy one though that it's going to print when somebody will try to evaluate that value how would you implement such thing well you would wrap this value into another function that will perform the login of that specific message let's quickly do that so here's the function here's the other function inside of that function we're logging that message and only then we're forcing this lazy failure so you see the result is still a lazy really but once you once you try to force that lazy value it will perform the side-effect let's make any sense about that so how we're going to apply all of that here let's find out let's find out so I'm gonna use Emacs magic yet again and I'm gonna wrap this value with trace and what kind of message I want to print there well since it's a left argument I'm gonna put L there okay I probably wasn't mataji to actually get rid of the multiple courses right now and here we're going to do a very similar thing but we're gonna put right here alright and I think it makes sense to actually format it slightly like that so if function add and we'll touch any of its argument they will scream with this message and we will clearly see whether it's touched left or right value let's find out if it's true or not okay something interesting is going on so you see for false and false it only touched the left value but that never touched the right one for true and false it touched the left well it figured out that the left value is true and we need to check the right one so yeah it took the right one the same for this one and of course since the first one is false it doesn't matter if the second one is true it just doesn't matter everything is false and we never touched the right one so you see once you mark all of your types as lazy the short-circuit behavior happens naturally and this is not something that you have to hard code into your language so something like that so this is sort of like a the second benefit of lazy evaluation something just happen naturally not the biggest you know benefit but anyway the same goes for kanjani disjunction as well so we can even to make it complete let's implement or write how would you implement or what's fun is that all it's kind of an opposite if a is true it doesn't matter what is B the result is true if a is false it will depend on B so this is basically the disjunction behavior and we can try to verify that I'm gonna put a consoler log something that was actually good three of them and let's copy-paste this thing here so what I'm gonna do I'm gonna go ahead and replace this thing with double bar I'm gonna replace end with or and I'm gonna leave this the code everywhere else the same okay there we go and here is our disjunction you see when it became false it needs to check the second one because if the second one is going to be true the whole expressions can be true so the first one is true doesn't matter what's the second one everything is true the first one is true doesn't matter what the second one it's true second one false first one false but the second one is true the whole thing is true so you see we can clearly see what what arguments were checked everything works as expected what would be another benefit that we're going to take a look today I guess the main and the biggest benefit that everybody is talking about when they talk about lazy evaluation and I already saw somebody is screaming about it in the chat yes we're going to talk about the infinite beta structures infinity structures can you imagine that how can you hold an infinite data structure in the memory how can you do that but you can so some parts of the data structure are not evaluated yet that's why you can have infinite data structures let's take a look at all this simplest one lazy list linked list everyone's favorite anyways so how would you define a lazy list in typescript with the lazy T type infinite data structures structures we need data structures interestingly enough in typescript you have a very epic feature where you can define type LS s like so you can define the type fool that is number or string I guess you can think of them as Union types maybe they even called a union types in terms of a type script but anyway and if you use full the compiler will check whether the type here is trying to put there is either number or string which is pretty convenient as a matter of fact the type system of type script is extremely powerful it's very powerful and I think this is exactly what you need to you know control the the wild language like JavaScript I guess you need a very powerful type system to actually hold the whole javascript in place so that's why it's so powerful anyway we're gonna use this kind of thing to implement a sort of algebraic data type thing if people who program and ask if they probably know what I'm talking about let's introduce a thing called a lazy at least a lazy list list so what is a lazy least well empty lazy list let's denote an empty lazy list as no no by the way is a type as well there is as far as I can tell this such type in or maybe not because I just remember that in typescript you can even define types that look like this I think you can do something like that so basically you find a new type as enumeration of specific values and yeah if you don't put that exact value there is gonna be a compile time error so I guess in this particular situation this is not really a type it's rather a specific value yeah but I'm gonna use new instead of undefined because I think it's a little bit closer to what I'm trying to achieve there it's a little bit closer to what I'm trying to achieve there anyway so it's gonna be either new or a pair of values as far as I can remember again in typescript you can actually define your own structures by just writing them as a JavaScript object so the first element of the lazy list is going to be the head we don't even call the head which is the lazy value of T and the tail is going to be the rest of the lazy list the rest of the elements of the waste list and on top of that the whole list also should be lazy like so so this is how you would define such type since this entire thing is the type you can put it as a type parameter for lazy value let's see if it works let's see if it works how do you like this type definition that's why in Haskell everything is lazy automatically and you don't have to explicitly mark anything as lazy because you don't have to deal with this kind of nonsense but this let's actually find out if it can pass from that I have no idea if I compile that's compiled it does seem to be compiled it's kind of inconvenient to you know work with this type maybe we can introduce a function that takes a regular array and generates you a lazy list that will be actually pretty convenient I think what's actually going to do that what's called to list it will take array of of course it's gonna be you know a generic thinking how do you define the race is it just number this I think this is how you do that and it will return you a lazy list see right is it is T so as as far as I know you cannot even return new lazy list is lazy all the way through it actually worked surprisingly enough because oh I guess it might move okay sure okay T thank you thank you thank you super keeper it's kind of strange I don't quite understand why it doesn't complain on putting new there I guess it moves the function yes it moves the function itself that's probably more heads doing that so but if I wrap it with a function like that it's also not gonna complain about this anyway alright so how can you convert an array into a lazy list it should be fairly straightforward if X is is empty how do you check the length of the array in JavaScript I don't remember I think it's just dot length and then you check if it's zero or not if it's zero we're gonna return no right we're gonna return no otherwise if it's not zero we're going to return a pair where the head where the head is equal access zero and tail is going to be equal recursively to least and a slice of access without the first argument but I don't remember how to do that in JavaScript do you guys remember how to do that in JavaScript there was a function like slice that takes an array anything it takes the first element there and you it will just work oh yeah it's X slice X slice one okay thank you evolve e evolve your mind I guess this is how we do that look it's it's very similar to slice syntax like in Python but you know they decided not to embed that into that into the core of the language so it's a library function so yeah this is basically how it's gonna look like essentially alright let's try to compile that and see if we didn't make any mistakes we apparently did some mistakes which is very interesting yes this thing has to be lazy for good about that this thing has to be lazy there you go it compiled and let's try to print it and see what exactly it will print so consoler look to least one two three one two three so and we get the function because it's a lazy value in if you remember correctly lazy really is basically a function but what's gonna happen when you try to call this function what's gonna happen being sure to call this function well if we challenge you appear where head is a function until is a function okay let's try to take head and call it and see what's gonna be there alright it was one so if we try to do the same but instead of head we're gonna call the tail well it's the next player it's the next player so we sort of X like unwinding that lazy least one by one like layers of onion yeah because that's exactly what's happening here because here we recursively build that onion and now here we manually peel with back so what if we call a head of that tail so what's gonna happen now we have the second element to okay what if we put another tail here the next will will we receive the next value here we go it's three next a will we receive the next value if we try to call it like that and we won't why because yeah head turned out to be new so if you take a look if you remove this head from here the last element was new and it indicates the end of the list we cannot go any further so it's a really weird thing but it's still finite structure how can you implement something like that but infinite what if we could make this list that infinity goes to infinity like it you will never encounter new whatsoever let's try to do that let's implement a function called how they call it range and it's going to take a number from from what number is going to begin and it will return you a lazy list of numbers so how would you implement something like that all right let's take a look [Music] hmm you simply return hat begin because begins already laces so we can just put it here and what's going to be the tail tail is essentially going to be a range where begin plus 1 so we recursively generate an infinite list but it's never gonna be gonna stack overflow because it will evaluate the next element only when you try to access it that's the thing so it only evaluates this element when we actually try to access them it's never evaluated until it's needed never evaluated until it's needed and all of that actually very close to generators in Python maybe there are generators in JavaScript these days so as you can see a lazy evaluation it gets to the mainstream languages these days quite quickly as a matter of fact a lot of functional programming ideas they never made functional programming languages successful themselves but the ideas sort of sucked up into mainstream languages and now we kind of have them in a different form in a different name but we still do have them and they reduce well they're useful so all right so let's try to do the following thing I'm gonna do I'm gonna do console along a range let's start from 3 and what's it was gonna happen so I'm gonna actually separate whatever I'm doing here now console 3 and that's gonna happen ok doesn't compile because this thing has to be lazy alright so function obviously excuse me you have to force this thing alright so now it's a player if we take a head of this thing it's three because we instructed the arrange function to start from 3 Oh already javascript has iterators engineer asus okay we're about them so maybe my entire talk is actually obsolete but i still want to show how it feels like in in Haskell at least so and let's repeat the same procedure for yet another tale wasted like that five six seven and it will never end it will just never end at all so since it's not really convenient to you know peel off these lazy lists like that let's implement a function that prints lazy lists for us that would be way more convenient what guys think I think it's a good idea that's let's implement that as implement that and so so let's implement a function called print at least it is going to take a lazy list I guess of T because we can just pass T to the console log and it console.log can print pretty much anything so what's actually make a generic and I guess this function is not supposed to return anything it is not supposed to return anything okay I guess we'll have to maintain the current pair all the time because you see access is a function so before even checking whether it's new or not I have to force it first after I forced it I can check where the player is new or not is that the idea magic way of checking whether something is new or no they don't I remember yeah and of course it has to be not equal of course it has to be not equal yeah if not know what do we do we just console console.log player head force in the head by the way and then assigning player tail to this thing so you see we automating automated this step here with a while loop right so and let's test if it works or not so first we're gonna print just a regular finite list just to verify that it's you know generally works because maybe it doesn't work at all maybe it doesn't work at all would you look at that it did you work for a finite list but of what about infinite list what's gonna happen if you try to print an infinite list what's gonna happen chat this is gonna blow up this it's actually kind of scary imagine printing and infinite data structure have a go of course three also has to be infinite three also has to be infinite well it went for a while and would you look at that what the hell is that what print does not even do any recursion and it's still got Stack Overflow what a hell [Music] well the problem is not really in print list the problem in the in the range implementation the problem is in the range of limitation was like a look at it so I can add anybody spot a problem can anybody spot a problem we take begin as the laser value and we put that laser value without even forcing it so you see to construct a lazy list we construct an Elise list of waste values that are never evaluated unless you try to touch them right so that begin if you put a very heavy computation into begin it will never be evaluated even if you try to traverse the list because that traversing doesn't even try to attach it unless you go to the second element where you are trying to attach it so what you ended up here is a very interesting situation where you have first element equal to function that returns three second element as you can see we put this expression as a second value right second value is going to be ended up with a function that looks like that where begin is the previous function so you basically replace begin with this function then you can just repeat that process infinitely where you basically take the previous value and replace it or please begin with it receiver angle is zero angle eight so this is basically the process that we have here what you end up with is a growing postponed computation you ended up with the list with a groaned postponed computation and this is one of the downsides of lazy evaluation you have to know how it happens because you can end up with something that you can classify as a memory leak yes so and this will grow and that actually contributes to the stack overflow that we witnessed here so lazy evaluation actually solves one class of the problems but introduced another one so it has pros and cons so when you work with lazy evaluated evaluation you have to keep these things in mind all the time so how can we mitigate this thing how can we mitigate this thing well we can just go ahead and force begin hmm so if lazy list is already lazy why head is lazy too why not make head not lazy it's a good question the reason is I wanted to demonstrate the true experience of Haskell not sugarcoat it but exactly the problem says the trick I have to deal with when you program in Haskell so because Haskell is not an ideal language and there are problems they're quite serious ones that difficult to solve and here they are everything is lazy and here's the cost kinetic consequences and you have to deal with these consequences so in in Haskell this particular range would not be as bad as in typescript because of separate small details but still there are similar problems in Haskell okay so in this particular situation we can just force begin like that and it will pass yeah and we'll just go into it it's even faster can you notice it it reached 17 K faster like because we had a problem on 17 K let's actually go back to the to the region elimination so it blows up at 17 K okay it blows up at 17 K but look at the speed with which it actually reached 17 K it was actually quite slow but once we start forcing this thing right yeah once we start forcing this thing semicolon is the semicolon what small stupid mistake did I make what small stupid mistake in the mixture head should do is a thank you yes that's exactly why we're using typescript it already reached 17 K it already reached enacted actually went beyond it so it lazy evaluation does make some things faster in very specific situation but in some situations it can make it even slower so there are pros and cons this approach is not ideal this approach is not a silver bullet keep that in mind all the time it's just a different approach this approach is not a silver bullet no matter what you know husky phonetics tell tell you because they will tell you all sorts of crazy seriously they've also a little told everything just to convince you that this is like the solution to all of your problems no this is not this is simply a different approach and let's just keep it that way it's simply a different approach anyways so alright alright so there is a print list and there is a range what kind of advantage do you have with infinite data structures what kind of adventures they have within this region well you can take a such structure of the infinite data structure that is finite and the your program your program still will be terminated right infinite data structure finite subsets of it small piece fight finite piece of infinite data structure and your whole program is actually terminating this is the things you can do for example we can implement a function that takes n elements from the infinite infinite list and it will still terminate let's try to do that this is actually pretty common function in in haskell for example if you have an infinite list here's an infinite list in haskell your encoding is probably terrible yeah but it is what it is this is how you you know h.264 encoding usually deals with a lot of moving small characters and I really apologize for that so imagine that you have an infinite list and you can take ten enemies with and here you go our program terminated we took a small finite subset of the infinite data structure in the program still terminated this is what you can do with lazy evaluation how can we implement something like that let's just go ahead and implement that about that let's just go ahead and implement that function take so it is going to take n number and lazy list and return another lazy list - all right let's return a lazy volume again let's first force n to not repeat the mistake of wrench let em and force next we check if M is 0 if M is 0 well there is nothing to take the corner of this function is literally take asks us to take 0 elements out of the list so we need to return an empty list how do you return an empty list well m to be suggesting that's what this is just an empty list next if M is greater than 0 well it would be better to actually swap the branches and make this thing like that I guess I guess it would be a little bit more correct just in case M happened to be negative which it shouldn't be but we all know how it ends up then at the end of the day if something can happen it will happen no matter how how do you try so let's actually help ourselves okay and while we're doing essentially we are assigning a head to the head of the access list and tail is take M minus 1 from the tail of that list so we see we sort of crawling on the list decreasing the counter and once the counter has decreased we just chop the tail and just return that by that finite list and since the tail is lazy it's never evaluated so it will be just dropped off and no matter how big it is no matter how many computations you have in that tail it will you know still be still not happen don't forget to return a lazy eye wrap the whole thing into raising yes I wrap the whole thing in too lazy so don't even worry about it yeah this is something that you can also do ok so right now again this is an infinite computation now that the problem is not that or like this thing has to be as well yes this thing has two delays you see this is why we're using typescript imagine if I didn't use typescript and try to do something like that in JavaScript there will be nightmare to actually troubleshoot because it will try to compute that and those sorts of random things maybe not maybe it will say number is not a function why are you trying to call function and I would have no idea what exactly is going on where exactly I have to make a fix this thing is also not helpful so maybe maybe my argument or no arguments or no that opinion anyway so okay what did I miss here what did I miss ah I know what I missed I never forced access that's right I never first access but they don't really want to force it two times so let's actually force it and so the sort of remember it like we did in the print list right and we're gonna replace this thing with bear-like so yeah in Haskell it's way simpler yeah you see it's still infinite as it's supposed to be because we never actually try to do take and let's take ten elements out of the infinite list and see if it will actually happen again is it really ten elements starting from three yes it's ten elements would you look at that we took ten elements out of infinite data structure out of infinite data structure how about that isn't that cool I think it's pretty cool I think it's pretty cool so another interesting operation that is very helpful in working with infinite lazy lists is filtering and you you will see a lot of haskell are using that filter function all the time for example one of the things you can do is taken infant list it's an infinite list yes enjoy your encoding problems you filter only even numbers out of infinite list so you cannot see that probably you can't see that but these are only even numbers yes these are only even numbers and then once you generated an infinite list of even numbers you can take a ton of them and here you go you generated ten even numbers so this is basically what people do in Haskell they generate infinite data structure the filter infinite data structure and they take small subsets small finite subsets of infinite data structure so this is like it's sort of a different way of thinking about programming like different way not the best way not a silver bullet bullet just a different way keep that in mind it's just a different way so don't let haskers to rope you into their cult it's just a different way of thinking about programming don't let them do that anyways so let's implement a filter let's implement 15 to wait so yeah for some people it might be too late so for an ultimate Haskell experience a fool takes a function right food it takes a function that function takes the element and returns a boolean and that boolean tells that function whether to keep the element or filter it out for an ultimate Haskell experience you have to make this argument lazy the result also has to be lazy and the function is for hope no it's it's for ultimate high skill experience right but do we really want to go that route I guess for education a little example I'm just gonna mention that in Haskell it's gonna be like that but we're gonna keep it you know strict it's it's not gonna it's not gonna affect our example in any case but it's quite important to keep in mind that and housekey it's probably going to be like that if I can get away with this kind of thing without affecting the example that I'm going to show I think him yeah I'm gonna go that role anyway so lazy least and this thing is going to return the lazy little T so how can we implement that function similarly to take believe it or not similarly to take so we return the lazy value I suppose I'll have to pre force access and I need to check where the access is empty list or not because if it's already empty there is nothing to filter anymore and I just have to return an empty list so if player is no you can't filter an empty list there is nothing to filter an empty list you return an empty list otherwise what you do you check that the head actually is something that we want to keep so we take the first element at the head of the list we put it into the predicate so yeah I just remember the you know the the name of this function it's a predicate yes function that takes an element and returns a boolean is called predicate and if it is the predicate that I'm thinking about it might be it might make sense to also prove or the head like solo and in that particular situation we're gonna return the pair where head is X and the tail is filtered tail yes the tail is filtered tail so we pass F on and we try to filter the tail of it okay if the element is not something that we want to keep if the element is not something wanna keep we're gonna return just the tail so we see with dropping that element we just droppin it yes this is basically what we do if the list is empty there is nothing to filter its empty list if the head is compliant with the predicate if it's completed with a predicate we keep it by constructing a new pair and given the tail of filter tails so it's gonna continue recursively doing this thing if X is not something that we want to keep we just return a filter tailed effectively drop in the head effectively drop in the head and I guess that's pretty much it that's pretty much the implementation of a filter that is not probably going to compile the first try let's find out of course it didn't of course it didn't a property tail does not exist on type oh yeah of course it has to be player this is why I'm using typescript because I'm constantly making mistakes like that oh maybe this is because I'm just stupid that might be the case nor argument access was provided 151 I guess yes modality I think you're right I think I forgot to yeah I completely forgot the type typescript syntax keep in mind that I'm not a typescript developers so I may not know a lot of things there there we go even crazier even crazier calculation error I'm just realizing that my arguments for static typing are not looking very appealing yes we don't need static typing you see this is what static typing leads you to write unreadable errors if it if it failed at one time it would be more clear what exactly happened am i right yes why do you need static typing why do you need static typing anyway fifty term I'll get actually worse than haskers exactly so it's it's even better than you know ultimate Haskell experience we want it ultimate Haskell experience here it is here's the ultimate Husky experience okay anyway 152 let's go back so this is where it complains it says that it's not the lazy list but if you return no okay this is where we return this you see we already wrapped everything into lazy values so the we'll use that we return in these three exit points yes I have three exit points out of the function please don't tell the extra so this has to be not lazy values but the result of filter is lazy and that's why I have to force it there we go so at least it compiles compiled at least if compiled let's try to filter infinite list with this filter function yes so let's actually put cansada logo three let's generate an infinite list starting from one let's filter even numbers so how how can you determine whether X is even or not well you / - and it's equal to zero that means it's even and we want to keep it in the finalists and then we're gonna try to print that list Oh would you look at that Emacs is finally managed to start up typescript server and it actually tries to tries to help me by twitching at the bottom of it yes Emacs thinks that this is helpful yes Emacs thinks that this is actually helpful anyway let's actually try to run it and see and of course ultimate Haskell experience ultimate Haskell explains a bit about this one alright so it's doing its thing and these are even numbers as you can see these are even numbers let's try to take a small finite subset out of the infinite list of even numbers take 10 this probably has to be you know raising like that let's just run it would you look at that now we have 10 even numbers that we took out of infinite list of even numbers so yeah that's just an alternative way of thinking of you know of programming now the best way just an alternative maybe you want to even sort of now this feels like Lisp I guess it does feel like respect okay all that is cool now but how can you make it useful well this kind of approach makes it difficult to compute a prime numbers using how is that called my English is so bad Civ okay let's go that yeah yeah that is does not make it easier to read yeah this particular approach makes implementing these thing easier I'm gonna show you how how many of you know this approach let me try to pronounce it a rat as thinnest aratus thinnest I hope I pronounce it correctly yes okay so this is the visualization of the approach what you do you take infinite list of numbers you see it's already actually fits to our to our model you say that 2 is a prime number and then you remove everything from that list that is divisible by 2 you take the next element you say it's a prime number and then you move everything from the list that is divisible by 3 and you do that indefinitely you see how it fits perfectly to our model of infinite data structure infinite lists and operations of them like take and filter and so on and so forth it fits actually perfectly as a matter of fact the idea of implementing this algorithm for for this particular stream I got from the computer file video about Haskell I think it was called to the infinity and beyond so I'm gonna leave the link to this video in the description and also I'm gonna put it in the chat if you're interested so let me find out computer file to the infinity infinity I think yeah - doesn't finish in beyond so I really recommend you to take a look at that specific video where they implemented that exact example but in Haskell so I'm not gonna implement it in Haskell instead you can just watch this video but we're going to implement that example in typescript but in a similar style that's right [Music] let's try to do that let's try to do that all right so we need a function I guess I want to find my separator here here it is yeah well we're doing lazy CP yes and so we're gonna have a function sieve that takes lazy list of numbers and returns a lazy list of numbers so we need to know what exactly it does it will take the head of the list and filled a filter out everything in the in detail that is divisible by the head and it's gonna do that recursively yes take the head take the tail filter tail filter out everything that is divisible by head and do that recursively and see if again this is how we're gonna do that I really recommend to watch at the computer file video because they also have visualizations of that process so it might be helpful to understand all right so let's actually quickly do that [Music] first of all we're gonna force the axis here's the pairs and there is nothing to see if if pair is dull so we're gonna say if pair is no well sorry there is nothing to see I really hope I pronounced it correctly anyway if it's not know what we do we take the tail and we filter it and we need to filter out everything that is divisible by the head but we need to force the head first so here's the player head so we first the head we have the head X is the element from the tail so we take X mod y equal equal zero so but we need to filter out everything that is divisible bye-bye head so we're gonna put inversion here so yeah so the tail is properly filtered out and what we're going to do with that tail we're gonna see it again so you see it's gonna recursively take the head filter see and that sieve is gonna take the head of the filter to the thingy and gonna filter again and see filter again in sieve and by that it will generate a list of prime numbers because only prime numbers will survive these very intensive process of saving yes because they are not divisible by anything but themselves yeah pretty much the idea pretty much the idea and of course here we're gonna just return return that and look at the entire employment Asian this is basically it surprisingly and let's introduce a variable called prime and prime numbers are going to be simply sieve range to arrange to generates an infinite list from 2 to infinity and then we see vit which will make to the first prime number and starting from that it will you know it will generate prime numbers ok and let's try to take ten elements out of prime numbers list and print them and see if what we actually generate 10 prime numbers will do that or will it fail well it probably will generate an unreadable compilation error yes I was right well it was readable at least because I know exactly what I was going on I forgot about ultimate Haskell experience yes there's the ultimate Haskell experience yes now we're going into the realm of unreadable errors nice so it's kind of similar I think I forgot like semicolon somewhere here no it was not a semicolon let's think about again this value has to be not lazy that's why we have to force this thing here yes I think all right and it did didn't generate anything nice even though we explicitly asked it to oh because it I guess we screwed up somewhere here's the lazy valium I force the payer if it's empty it's empty list okay I force the head and I use the head to filter out the list but you know what I forgot I forgot to here to keep the head yes I just dropped the head I'm using the head but I just dropped it I just dropped it so that means I need to continue generating the list so head this has to be put back in place and the tail is gonna be deceived and that does not require forcing that see yes that's where I made a mistake can it generate ten prime numbers now it can in fact it did are those prime numbers does this list of ten numbers contained and non prime numbers anybody Tony I think it does contain all the prime numbers but what if we remove take if we remove take it should keep generating prime numbers because prime number is an infinitive a prime is an infinite list of prime numbers which is lazy that's why it can be infinite let's find out so what keep generating something and notice how it's I think it slows down over time I think it slows down let's actually make it like take a random number from here and check these Prime oh nice Thank You Amazon very cool okay check if number is prime online you know what I think there should be way easier way to check if it's a prime or not if I remember correctly Linux and UNIX operating system has a very interesting function called Factory I bet you didn't know that but there is a function called factor that factorizes your number and if you give it yes I know I know you didn't know that I didn't know like it's it's so underrated underrated program if you put a prime number there yes this is the only factor of prime number itself there you go so yeah we just proved that a random number from our generated list is a prime number so yeah this is how basically you can think in terms of lazy evaluation and this is basically how you have to turn your thinking inside out when you program in Haskell again this is not a silver bullet it's just an alternative way of programming a very interesting one I have to admit a very interesting one

Channel: Tsoding

Views: 33,208

Keywords: Programming, Coding, Functional Programming, Web Programming, Web Development, JavaScript, TypeScript, Haskell, Lazy Evaluation, Emacs, Linux, Node.js, Rust, Deno, Tutorial

Id: E5yAoMaVCp0

Length: 82min 25sec (4945 seconds)

Published: Sun Feb 09 2020