Про хаскелль для самых маленьких на примере задачи с codefights

Если вы интересуетесь функциональным программированием или даже пытаетесь его потихоньку освоить то вам, наверняка, не раз приходилось слышать, что главным отличием от привычного вам императивного подхода является тот факт, что программы строятся от общего к частностям, а не наоборот. Т.е. сначала вы определяетесь с тем, что вы хотите получить, а потом уже — как этого достичь. Такая простая, казалось бы, мысль обычно не дает мозгу покоя и вызывает множественные фрустрации в попытках написать что-нибудь полезное. Если эта история про вас, или вам просто интересно немного научится хаскеллю и ФП продолжайте чтение и я покажу вам как все просто. Статья в стиле «некогда объяснять, пиши».

Идея этой статьи пришла мне в голову на следующее утро после завершения состязания на codefights.com, где мне нужно было срезать еще 10 символов, чтобы получить самое короткое решение. Я посмотрел другие решения и увидел, что если бы свое решение я заканчивал не в пять утра и не забыл бы применить один хак, то оно оказалось бы самым коротким, и, что важнее всего, сохранило бы простоту и понятность. Постойте ка, подумал я, если объяснить пару нюансов любому программисту писавшему на яваскрипте или питоне он тут же врубится, пойду напишу об этом статью на Хабр!

Итак, задача. Есть Чувак. Чувак любит приходить на железнодорожную станцию и считать вагоны в проходящем каждый день поезде. Любит он это настолько, что приходит туда каждый день. Иногда, Чувак идет играть в боулинг и пить белого русского. И тогда, он может выпадать из реальности на несколько дней. Когда Чувак приходит в себя то первым делом интересуется, сколько же вагонов он пропустил. Нужно помочь Чуваку в этих подсчетах. Известно, что количество вагонов в поезде непостоянно. В первый день месяца поезд состоит только из одного вагона:

В каждый последующий день вагонов становится на два больше:

И так до начала следующего месяца. Итого: месяц month ∈ [1..12], день day ∈ [1..максимальное количество дней в этом месяце], количество дней проведенных в боулинге n ∈ [0..365], нужно вернуть целое число означающее сколько поездов пропустил Чувак. Например, month=1, day=1, n=1 ответ 1. Потому, что в первый день любого месяца поезд состоит из одного вагона и пропущен только один день т.е. тот самый первый день. Для month=5, day=1, n=5 ответ 25:

Для month=2, day=1, n=30 ответ будет 788 (можно, я не буду рисовать?) и т.д.

Ставьте хаскелль, расчехляйте любимый редактор, создавайте пустой файл dude.hs, делайте его исполняемым chmod +x dude.hs (мы не будем ничего компилировать, хаскелль прекрасно работает как скриптовый язык), в самом начале файла пишите #!/usr/bin/env runhaskell и мы готовы начинать.

#!/usr/bin/env runhaskell
dude month day n = …

dude — имя функции, все что дальше — аргументы, после равно идет тело функции (котороые мы сейчас будем придумывать).

Что мы хотим получить в результате? В результате мы хотим получить число пропущенных вагонов. Чему равно это число? Сумме вагонов за все дни, что Чувак не приходил на станцию. Значит, в итоге нам нужна сумма. Ее мы будем искать в прелюдии — стандартной бибилотеке по-умолчанию импортируемой во все модули. Если будем искать хорошо, найдем функцию sum — она суммирует все числа в списке. И заметьте, я ничего не говорю про типы, монады и чем вас там еще пугали. На самом деле, хаскелль намного проще и очень похож на современный яваскрипт (как тут не вспомнить пост Льва Валкина о том, как из яваскрипта выбросить синтаксический мусор и получить, в итоге, хаскелль). Впрочем, мы замечтались:

dude month day n = sum …

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

dude month day n = sum [1, 3, 5, 7, 9]

Запускаем: ./dude.hs. Не работает? Ругается матом? Правильно, потому, что нам нужна точка входа, функция main. Которая, за одно, еще должна преобразовать наш ответ в строку и напечатать на экране. Вот такая функция нам подойдет:

main = putStrLn (show (dude 1 1 1))

Воу-воу-воу! Столько скобочек сразу, почти что лисп. Их пришлось расставить так, потому, что вызов функций в хаскелле лево-ассоциативен. Т.е. если бы мы не расставили скобочки и написали бы:

main = putStrLn show dude 1 1 1

Хаскелль решил бы, что мы хотим сделать так:

main = ((putStrLn show) dude) 1 1 1

Что не соотвествует истине. В правильной функции main мы сначала вызываем чувака с тремя аргументами (которые, на текущий момент, счастливо игнорируются), потом, при помощи show преобразуем результат работы этой функции в строку и только затем печатаем на экран строку при помощи putStrLn. В неправильной функции putStrLn пытается напечатать функцию show (безуспешно, как можно догадаться), а потом результату работы (который должен оказаться, но никогда не окажется, функцией) в качестве единственного аргумента кормится функция dude, и вот результату работы этой содомии (который тоже должен оказаться функцией) кормятся те три аргумента — так не работает. Поэтому, мы и расставили скобочки. Есть еще замечательный оператор $ который как бы говорит хаскеллю: «сначала выполни все, что правее меня, а результат подставь на мое место». Поэтому, правильную функцию main мы можем переписать вот так:

main = putStrLn $ show $ dude 1 1 1

Все как в сказке про репку. Хотим печатать, но сначала нужно преобразовать в строку. Хотим преобразовать в строку, но прежде, вызвать чувака. Чувак берет три аргумента и возвращает сумму. Ну а сумма легко преобразуется в строку, которая легко печатается на экране. Шикарно!

