Решение турнирных задач на языке Haskell

В качестве примера программы я выбрал задачу с сайта Codeforces. Эта задача очень простая, а значит мы сможем сосредоточиться непосредственно на языке, который мы хотим изучить, кроме того Codeforces поддерживает отправку решений на языке Haskell, а это значит, что мы сможем протестировать свое решение на их тестах. Начнем с того, что прочитаем условие задачи.

Заданы два числа. До тех пор, пока оба они больше нуля, с ними производят одну и ту же операцию: из большего числа вычитают меньшее. Если числа равны, то из одного вычитают другое. Например, из пары (4,17) за одну операцию получается пара (4,13), а из пары (5,5) пара (0,5).

Вам задано некоторое количество пар (a_i, b_i). Сколько операций будет выполнено для каждой из них?

Итак, нам нужно для каждой пары чисел посчитать число операций над ними для достижения результата. Это соответствует следующей сигнатуре функции

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

Реализацию функции я записал как undefined, что позволит проверить программу на наличие ошибок компиляции. Полноценную реализацию функции оставляю читателям в качестве упражнения.

Наша программа должна считать входные данные. В первой строке содержится одно число n, задающее количество пар чисел, для которых необходимо вывести ответ (посчитать значение функции solve). Считывание числа можно реализовать следующим образом

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

Для простоты будем использовать do-нотацию (хотя она и считается вредной). Те, кто не знаком с этой нотацией, может пока считать, что она позволяет записывать функцию в стиле, напоминающем императивный. Сначала считываем строку, затем конвертируем ее в число и заносим в переменную n. Это незаконченная реализация функции main, ее еще предстоит дописать.

Дальше нужно считать n строк, каждая из которых содержит пару чисел, для которых нужно вывести значение функции solve. Здесь необходимо повторить одно действие (считать 2 числа в строке, посчитать значение функции solve, вывести результат) n раз. Для начала реализуем это действие

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

Функция считывает строку (getLine), разбивает ее на части (words), преобразует каждую часть в число (map (read :: String -> Int)), а затем распечатывает значение функции solve, вызванной со считанными параметрами (print $ solve (nums!!0) (nums!!1)). Рекомендую запомнить функции words и read, их очень удобно использовать для работы с вводом, да и вообще со строками.

Затем нужно реализовать повторение этого действия n раз. В императивных языках это записывалось бы через цикл, но у нас язык функциональный, поэтому прибегнем к помощи рекурсии

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

Передаем функции параметр типа Int — число повторений. Если число равно 1, то надо просто один раз вызвать printSolution, если же оно больше 1, то надо вызвать printSolution 1 раз, а затем повторить вызов еще n-1 раз. Значений n меньших 1 нам по условию достаться не может, поэтому я не делаю никаких дополнительных проверок входных данных ни здесь, ни в других местах, где идет работа с вводом данных.

Все, что осталось сделать, — это вызвать функцию `printNSolutions` с аргументом n, уже считанным ранее в функции main

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

Теперь функция main дописана до конца, однако можно сделать ее чуть короче

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

Или вовсе отказаться от do-нотации

main = getLine >>= (printNSolutions . (read :: String -> Int)) 

Вот и все, мы написали программу на языке Haskell! Напоследок я приведу ее полный код (если вы хотите сделать упражнение, не открывайте листинг, а напишите реализацию самостоятельно и протестируйте в системе Codeforces)

module Main where  solve :: Int -> Int -> Int solve 0 _ = 0 solve _ 0 = 0 solve a b       | a >= b = (a `div` b) + solve b (a `mod` b)       | otherwise = solve b a  printSolution :: IO () printSolution = do               numsStr <- getLine               let nums = map (read :: String -> Int) $ words numsStr               print $ solve (nums!!0) (nums!!1)  printNSolutions :: Int -> IO () printNSolutions 1 = printSolution printNSolutions n = do                   printSolution                   printNSolutions (n-1)                  main = do      nStr <- getLine      printNSolutions $ (read nStr :: Int) 

haskell, хаскель, functional programming, функциональное
программирование, tutorial, codeforces