About Haskell for the smallest on the example of the problem with codefights

If you are interested in functional programming or even try to master it slowly, then you probably have heard more than once that the main difference from the usual imperative approach is the fact that programs are built from general to particular, and not vice versa. Those. first you decide what you want to get, and then how to achieve it. Such a seemingly simple thought usually doesn’t give the brain peace of mind and causes multiple frustrations in trying to write something useful. If this story is about you, or you are just wondering, learn a bit of Haskell and OP, continue reading and I'll show you how simple it is. An article in the style of "no time to explain, write."

The idea of ​​this article came to my mind the next morning after the end of the contest on codefights.com , where I had to cut off another 10 characters to get the shortest solution. I looked at other solutions and saw that if I hadn’t finished my decision at five in the morning and had not forgotten to apply one hack, it would have been the shortest, and, most importantly, would have kept its simplicity and clarity. Wait a minute, I thought, if you explain a couple of nuances to any programmer who wrote in javascript or python, he got it right then, I 'll go write an article about this on Habr !

So, the task. Got a Dude. The dude loves to come to the railway station and count the cars in a passing train every day. He loves it so much that he comes there every day. Sometimes, the Dude goes to play bowling and drink white Russian. And then, he may fall out of reality for several days. When the Dude comes to his senses, he first wonders how many cars he missed. Need help Dude in these calculations. It is known that the number of cars in the train is not constant. On the first day of the month, the train consists of only one car:

On each subsequent day, there are two more cars:

And so on until the beginning of the next month. Total: month month ∈ [1..12] , day day ∈ [1.. ] , the number of days spent in bowling n ∈ [0..365] , you need to return an integer meaning how many cars will miss Dude . For example, month=1, day=1, n=1 answer 1 . Because on the first day of any month the train consists of one carriage and only one day is missed. the very first day. For month=5, day=1, n=5 answer is 25 :

For month=2, day=1, n=30 answer will be 788 (can I not draw?), Etc.

Put Haskell , uncover your favorite editor , create an empty dude.hs file , make it executable chmod +x dude.hs (we will not compile anything, Haskell works fine as a scripting language), write #!/usr/bin/env runhaskell at the very beginning of the file #!/usr/bin/env runhaskell and we are ready to start (or just use the service .

 #!/usr/bin/env runhaskell dude month day n = … 

dude - the name of the function, all that goes on - the arguments, after which the body of the function (which we will now invent) goes equally.

What do we want to get as a result? As a result, we want to get the number of skipped wagons. What is this number? The amount of cars for all the days that Dude did not come to the station. So, in the end, we need a sum. We will look for it in the prelude - the standard default library imported into all modules. If we search well, we find the sum function — it summarizes all the numbers in the list. And note, I am not saying anything about types, monads, and what else they scared you about. In fact, haskell is much simpler and very similar to modern javascript (how can one not recall the post of Lev Valkin on how to throw out syntax garbage from javascript and get haskell as a result). However, we remarked:

 dude month day n = sum … 

Well, the amount we know how to find. Now we need a list of missing cars. Let's start, instead of this ridiculous ellipsis, we substitute the test list, and make sure that the program works at all. So, for example:

 dude month day n = sum [1, 3, 5, 7, 9] 

Run: ./dude.hs . Does not work? Swears? That's right, because we need an entry point, a main function. Which, for one, still has to transform our answer into a string and print on the screen. This function will suit us:

 main = putStrLn (show (dude 1 1 1)) 

Wow wow wow! So many braces at once, almost a lisp. They had to be placed like this, because the call of functions in Haskelle is left-associative. Those. if we had not placed the brackets and would have written:

 main = putStrLn show dude 1 1 1 

Haskell would decide what we want to do:

 main = ((putStrLn show) dude) 1 1 1 

What is not true. In the correct main function, we first call the dude with three arguments (which, for the moment, are happily ignored), then, with the help of show convert the result of this function into a string and only then print the string with putStrLn . In an incorrect function, putStrLn tries to print a show function (unsuccessfully, as you might guess), and then the result of the work (which should be, but never will be, a function) is fed as a single argument to the dude function, and here is the result of this sodomy (which also to be a function) those three arguments are fed - this does not work. Therefore, we placed brackets. There is another wonderful $ operator that says to Haskell: “first do everything right of me, and put the result in my place”. Therefore, we can rewrite the correct main function like this:

 main = putStrLn $ show $ dude 1 1 1 

Just like in a fairy tale about a turnip. We want to print, but first we need to convert to a string. We want to convert to a string, but before that, call the dude. The dude takes three arguments and returns the sum. Well, the amount is easily converted to a string that is easily printed on the screen. Gorgeous!

