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

  • Tutorial

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


Идея этой статьи пришла мне в голову на следующее утро после завершения состязания на 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 получает от него на вход всего одно число — элемент из списка дней в месяце, а возвращает целый список дней в этом месяце. Получается список в списке:
Так работает 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. Многовато! Однако, ответ верный.




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

Share post

Comments 35

    +3
    При всём уважении к ФЯП, написание чистых функций — не самая интересная (читай: сложная) вещь. Вот грамотное сосуществование с сайд-эффектами от IO — это реальная проблема. И по моим ощущениям решения на ФЯП не всегда интуитивно и разумно отражают реальность.

    Ближайшее место, где начинается веселье — база данных с конкурентным доступом. Все виды ORM, которые я видел, на Хаскеле выглядели так же трагично, как и на других языках. Начинают красиво, а дальше квирк на хаке и воркэраундом погоняет.
      0
      Не буду холиварить, замечу только, что F# функциональный и при этом никто не жаловался на работу с БД в нем. Впрочем, я согласен, что не все и не на всех языках получается хорошо и удобно. Я думаю, у меня будет статья и про вещи более приземленные, чем решение задачек.
        0
        Никто не жаловался ни на одном языке — потому что всюду фигачат как много.
        +3

        Знакомство с фяп научило меня видеть чистые функции там где раньше была борода из классов и сайд эффектов. Но работать все-таки приходится на ооп.

          0
          А можно примерчик? Ну вот я скажем не понимаю, что является хаком в slick, хотя сейчас вижу его практически впервые.

          Не хочу сказать, что это выглядит как-то там особо прекрасно, но и трагичности в этом тоже не наблюдается. Да, это делается не так, как привычно, иногда даже совсем не так. Но привычка — это все же немного другое, согласитесь. Это даже называется FRM, а не ORM, потому что маппинг тут не в объекты, а с функциями. Но опять же — это как раз естественно для функционального языка.
          +1
          где мне нужно было срезать еще 10 символов, чтобы получить самое короткое решение

          Серьезно? Ну я догадываюсь, что вы имели в виду заменить concatMap на монадический бинт. Но там и остальное можно неплохо ужать:
          months = cycle [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
          
          dude m d n = sum . take n . drop (d-1) $ flip take [1,3..] =<< drop (m-1) months
          
          main = print $ dude 12 31 10
          
            0

            Вместо flip take [1,3..] можно же написать


            (`take`[1,3..])

            Будет еще короче

              0

              Давайте посчитаем:


              (`take`[1,3..])``` -- 15 символов
              flip take [1,3..] -- 15 символов
                +2

                Хм, а значимые пробелы что, не считаются?..

                  0

                  Ну да. Только символы кода.

              0

              Эта статья не про самое короткое решение, а про решение вообще. В конце написано об этом. Ужать можно еще сильнее.

              +1
              В целом получилось неплохо, спасибо.

              Только если уж вы пишете для начинающих, то советы типа «залезть в prelude и найти там нечто» — они не очень хорошие. Ибо откуда начинающий догадается, что ему нужно? Даже в случае суммы это далеко не так очевидно, как вы показываете. Не говоря уже про применение map, которое вы подаете так, как будто всем это давно известно. На самом деле, тем кому это очевидно, уже не нужно введение такого уровня — им захочется посложнее.

              Ну и так, по мелочи — хорошо бы через проверку правописания пропустить, есть некоторое немаленькое число опечаток.
                +1

                Так вот в статье как раз и написано где нужно смотреть и дана ссылка. Теперь начинающий знает, что есть такое место и что там можно что-то найти.
                А что не известного в map? В питоне и яваскрипте он есть. Большинство людей с ним знакомы. Я не ставлю себе целью научить людей программировать. Статья для тех кто уже умеет, но боится хаскелля.
                В продолжении будет посложнее, придется рассказать про типы и слово на букву м. Для одной статьи было бы слишком много.
                Прошу прощения. Видимо, хромовый спеллчекер не очень. Сейчас поищу какой-нибудь сервис и проверю.

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

                    Спасибо за замечание. Я часто мучаюсь из за того, что не могу понять, что нужно рассказать. Что очевидно, а что требует пояснения.

                      0
                      На самом деле одно нужное пояснение уже ниже написали — про ленивость. Я бы сказал, что оно самое существенное — потому что те языки, с которыми люди знакомы, в большинстве все-таки не ленивые. А это очень важно.

                      И не только в этом месте — ленивость в общем виде например позволяет написать if в виде функции с тремя аргументами, при этом не вычисляя аргумент для else до тех пор, пока он не потребуется. А если у else есть побочные эффекты, то вычислять его всегда — это моветон. Ну вы поняли, я думаю.
                        0

                        Побочные эффекты в чистых функциях — моветон независимо от ленивости или неленивости

                          0
                          Речь вообще-то не о том, хороши побочные эффекты или плохи.

                          Речь о том, что ленивость это как раз то, что сильно отличает хаскель от большинства других языков, где есть скажем такие же на первый взгляд map, fold и списки, потому что большинство из этих других языков все-таки не ленивые.

                          И на самом деле, если смоделировать поведение неленивого языка в хаскеле можно, и достаточно несложно, то чтобы смоделировать ленивость в изначально неленивом языке, придется довольно сильно напрягаться (и не всегда выйдет). Скажем, в java это стало делать сравнительно легко, когда появились лямбды. А если нет функций как 1st class object, то и вообще вряд ли получится.

                          И именно ленивость дает возможность использовать бесконечные структуры данных.
                    –1
                    Статья для тех кто уже умеет, но боится хаскелля.
                    Я боюсь не haskell, а cabal. От того вместо haskell играюсь с clojure.
                  +3
                  Для самых ленивых можно не устанавливать haskell, а воспользоваться онлайн сервисом
                    0

                    Точно! Сейчас добавлю.

                    +3
                    Где же самое короткое решение, спросите вы? Там такое дело, в общем, есть слово на букву м.
                    Хорошая статья, пишите про букву м. :)
                      0

                      Спасибо. Уже половина написана.

                      0
                      Поясните, пожалуйста, эту магию
                      to_days max_days = [1..max_days]
                      

                      Как ни прочитаю любую статью про хаскель, всегда долго медитирую на какую-то магию и вспоминаю вот эту историю.
                        +1

                        А что тут, собственно, магического?


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


                        Прямые аналоги:


                        function to_days(max_days) {
                          return _.range(1, max_days+1);
                        }

                        def to_days(max_days):
                            return xrange(1, max_days+1)

                        static IEnumerable<int> ToDays(int max_days) => Enumerable.Range(1, max_days);
                        0

                        Функция to_days с аргументом max_days которая при помощи синтаксического сахара [1..max_days] создает список от 1 до max_days. Ну т.е. [1..10] == [1, 2, 3, 4, 5, 6, 7, 8, 8, 10].
                        Gryphon88 сорри, не в ту ветку ответил

                          0
                          понял, спасибо. Просто смутился, что по разные стороны знака равенства одна переменная да ещё в разной семантике
                            0

                            Ничего страшного. Спрашивайте еще; мне нужно знать, что я не понятно объясняю.

                              0
                              Можете мне ещё объяснить пафос map? Читать код компилятора страшно, можете пояснить, почему map отработает только часть бесконечного списка? Если бы список был конечным, в чём отличие map от простого итерирования по списку?
                                0
                                В общем, нет никакого пафоса. И никаких отличий от простого итерирования по конечному списку нет. Просто в хаскелле(как и во многих других ФЯП) нет циклов как конструкций, все итерирование работает через рекурсию. А так как выполнение функций ленивое — итераций происходит ровно столько сколько нужно для получения результата и происходит это в самый последний момент при вводе/выводе (что, иногда, вызывает немалые проблемы). Когда мы ищем сумму то конечным условием для функции sum является достижение конца списка. Если искать сумму бесконечного списка то конечное условие никогда не будет достигнуто и все поломается. Для функций же вроде take или drop конечным условием является перебор заданного количества элементов, поэтому им все-равно где заканчивается список, они "проходят" только n заданных шагов, а значит map который перед ними выполняет только эти n шагов.

                                ну т.е. даже будь у вас конечный список, если для получения результата вы берете только первые три элемента, то только они и будут вычислены.

                              0

                              Что значит "в разной семантике"?

                                0
                                меня смутило, что слева max_days — список, а справа int. Неправильно понял синтаксис.
                            0
                            Есть еще замечательный оператор $ который как бы говорит хаскеллю: «сначала выполни все, что правее меня, а результат подставь на мое место».

                            По моему такое определение отражает суть оператора $ с искажением. В противном случае, в выражении
                            take 3 . reverse . filter even $ [1..10]
                            
                            логично было бы убрать $, однако компилятор в таком случае выдаст ошибку:
                            take 3 . reverse . filter even [1..10]
                                -- take 3 . reverse . [2,4,6,8,10]
                                -- ошибка: применение композиции (.) к списку
                            

                            Получается что оператор $ в данном примере говорит хаскеллю: «сначала выполни все, что левее меня, а результат подставь на мое место». А версия со скобками выглядит так:
                            (take 3 . reverse . filter even) [1..10]
                            

                            Даже в одной из книг, помню, было определение типа «сначала выполни все что справа, потом примени». Со временем появились сомнение, и выяснилось, что '$' такой же оператор применения как ' ' (пробел), только первый имеет самый низкий приоритет — 0, а второй — самый высокий — 10.
                            К слову, оператор композиции (.) имеет приоритет 9, что объясняет ошибку компилятора в примере выше.

                            Спасибо за статью, с удовольствием прочитаю продолжение!
                              0

                              Говорить "сначала выполни все, что левее меня" — тоже ошибка, потому что приоритет "работает" в обоих направлениях: foo $ bar baz будет вычислено как foo (bar baz)


                              А в книгах пишут "сначала правее" подразумевая, что оператор $ — правоассоциативный. Иными словами, foo $ bar $ baz эквивалентно foo (bar baz), а вовсе не (foo bar) baz. В этом заключается его еще одно отличие от левоассоциативного пробела.

                                0
                                Говорить «сначала выполни все, что левее меня» — тоже ошибка, потому что приоритет «работает» в обоих направлениях:
                                Совершенно верно. Это был лишь пример другого «искажения» противоречащего с первым.

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

                            Only users with full accounts can post comments. Log in, please.