Добрый день всем Хабражительникам Перед вами статья, посвященная достаточно известному, но не очень популярному языку Haskell. В ней я хотел бы показать пример решения простой турнирной задачи на Haskell. Надеюсь, что эта статья поможет начинающим хаскелл-программистам сделать первые шаги к написанию полноценной программы.
В качестве примера программы я выбрал задача с сайта Codeforces. Эта задача очень проста, а это значит, что мы можем сосредоточиться непосредственно на языке, который хотим выучить, кроме того, Codeforces поддерживает отправку решений на Haskell, а это значит, что мы можем протестировать наше решение на их тестах.
Начнем с прочтения постановки задачи.
Даны два числа.Итак, для каждой пары чисел нам нужно посчитать количество операций над ними для достижения результата.Пока оба они больше нуля, над ними производится одна и та же операция: из большего числа вычитается меньшее число.
Если числа равны, то из одного вычитается другое.
Например, из пары (4,17) за одну операцию получается пара (4,13), а из пары (5,5) пара (0,5).
Вам дано определенное количество пар ( я ,б я ).
Сколько операций будет выполнено для каждого из них?
Это соответствует следующей сигнатуре функции
Реализацию функции я написал как неопределенную, что позволит мне проверить программу на наличие ошибок компиляции.solve :: Int -> Int -> Int solve = undefined
Полную реализацию функции оставляю в качестве упражнения для читателей.
Наша программа должна прочитать входные данные.
В первой строке записано одно число n, указывающее количество пар чисел, для которых нужно отобразить ответ (вычислить значение решающей функции).
Чтение числа можно реализовать следующим образом main = do
nStr <- getLine
let n = (read nStr :: Int)
Для простоты мы будем использовать обозначение do (хотя это считается вредным ).
Те, кто не знаком с этой нотацией, могут подумать, что она позволяет написать функцию в стиле, напоминающем императив.
Сначала мы читаем строку, затем преобразуем ее в число и помещаем в переменную n. Это незавершенная реализация основной функции, ее еще нужно доделать.
Далее вам нужно прочитать n строк, каждая из которых содержит пару чисел, для которых нужно вывести значение решающей функции.
Здесь нужно повторить одно действие (посчитать 2 числа в строке, вычислить значение решающей функции, вывести результат) n раз.
Сначала давайте реализуем это действие printSolution :: IO ()
printSolution = do
numsStr <- getLine
let nums = map (read :: String -> Int) $ words numsStr
print $ solve (nums!!0) (nums!!1)
@leventov предложил хороший способ чтения чисел с помощью сопоставления с образцом.Функция читает строку (getLine), разбивает ее на части (слова), преобразует каждую часть в число (map (read::String -> Int)), а затем печатает значение функции решения, вызванной с параметрами чтения (выведите $solve (nums !!0) (nums!!1)).
printSolution :: IO () printSolution = do numsStr <- getLine let [n1, n2] = map read $ words numsStr print $ solve n1 n2
Обратите внимание: здесь я явно не указал тип функции чтения.Система типов Haskell сможет вывести это сама, поскольку функция решения принимает параметры типа Int, поэтому загромождать код смысла нет (спасибо Дима Менделеев ).
Рекомендую запоминать слова и функции чтения; их очень удобно использовать для работы с вводом, да и вообще со строками.
Затем вам нужно реализовать повторение этого действия 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 = do
nStr <- getLine
let n = (read nStr :: Int)
printNSolutions n
Теперь основная функция написана до конца, но можно сделать ее немного короче (и опять же не обязательно явно прописывать тип функции чтения) main = do
nStr <- getLine
printNSolutions $ read nStr
Или вообще отказаться от do-нотации main = getLine >>= (printNSolutions .
read)
Вот и все, мы написали программу на Хаскеле! Напоследок приведу его полный код (если вы хотите выполнить упражнение, не открывайте листинг, а напишите реализацию самостоятельно и протестируйте ее в системе 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 #haskell #функциональное программирование #Функциональное программирование #учебник #codeforces #программирование #haskell #Функциональное программирование
-
Перевод Rss В Yahoo! Трубы
19 Oct, 24 -
Две Интересные Проблемы
19 Oct, 24 -
Google Adsense: Аутентификация Сайта
19 Oct, 24