We return to our cars. Now, if we run ./dude.hs we get 25 - the sum of the numbers in our test list. How to make a real list? Let me remind you, we want to get a list of the lengths of cars in those days that Dude did not come to the station. Well, maybe we can make a list of cars for each day of the year, and then just choose from it those days that the dude was not? I do not know about you, but I like this idea. We climb into the prelude and find the function take :

 dude month day n = sum $ take n $ … 

Well, well, we took n days from the list, but these will be the first n days of the first month of the year, since The take function takes the first n values ​​from the beginning of the list. No good. It is necessary to retreat day days from the beginning of the month (in fact, day - 1 as the first day of absence is also considered). We will retreat burning Moscow and using drop :

 dude month day n = sum $ take n $ drop (day - 1) $ … 

And then another month - 1 month from the beginning of the year. But this fact we will take into account a little later. Since here we are dealing with days we cannot just retreat for several months. Each month has its own number of days beyond any logic and common sense. So let's, somewhere on the new line, write a list of days in each month, come in handy:

 months = [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31] 

And you know what, after all, it may happen that the Dude will start on the 31st and end only on the 9th. We'll have to take into account this fact in the calculations. Jump from the end of the list (December) to the beginning (January). Laziness. It is better to turn this list into an infinite one and we will always go forward only on it:

 months = cycle [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31] 

The cycle function makes an infinite list of the final list looping around the source list. It is arranged approximately as follows:

 cycle list = list ++ cycle list 

Where ++ operator adds two lists to one, and list is our list that we want to make infinite. How is this possible, you ask? This is an endless recursion! Memory is finite, time is of course, but the recursion and the list it generates is not? Yes, that's it. The fact is that Haskell is lazy (like programmers, what a coincidence) and therefore will not do anything until the results are needed (procrastination?). Therefore, it is possible to work here with endless lists (as well as trees, and what else is endless there; human stupidity?), But exactly as long as we work on a finite subset of such a list. If we wrote this:

 months = cycle [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31] dude month day n = sum months --  

That haskell would die after 4 seconds (see for yourself, by the way), due to exceeding the execution time; because to summarize the elements of an infinite list you need infinitely long. It’s good that from our endless list we take only n days!
Let's now move on to the most important thing, let's make a list of days from the list of months, and then we calculate how many cars are in each of them. To move from something one (list of months) to something else (list of days) in the entire universe, use the map :

 months = cycle [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31] to_days max_days = … dude month day n = sum $ take n $ drop (day - 1) $ map to_days months 

The first argument of the map function is a function that converts a month into a list of days, we still have to come up with it. The second argument is our endless list. Do not worry, the map also lazy and will not go further in the list than we need.
Now, quite simply:

 months = cycle [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31] to_days max_days = [1..max_days] dude month day n = sum $ take n $ drop (day - 1) $ map to_days months 

[1..max_days] is such a syntactic sugar that will create a list of all integers from 1 to max_days . If you run the program now, it will not work again. The fact is that the function to_days which the map causes it to receive from the input is only one number - an element from the list of days in the month, and returns a whole list of days in this month. It turns out the list in the list:

You can call concat and flatten the list into one-dimensional:

 months = cycle [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31] to_days max_days = [1..max_days] dude month day n = sum $ take n $ drop (day - 1) $ concat $ map to_days months 

And you can immediately use concatMap :

 months = cycle [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31] to_days max_days = [1..max_days] dude month day n = sum $ take n $ drop (day - 1) $ concatMap to_days months 

It remains a little bit. Let's now from the list of days make a list of cars on this day. The condition says that on the first day of the month the train has one car, and then two more are added every day. We write this on a separate line:

 number_of_wagons x = x*2 - 1 

Where x is the number of the day in the month, of course. Map this function to the list of days from the previous step, and do not forget to retreat a month - 1 month:

 #!/usr/bin/env runhaskell months = cycle [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31] to_days max_days = [1..max_days] number_of_wagons x = x*2 - 1 dude month day n = sum $ take n $ drop (day - 1) $ map number_of_wagons $ concatMap to_days $ drop (month - 1) months main = putStrLn $ show $ dude 1 1 1 

We start. Works. Answer 1 . We try other values, for example 3 2 4 . Answer 24 . Let's now test our hypothesis about December 31st. Baseline: 12 31 10 , the answer is 142 . Too much! However, the answer is correct.

Where is the shortest solution you ask? There is such a thing, in general, there is a word on the letter M. And I have not yet figured out how to explain it in the same format. Well, in general, a lot of writing has happened, for an article would be a bust. Next.