Доброго времени суток всем хабражителям
Перед вами статья, посвященная довольно известному, но не сильно популярному языку Haskell. В ней мне хочется показать пример решения простой турнирной задачи на языке 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
Автор: Shekeen
