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

Доброго времени суток всем хабражителям
Перед вами статья, посвященная довольно известному, но не сильно популярному языку 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)

@leventov предложил красивый способ считывания чисел при помощи сопоставления с образцом

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

Заметьте, что здесь я не указал явно тип функции read. Система типов Хаскеля сможет вывести его сама, поскольку функция solve принимает параметры типа Int, поэтому загромождать код особого смысла не имеет (спасибо dima_mendeleev).

Функция считывает строку (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 дописана до конца, однако можно сделать ее чуть короче (и опять, тип функции read можно явно не писать)

main = do
     nStr <- getLine
     printNSolutions $ read nStr

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

main = getLine >>= (printNSolutions . read)

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