Solving tournament problems in Haskell

Good day to all harazhiteli
Here is an article dedicated to the fairly well-known, but not very popular Haskell language. In it, I would like to show an example of solving a simple Haskell tournament problem. I hope that this article will help novice Haskele programmers to take the first steps to writing a full-fledged program.



As an example of a program, I selected a task from the Codeforces site. This task is very simple, which means we can focus directly on the language we want to learn, in addition, Codeforces supports sending solutions in Haskell, which means that we can test our solution on their tests. Let's start by reading the statement of the problem.
')

Two numbers are given. As long as they are both greater than zero, the same operation is performed with them: less is subtracted from a larger number. If the numbers are equal, then another is subtracted from one. For example, from a pair (4.17) in one operation a pair (4.13) is obtained, and from a pair (5.5) a pair (0.5).

You are given a certain number of pairs (a _i , b _i ). How many operations will be performed for each of them?

So, we need for each pair of numbers to count the number of operations on them to achieve the result. This corresponds to the following function signature.

solve :: Int -> Int -> Int solve = undefined 

I wrote down the implementation of the function as undefined, which will allow the program to check for compilation errors. I leave the full implementation of the function to the readers as an exercise.

Our program should read the input data. The first line contains one number n, specifying the number of pairs of numbers for which you want to output an answer (calculate the value of the solve function). Reading the number can be implemented as follows

 main = do nStr <- getLine let n = (read nStr :: Int) 

For simplicity, we will use do-notation (although it is considered harmful ). Those who are not familiar with this notation may still consider that it allows you to write a function in a style reminiscent of imperative. First we read the string, then we convert it into a number and put it into the variable n. This is an incomplete implementation of the main function, it has yet to finish writing.

Next you need to read n lines, each of which contains a pair of numbers for which you want to output the value of the function solve. Here it is necessary to repeat one action (count 2 numbers in a line, count the value of the function solve, display the result) n times. To begin, we implement this action.

 printSolution :: IO () printSolution = do numsStr <- getLine let nums = map (read :: String -> Int) $ words numsStr print $ solve (nums!!0) (nums!!1) 

@leventov suggested a beautiful way to read numbers using pattern matching

 printSolution :: IO () printSolution = do numsStr <- getLine let [n1, n2] = map read $ words numsStr print $ solve n1 n2 

Notice that here I did not explicitly specify the type of the function read. The system of Haskell types will be able to deduce it itself, since the solve function accepts parameters of the Int type, therefore it does not make much use of the code (thanks to dima_mendeleev ).

The function reads a line (getLine), breaks it up into parts (words), converts each part into a number (map (read :: String -> Int)), and then prints the value of the solve function called with the read parameters (print $ solve (nums !! 0) (nums !! 1)). I recommend memorizing the words and read functions, it is very convenient to use them for working with input, and indeed with strings.

Then you need to implement a repetition of this action n times. In imperative languages, this would be recorded in a cycle, but our language is functional, so we will resort to using recursion.

 printNSolutions :: Int -> IO () printNSolutions 1 = printSolution printNSolutions n = do printSolution printNSolutions (n-1) 

Pass an Int type parameter to the function - the number of repetitions. If the number is 1, then you just need to call printSolution once, but if it is greater than 1, then you need to call printSolution 1 time, and then repeat the call n-1 more times. Values ​​of n less than 1 cannot be accessed by condition, so I do not do any additional checks on the input data either here or in other places where data entry is under way.

All that is left to do is call the function `printNSolutions` with the argument n already read in the main function

 main = do nStr <- getLine let n = (read nStr :: Int) printNSolutions n 

Now the main function is added to the end, but you can make it a bit shorter (and again, the type of the read function can be clearly not written)

 main = do nStr <- getLine printNSolutions $ read nStr 

Or completely abandon the do-notation

 main = getLine >>= (printNSolutions . read) 

That's it, we wrote a program in Haskell! Finally, I will provide its full code (if you want to do an exercise, do not open the listing, but write the implementation yourself and test it in Codeforces)