Возвращаемся к нашим вагонам. Теперь, если запустить ./dude.hs мы получим 25 — сумму чисел в нашем тестовом списке. Как составить настоящий список? Напомню, мы хотим получить список длин вагонов в те дни, что Чувак не приходил на вокзал. Ну так может составим список вагонов на каждый день года, а потом просто выберем из него те дни, что чувака не было? Не знаю как вам, но мне нравится эта идея. Лезем в прелюдию и находим функцию take:

dude month day n = sum $ take n $ …

Ну хорошо, мы взяли n дней из списка, но это будут первые n дней первого месяца года т.к. функция take берет первые n значений из начала списка. Не годится. Надо отступить day дней от начала месяца (на самом деле day - 1 так как первый день отсутствия тоже считается). Отступать будем сжигая Москву и при помощи drop:

dude month day n = sum $ take n $ drop (day - 1) $ …

А потом еще month - 1 месяцев от начала года. Но этот факт мы возьмем в расчет чуть позже. Так как здесь мы имеем дело с днями мы не можем просто так отступить несколько месяцев. В каждом месяце свое число дней не поддающееся никакой логике и здравому смыслу. Поэтому давайте-ка, где-нибудь на новой строчке, напишем список дней в каждом месяце, пригодится:

months = [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]

И знаете что, ведь может так получится, что Чувак начнет 31го а закончит только 9го. Придется учесть этот факт в расчетах. Перескакивать с конца списка (декабрь) в начало (январь). Лень. Лучше превратим этот список в бесконечный и всегда будем идти по нему только вперед:

months = cycle [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]

Функция cycle делает из конечного списка бесконечный циклически повторяя исходный список. Устроена она, примерно, так:

cycle list = list ++ cycle list

Где ++ оператор складывающий два списка в один, а list — наш список, который мы хотим сделать бесконечным. Как такое возможно, спросите вы? Это ведь бесконечная рекурсия! Память конечна, время конечно, но рекурсия и список, который она порождает, нет? Да, все так. Дело в том, что хаскелль ленив (как и программисты, какое совпадение) и поэтому не будет ничего делать до тех пор, пока результаты не понадобятся (прокрастинация?). Поэтому, тут возможно работать с бесконечными списками (а так же деревьями, и что там еще бывает бесконечным; человеческая глупость?), но ровно до тех пор, пока мы работает над конечным подмножеством такого списка. Если бы мы написали так:

months = cycle [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
dude month day n = sum months --бесконечный чувак

То хаскелль умер бы через 4 секунды (проверьте сами, кстати), из за превышения времени выполнения; потому, что суммировать элементы бесконечного списка нужно бесконечно долго. Хорошо, что из нашего бесконечного списка мы берем только n дней!
Давайте теперь перейдем к самому главному, давайте из списка месяцев сделаем список дней, а потом посчитаем сколько вагонов в каждом из них. Чтобы перейти от чего то одного (списка месяцев) к чему-то другому (списку дней) во всей вселенной используют map:

months = cycle [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
to_days max_days = …
dude month day n = sum $ take n $ drop (day - 1) $ map to_days months

Первый аргумет функции map — функция которая преобразует месяц в список дней, нам еще предстоит ее придумать. Второй аргумет — наш бесконечный список. Не волнуйтесь, map тоже ленив и не будет идти по списку дальше, чем нам нужно.
Теперь совсем просто:

months = cycle [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
to_days max_days = [1..max_days]
dude month day n = sum $ take n $ drop (day - 1) $ map to_days months

[1..max_days] это такой синтаксический сахар, который создаст список всех целых чисел от 1 до max_days. Если запустить программу сейчас то снова ничего не заработает. Дело в том, что функция to_days которую вызывает map получает от него на вход всего одно число — элемент из списка дней в месяце, а возвращает целый список дней в этом месяце. Получается список в списке:

Можно вызывать concat и расплющить список в одномерный:

months = cycle [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
to_days max_days = [1..max_days]
dude month day n = sum $ take n $ drop (day - 1) $ concat $ map to_days months

А можно сразу использовать concatMap:

months = cycle [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
to_days max_days = [1..max_days]
dude month day n = sum $ take n $ drop (day - 1) $ concatMap to_days months

Осталось чуть-чуть. Давайте теперь из списка дней сделаем список вагонов в этот день. В условии написано, что в первый день месяца у поезда один вагон, а потом каждый день прибавляется по два. Запишем это на отдельной строчке:

number_of_wagons x = x*2 - 1

Где x — номер дня в месяце, разумеется. Мапаем эту функцию на список дней из предыдущего шага, и не забываем отступить month - 1 месяцев:

#!/usr/bin/env runhaskell
months = cycle [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
to_days max_days = [1..max_days]
number_of_wagons x = x*2 - 1
dude month day n = sum $ take n $ drop (day - 1) $ map number_of_wagons $ concatMap to_days $ drop (month - 1) months
main = putStrLn $ show $ dude 1 1 1

Запускаем. Работает. Ответ 1. Пробуем другие значения, например 3 2 4. Ответ 24. Давайте теперь проверим нашу гипотезу про 31е декабря. Исходные данные: 12 31 10, ответ 142. Многовато! Однако, ответ верный.

---

Где же самое короткое решение, спросите вы? Там такое дело, в общем, есть слово на букву м. И я пока не придумал как объяснить его в таком же формате. Ну и вообще, писанины много вышло, для одной статьи был бы перебор. В следующий раз.

Автор: mynameisdaniil

Источник