23 января 2013 в 13:26

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

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



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

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

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


Итак, нам нужно для каждой пары чисел посчитать число операций над ними для достижения результата. Это соответствует следующей сигнатуре функции
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)
Листинг
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)

+3
4576
8
Shekeen 4,3

Комментарии (7)

+1
dima_mendeleev, #
Я конечно фанат, Haskell, но вы как-то плохо его популяризируете =)
Уберите пожалуйста эти пугающие типы у read, они легко выводятся из использования (solve и printNSolutions принимают Int).
Там где вы считываете два числа можно сразу их распаковать:
let n1 : n2 : [] = map read $ words numsStr
А конец итерации лучше заменить на:
printNSolutions 0 = return ()
0
Shekeen, #
Не ставил своей целью популяризацию языка, скорее хотел помочь новичкам, показав, что такие программы, обычно пишущиеся на императивных языках, не так уж и сложно пишутся и на Хаскеле.

Про типы у read согласен, выглядит страшно, но я не могу избавиться от параноидальной привычки явно их указывать) Да и так более наглядно, я думаю.

А про такой удобный способ распаковки даже не подумал, спасибо за совет!
Добавлю в пост ваши замечания.

+2
leventov, #
let n1 : n2 : [] = ...
можно заматчить и так:
let [n1, n2] = ...
0
dima_mendeleev, #
Круто, спасибо!
*на самом деле я тоже в Хаскеле новичок=)
+2
Wolong, #
Как вы находите время так воду лить во время соревнования, обычно выходит что-то вроде:
main = putStr.unlines.map(show.solve.map read.words).tail.lines=<<getContents
	where { solve (0:_) = 0; solve (_:0:_) = 0; solve (a:b:_) = if a >= b then (div a b) + solve [b,(mod a b)] else solve [b,a]; }


Задача та же самая.
0
Shekeen, #
Я еще новичок в Хаскеле, поэтому пока не рискую использовать его во время реальных контестов. Вот и решаю задачи со старых контестов для того, чтобы лучше изучить Хаскель.
0
Darkus, #
main = getLine >>= printNSolutions . read, например.

Только зарегистрированные пользователи могут оставлять комментарии.
Войдите, пожалуйста.