Treating Lists as Monads — HaskellRank Ep.11

welcome to the Husky rink the series where we solve programming problems but you know in high school the next problem is going to be in the new experiment going to be electronics shop Monica wants to buy a keyboard and a USB Drive from her favorite electronics store the store has several models of which Monica wants to spend as much as possible for the two items given her budget given the price list for the store's keyboards and USB drives and Monica's budget fine entering the amount of money Monica will spend if she doesn't have enough money to both a keyboard and USB Drive print -1 instead she will buy only the two required items for example suppose she has a budget of 16 to spend 3 types of keyboards cost forty fifty and sixty two USB drives cost five eight and twelve she could purchase a forty keyboard plus twelve drive which is 42 in total or fifty keyboard plus eight drive which is fifty eight in total she chooses the later she can't buy more than two items so she can spend only sixty all right let's take a look at the input format the first line contains three space separated injuries B N and M her budget the number of keyboards and number of USB drives second line contains ends by separated integers keyboards and the third line contains M space separated integers drives so the first thing of that will have to do I think we need to find all of the possible combination of pairs of keyboards and drives so let's bring some input data to our shell first line contains keyboards so this is are going to be our keyboards and drives how to find all the possible combination of pairs of these two this is the way I see is to probably use something like list comprehension so we tear right through all the keyboards and through all of the drives and we just generate all of the possible pairs of them something like that but I'm going to show you a really interesting trick that you can use to find and reuse existing functions so let's think of what function we need to generate all of the possible pairs we need some kind of function that takes a list of one type a list of another type and just combines them together so list is actually a kind of a generic type it's parameterize by the type of its element so what if we abstract it out what if we do something like that so instead of using brackets we're gonna use this type so some kind of abstract a generic type which is also parameterize by this type so now we have a function that that takes two containers and produces this container but there's not a say you have to combine them into pairs it can combine them into anything if you have function that takes a and B and squashes them to C so we need to find something like that so let's actually open website called has killed org slash Google which is very interesting service that allows you to search haskell api by its signatures and let's just put that signature there and see what we can find and this is first thing that we found lift em 2 it has exactly the signature that we want to produce cartesian product but what's interesting instead of lists it uses something called monad and what is a Minette and how we can use it is completely irrelevant for the discussion the only thing that is important is that list is a Monnett and so that means that particular function can be used on lists to enable that particular function to enable that particular function we need to import control monad and you will be able to actually use it since we need to pack the elements of pairs into triples so we're going to use this as a function so if you take a look at the signature of this particular operation it's a function that takes two elements and returns a pair of these two things you can even double check that it works so you can construct queries like that or like that so it doesn't matter how we do that but what's cool about kama is that then you can use it as a function and pass it to other functions to pass it kama here indicating how we want to pack our payers then we provide key words and then we provide drives yeah and we already lost all of them because we reloaded the repo okay let's find all of these things and recreate them I think the easiest way would be to actually put them into the file so every time I reload the module they are always there I think it's gonna be a way easier to work with okay let's try to apply a lift m2 to them keyboards and drives and as you can see it also generates all of the possible pairs so this is how quite easily using services like Google you can find code in standard library or in third-party libraries that you can use in your Haskell programs which is which is kind of nice which is kind of nice and we found a way to actually produce a cartesian product on two lists if we treat lists as monads which they are hopefully this is how we generate the payers but what's interesting is that we don't really care about them being payers we only hear about their total price so instead of packing them into cheapest why not just sum them up and this is the sums of all of the combinations of keyboards and drives next we want to filter everything that goes over the budget so basically those are lists of all possible amount of money that Monica can pay for drive and keyboard so we want to filter out everything that goes over her budget so let's actually put budget into file here so it will be available in repo I think the test budget is 10 so let's filter everything that less or equal to the budget and yeah we filtered out things like 11 because it's obviously over the budget because the budget was 10 once we have everything that fits into the budget we want to find the maximum obvious thing in that situation would be just throw a maximum function here which is 9 but here lies the problem what if nothing fits in the budget what if your budget is actually one filter will generate an empty list and what happens when you apply maximum to empty list we get an error but in this situation instead of like throwing an arrow we actually have to print minus one according to the description so how to do that instead of just throwing blindly maximum to this solution I want to sort everything in a descending order I can not because I didn't have survived because it's like 80 in data at least modulus quickly and I don't have a function whew but I have filled so you see when you sort this result in the descending order the answer is going to be the first element but if after the filter you get an empty list it's not going to throw an error it will just return an empty list which simplifies handling this situation but again you cannot just easily head the result of sorting because in case of empty list you again gonna get an error so to handle that situation we're gonna use an autistic function called list to maybe which is located in data maybe module it takes a list and returns a maybe of a so second look at how it works if you convert an empty list maybe you get nothing but if you convert an actual list with several elements it takes the first element of that list and wraps it into just and this is exactly what we need so instead of taking the head we're gonna do least two maybe and now when there is nothing that fits the budget we get nothing and when we have an actual solution we get just that solution and it only remains to unwrap maybe to unwrap that maybe we're gonna use from maybe function which takes the default value maybe and unwraps it and in case of nothing it returns the default value let me show you from maybe five nothing will return five just six returns six that enables us with using from maybe and in case of nothing according to the requirements we have to return minus one so it's nine when it fits the budget and it's minus one when does it fit the budget and guess what this is the final entire solution of this problem fits nicely into a single line so let's actually try to wrap it into a function the function is going to be solve which takes the budget takes the prices of the keyboards the prices of the drives and returns the answer budget keyboards drives and let's just copy paste it right here let's format it nicely so it looks a little bit better and remove this stays data that we don't need anymore so now we have a boiled solution but again this is just a solution this is just a pure function we need to make it an interactive program the input format of this particular problem is a little bit complicated so we're going to use our usual get list trick to parse the input line by line so this time I want to use some function notation where I treat the result of get line as a functor and f map it with words and map treat and now let's implement the main function so on the first line of the input we get B and in M and what's interesting is that keyboards and drives are fully located on their separate lines which makes it possible for us to parse them without knowing m and M so we don't need these two things and once we have all of the input data we can just solve it solve aspheric they can remember returns integers that means we'll have to convert it to a string and one since converted to a string we bring it to the standard output so this thing can piles and let's try to submit that let's try to submit that let's put it here let's see if it compiles in their side compile so not submit that as usual and see what will happen and see what will happen and yeah it works next problem [Music]

Channel: Tsoding

Views: 9,348

Rating: 4.9577837 out of 5

Keywords: Haskell, Functional Programming, Emacs, Linux, NixOS, HackerRank, Coding Problems, Problem Solving

Id: ofUAlkYHFsI

Length: 11min 2sec (662 seconds)

Published: Mon Jan 14 2019

Reddit Comments

[u/wewbull]

It would also be good to look at do notation for this, and Applicative (liftA2 and <*>).

[u/heisenbug]

Why not (-1:) before sorting?

[u/pokemonplayer2001]

"I don't have function filp" - made me laugh out loud. :)