Про хаскелль для самих маленьких на прикладі задачі з 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 day month n = ...

dude
— ім'я функції, все що далі — аргументи, після одно йде тіло функції (які ми зараз будемо придумувати).
Що ми хочемо отримати в результаті? В результаті ми хочемо отримати число пропущених вагонів. Чому одно це число? Сумі вагонів за всі дні, що Чувак не приходив на станцію. Отже, у підсумку нам потрібна сума. Її ми будемо шукати в прелюдії — стандартної бібілотеці за замовчуванням імпортованої в усі модулі. Якщо будемо шукати добре, знайдемо функцію
sum
— вона підсумовує всі числа в списку. І зауважте, я нічого не кажу про типи, монади і чим вас там ще лякали. Насправді, хаскелль набагато простіше і дуже схожий на сучасний яваскрипт (як тут не згадати пост Лева Валкина про те, як з яваскрипт викинути синтаксичний сміття і отримати, в результаті, хаскелль). Втім, ми замріялися:
dude day month n = sum ...

Добре, суму ми знаємо як знайти. Тепер потрібен список з пропущеними вагонами. Давайте, для початку, замість цього безглуздого трикрапки підставимо тестовий список, і переконаємося, що програма взагалі працює. Ось так, наприклад:
dude day month 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 day month n = sum $ take n $ ...

Ну добре, ми взяли
n
днів з списку, але це будуть перші
n
днів першого місяця року т. к. функція
take
бере перші
n
значень з початку списку. Не годиться. Треба відступити
break
днів від початку місяця (насправді
day - 1
так як перший день відсутності теж вважається). Відступати будемо спалюючи Москву і за допомогою
drop
:
dude day month 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 day month 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 day month 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 day month n = sum $ take n $ drop (day - 1) $ map to_days months

[1..max_days]
це такий синтаксичний цукор, який створить список всіх цілих чисел від 1 до
max_days
. Якщо запустити програму зараз то знову нічого не запрацює. Справа в тому, що функція
to_days
яку викликає
map
отримує від нього на вхід лише одне число — елемент зі списку днів у місяці, а повертає цілий список днів у цьому місяці. Виходить список у списку:
Так працює map (у поданні художника)
Можна викликати
concat
і розплющити список одновимірний:
months = cycle [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
to_days max_days = [1..max_days]
dude day month 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 day month 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 day month 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
. Забагато! Однак, відповідь вірна.


Де ж саме коротке рішення, запитаєте ви? Там така справа, загалом, є слово на букву м. І я поки не придумав як пояснити його в такому ж форматі. Ну і взагалі, писанини багато вийшло, для однієї статті був би перебір. В наступний раз.
Лямбда (у поданні художника)
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.