Первые вопросы. Функциональное программирование на языке Haskell. Конспект лекций

Несмотря на то, что он не соответствует одному из ваших больших критериев (статический * ввод), я собираюсь сделать дело для Python. Вот несколько причин, по которым я думаю, вам стоит взглянуть на это:

Для императивного языка это удивительно функционально. Это было одно из того, что меня поразило, когда я узнал об этом. Например, обратите внимание на списки . Он имеет лямбды, первоклассные функции и множество функционально вдохновленных композиций на итераторах (карты, складки, молнии...). Это дает вам возможность выбрать любую парадигму, которая лучше всего подходит для этой проблемы.
ИМХО, это, как и Haskell, красиво кодировать. Синтаксис прост и элегантен.
У этого есть культура, которая сосредотачивается на том, чтобы делать вещи прямолинейно, вместо того, чтобы сосредотачиваться слишком аккуратно на эффективности.

Я понимаю, если вы ищете что-то еще. Логическое программирование, например, может быть прямо вверх по вашей аллее, как и другие.

* Я предполагаю, что вы подразумеваете статическую типизацию здесь, так как вы хотите объявить типы. Techincally, Python - это строго типизированный язык, поскольку вы не можете произвольно интерпретировать, скажем, строку как число. Интересно, что существуют производные Python, которые позволяют статическую типизацию, например Boo .

2018-12-04T00:00Z

Если вам нужен сильный (эр) личный пролог, Mercury - интересный выбор. В прошлом я занимался этим, и мне нравилась другая перспектива, которую он мне дал. Он также имеет moded-ness (какие параметры должны быть свободными / фиксированными) и детерминизм (сколько результатов есть?) В системе типов.

Clean очень похожа на Haskell, но имеет уникальную типизацию, которая используется как альтернатива Monads (более конкретно, монада IO). Уникальность ввода также делает интересный материал для работы с массивами.

2018-12-11T00:00Z

Поскольку вы не указали никаких ограничений, кроме своих субъективных интересов, и подчеркиваете «вознаграждение учиться» (хорошо, хорошо, я проигнорирую ограничение статического набора текста), я бы предложил изучить несколько языков различных парадигм и, предпочтительно, те, которые являются «образцовыми» для каждого из них.

Липский диалект для кода-данных-данных / гомоконичности и потому что они являются хорошими, если не лучшими, примерами динамических (более или менее строгих) языков функционального программирования
Пролог как преобладающий логический язык программирования
Smalltalk как единственный истинный язык ООП (также интересный из-за его обычно чрезвычайно ориентированного на изображение подхода)
возможно, Erlang или Clojure, если вас интересуют языки, выкованные для параллельного / параллельного / распределенного программирования
Форвард для программирования, ориентированного на стек
(Haskell для строгого функционального статически типизированного ленивого программирования)

Особенно Lisps (CL не так много, как Scheme) и Prolog (и Haskell) охватывают рекурсию.

Хотя я не гуру ни на одном из этих языков, я провел некоторое время с каждым из них, кроме Эрланг и Форта, и все они дали мне открывающиеся и интересные познавательные впечатления, поскольку каждый из них подходит к решению проблем под другим углом,

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

2018-12-18T00:00Z

С точки зрения того, что подходит вашему майору, очевидный выбор кажется логическим языком, таким как Prolog или его производные. Логическое программирование может быть сделано очень аккуратно на функциональном языке (см., Например, The Reasoned Schemer), но вам может понравиться работать с логической парадигмой напрямую.

Интерактивная теоретическая система доказательства, такая как twelf или coq, может также поразить вашу фантазию.

2018-12-25T00:00Z

Я хотел бы расширить свои знания в области программирования. (...) Я думал, что поставил бы здесь вопрос, а также несколько положений о типе языка, который я ищу. Некоторые из них субъективны, некоторые из них предназначены для облегчения перехода от Haskell.
Сильная система типов. (...) Он также делает неформальные рассуждения о правильности моей программы более легкими. Меня беспокоит правильность, а не эффективность.
Акцент на рекурсии, а не на итерации. (...)

Боюсь, вы можете немного облегчить переход сюда. Очень строгая система типов и чисто функциональный стиль характерны для Haskell, и почти все, что похоже на основной язык программирования, потребует компрометации, по крайней мере, на одном из них. Итак, имея в виду, вот несколько широких предложений, направленных на сохранение большей части того, что вам нравится в Haskell, но с некоторым существенным сдвигом.

Не обращайте внимания на практичность и отправляйтесь на «больше Haskell, чем Haskell» : система типа Haskell полна дыр, из-за прекращения и других беспорядочных компромиссов. Очистите беспорядок и добавьте более мощные функции, и вы получите такие языки, как Coq и Agda , где тип функции содержит доказательство ее правильности (вы можете даже читать функцию arrow -> как логическую импликацию!). Эти языки использовались для математических доказательств и для программ с чрезвычайно высокими требованиями к правильности. Coq, вероятно, является самым выдающимся языком стиля, но у Agda больше чувство Haskell-y (а также написано в Haskell).

Не учитывайте типы, добавляйте больше магии : если Haskell - колдовство, Lisp - это сырая первобытная магия творения. Языки семейства Lisp (включая Scheme and Clojure ) обладают почти беспрецедентной гибкостью в сочетании с экстремальным минимализмом. Языки по существу не имеют синтаксиса, написание кода непосредственно в виде структуры данных дерева; метапрограммирование в Lisp проще, чем не-мета-программирование на некоторых языках.

Компромисс немного и приближайтесь к мейнстриму : Haskell попадает в широкую семью языков, сильно влияющих на ML, любой из которых вы, вероятно, могли бы перейти без особых трудностей. Haskell является одним из самых строгих, когда речь заходит о гарантиях правильности от типов и использования функционального стиля, где другие часто являются либо гибридными стилями, либо / или делают прагматические компромиссы по разным причинам. Если вы хотите подвергнуть ООП и доступ к множеству основных технологических платформ, либо Scala на JVM, либо F # на.NET имеет много общего с Haskell, обеспечивая легкую совместимость с платформами Java и.NET. F # поддерживается непосредственно Microsoft, но имеет некоторые досадные ограничения по сравнению с Haskell и проблемами переносимости на платформах, отличных от Windows. У Scala есть прямые аналоги с системой типов Haskell и кросс-платформенным потенциалом Java, но она имеет более тяжелый синтаксис и не обладает мощной поддержкой сторонних разработчиков, которой пользуется F #.

Мэтью Гриффин

После продолжительного изучения Haskell я набрался достаточно опыта, чтобы сейчас дать вам пару советов. Кроме того, я хотел бы усвоить для себя кое-какие принципы, прежде чем идти дальше.

И хотя я иногда прибегаю к помощи Python, большую часть работы в вебе я теперь делаю на Haskell.

В первую очередь - данные

Я думал о переходе от динамического языка к статическому, а в Haskell’e структура данных, с которыми вы работаете, четко описывается при объявлении. В Python в большинстве случаев эту задачу выполняет код.

Когда я впервые увидел функции в Haskell, я задался вопросом: «Что представляют собой данные? Эта функция что-то берет на вход и выдает что-то на выходе?» А при работе с Python у меня возникал вопрос: «WHAT DOES THE CODE SAY?»

Структура данных Haskell сформировала качественно новый образ моего мышления, который я принес и в свою работу на Python. Мой код стал заметно лучше. И хотя очень часто мне казалось, что форма описанных мною данных менялась без причины, однако на деле все становилось ясно при небольшом изучении вопроса. Ограничения свободы в изменении данных также делают код менее сложным и более понятным.

Читаемость кода

Python привлекал меня возможностью писать действительно читаемый код. Примеры кода же на Haskell выглядели просто ужасно, за исключением некоторых сниппетов, которые, казалось, были подобраны специально, чтобы не напугать новичков. И хотя некоторые куски кода смотрелись очень даже приятно, большая часть исходников была наполнена чем-то страшным. А за этим «страшным» как раз и скрывалась вся мощь языка.

Я определенно не хотел писать «умный» код - тот, который способен продемонстрировать впечатляющие возможности языка, но совершенно неудобен.

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

Я понял, что Haskell - это язык не «умный», но с хитринкой. Написать «умный» код на Haskell, конечно, можно, но это не распространенный случай. В то же время, мощь «умного» кода ограничена строгой типизацией. Если функция должна вернуть Int , она вернет Int . Ну или выкинет ошибку компиляции в крайнем случае.

А более мощные абстракции в Haskell и вовсе напоминают некую магию, которой я пытался избегать при работе с Python.

Про читаемость я говорю серьезно

Сначала поверьте и убедите себя, что, да, люди действительно читают листинги на этом новом для вас языке, причем делают это быстро и регулярно. Разобравшись наконец с большей частью известных нюансов, я начал спокойнее относиться к коду на Haskell.

Комментарии. Они занимают верхнюю строчку в одной из глав нашей «книги».

Эта глава описывает то, как Томми пошел в магазин и купил утку.

chapter:: Tommy -> Market -> Duck

Функции из другой, уменьшенной функции, в общей картине сокращают код по максимуму.

Краткость. Вам не потребуется тонна кода для воплощения ваших идей.

Вставные символы

Я также хотел упомянуть о вставных функциях, которые распространены в языке Haskell. Вставные функции (или операторы) - это те функции, которые используют between для двух аргументов вместо before . Простым примером является «+».

В языке Haskell мы имеем несколько вставных символов, которые используются по умолчанию: $, <$>, <-, ->, др. Они могут вас немного смутить на начале пути.

Не переживайте! Как только вы научитесь применять их, вы поймете, как они полезны и просты. Я насчитал около 5 символов, которые я использую регулярно.

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

Нужно полностью обновить знания

При изучении Haskell вы будете попутно сталкиваться с новыми терминами, например, функтор или монада.

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

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

Моя стратегия по изучению таких слов пришла ко мне в голову совсем недавно, и я начал использовать ее каждый раз, когда видел непонятный мне термин. Она заключается в подборе синонимов к тем словам, которые вам не понятны и незнакомы. Спустя некоторое время, я научился подбирать эти синонимы.

Например, функтор.

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

Map (+1) -- results in

Так я дал название этому - мапа. Слово «мапа» является очень простым для запоминания. Список - это функтор. Список - это мапа.

Моя система проверки ошибок

Когда я писал на Python, моим инструментом отладки были операторы печати.

В Haskell я пользовался систематическими инструментами.

Но! Вы можете применить Debug.Trace . Данный прием схож с тем, как в Python функция печати не зависит от Haskell IO. И данный модуль может вначале принести пользу. Когда вы только начинали работать с Haskell, вы думали о том, как много вы будете его использовать?

Если вы не будете использовать операторы трассировки в вашем коде после проверки ошибок, то вы сразу заметите, что ваш код в Haskell выглядит хуже, чем в Python.

Лучший учебник по монадам

Каждый раз, когда вы слышите об успехе человека, программирующего на Haskell, вы задумываетесь: «Как этот человек до конца усвоил монады?» Итак, все по порядку.

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

Окей, сейчас я расскажу подробнее. Я буду объяснять на Haskell.

Я нашел видео на YouTube, «Parsing Stuff in Haskell », в котором описывалось, как сделать JSON анализ в Haskell, используя при этом библиотеку Parsec.

Это видео помогло мне ненароком понять, как можно, используя монады и аппликативные функторы, создать то, что мне требовалось. Я понял, как их функции (har, har) соединяются друг с другом.

После написания синтаксического анализа при помощи видео, я начал понимать весь код. Я также начал понимать всю его «природу». Но на начальном этапе это не пригодится.

Итак, Parsec делает свое дело достаточно неплохо, так что моя неопытность при написании анализа практически не заметна. Так же, как и любой другой начинающий в Haskell, я с лёгкостью мог даже в начале знакомства с этим языком делать неплохие программы и операции.

Польза от ваших знаний

Haskell является моим основным языком по нескольким причинам:

Выбор технологий, которыми я буду пользоваться.
Я могу писать свои программы быстрее, и чаще всего эти программы я и продаю.
Не приходится иметь дело с мелкими багами.
Даже сталкиваясь с несколькими ошибками, я быстро решаю их, так как они более-менее понятны.
Python не делал акцент на скорости работы. Haskell делает то же самое, но выбор все же за мной.
Рефакторинг, по сути, достаточно «ветреный». В Python я иногда сильно ругал себя, когда забывал править небольшие ошибки в коде, которые позже вызывали огромные затруднения.
Замечательные библиотеки. Основная особенность Haskell заключается в высоком качестве библиотек.
Сообщество , всегда готовое помочь.
Простота масштабирования кода до нужного ядра.
Haskell часто обновляется. В прошлом году, когда GHC (компилятор для Haskell) был обновлен до версии 7.8, делая при этом написание кода в два раза удобнее, были ускорены многие веб-сервера.

И в заключение хочу сказать, что Haskell доставил мне уйму удовольствия. Это был лучший опыт за всю мою жизнь.

Мне задавали их множество раз. Отвечаю.

«Что такое этот ваш Haskell?»

Haskell - чисто функциональный язык программирования общего назначения, может быть использован для решения самого широкого круга задач. Компилируемый, но может вести себя и как скриптовый. Кроссплатформенный. Ленивый, со строгой статической типизацией. И он не похож на другие языки. Совсем.

«Это что, какой-то новый язык?»

Вовсе нет. История Haskell началась ещё в 1987 году. Этот язык был рождён в математических кругах, когда группа людей решила создать лучший функциональный язык программирования. В 1990 году вышла первая версия языка, названного в честь известного американского математика Хаскелла Карри . В 1998 году язык был стандартизован, а начиная с 2000-х началось его медленное вхождение в мир практического программирования. За эти годы язык совершенствовался, и вот в 2010 мир увидел его обновлённый стандарт. Так что мы имеем дело с языком, который старше Java.

«И кто его сделал?»

Haskell создавался многими людьми. Наиболее известная реализация языка нашла своё воплощение в компиляторе GHC (The Glasgow Haskell Compiler), родившегося в 1989 году в Университете Глазго. У компилятора было несколько главных разработчиков, из которых наиболее известны двое, Simon Peyton Jones и Simon Marlow . Впоследствии весомый вклад в разработку GHC внесли ещё несколько сотен человек. Исходный код компилятора GHC открыт . Кстати, сам компилятор на 82% написан на Haskell.

Для любопытных: исчерпывающее повествование об истории Haskell и GHC читайте .

«А библиотеки для Haskell имеются?»

О да! Их даже не сотни - их тысячи. В процессе чтения вы познакомитесь со многими из них.

«И что, его уже можно в production?»

Он уже в production. С момента выхода первого стандарта язык улучшался, развивалась его экосистема, появлялись новые библиотеки, выходили в свет книги. Haskell полностью готов к серьёзному коммерческому использованию, о чём свидетельствуют истории успешного внедрения Haskell в бизнесе, в том числе крупном .

«А порог вхождения в Haskell высокий?»

И да и нет. Освоение Haskell сложно в первую очередь из-за его непохожести на остальные языки, поэтому людям, имеющим опыт работы с другими языками, мозги поломать придётся. Именно поломать, а не просто пошевелить ими: Haskell заставляет иначе взглянуть даже на привычные вещи. С другой стороны, Haskell проще многих известных языков. Не верьте мне на слово, вскоре вы и сами в этом убедитесь. И знайте: многие люди, узнав вкус Haskell, категорически не желают возвращаться к другим языкам. Я вас предупредил.

«А я слышал ещё про какие-то монады…»

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

«А если сравнить его с C++/Python/Scala…»

Сравнение Haskell с другими языками выходит за рамки этой книги. Несколько раз вы встретите здесь кусочки кода на других языках, но я привожу их исключительно для того, чтобы подчеркнуть различие с Haskell, а вовсе не для сравнения в контексте «лучше/хуже». И вообще, я буду изо всех сил стараться не восхвалять Haskell без меры, я хочу лишь рассказать вам правду о нём. Мой вывод об этом языке я уже сделал, а свой вывод о нём вы должны сделать сами.

Функциональные языки программирования (ФЯП) представляют собой в первую очередь новый (для многих) способ думать о программах и программировании. Часто хорошо написанный функциональный код оказывается гораздо более выразительным и аккуратным, чем эквивалентный императивный или ООП-код.

Большинство современных функциональных языков так же предоставляют некоторые гарантии касательно программ. В частности, Haskell в большинстве случаев гарантирует, что программа не завершится с ошибкой доступа к памяти, как, скажем C++, или с ошибкой преобразования типов, как, скажем, Python или Ruby. Большинство подобных ошибок будут обнаружены на этапе компиляции программы.

В основе функционального программирования лежит простое представление о том, что функции в языке ничем не отличаются от переменных. Обычно к этому добавляют, что функции в целом должны быть функциями в математическом смысле, то есть не должны иметь некого внутреннего состояния и не должны неявно изменять внешнего состояния (окружения). Прямым следствием отсутствия состояния является тот факт, что функция, вызванная с одними и теми же аргументами возвращает одно и то же значение. Следствием неизменности внешнего состояния является отсутствие побочных эффектов. Например, printf в C/C++ принимает некие аргументы, и возвращает число. Но кроме этого, printf выводит символы в терминал. Последнее является побочным эффектом. В общем случае, неявные изменения внешнего (по отношнению к программе) состояния считаются побочными эффектами.

Но если внешнее состояние неизменно, программа неизбежно превращается в некую Кантовскую “вещь в себе” – она не может читать/записывать файлы, терминал, и т.д. Это не выглядит очень полезным. На самом деле, ФЯП выходят из положения, вводя некую псевдопеременную “мир”, которая может явно быть передана главной функции программы (main), и ее измененное состояние явно возвращается главной функцией программы. Таким образом, функциональную программу можно алгебраически представить как некую функцию:

\[ W_{n+1} = P(W_{n}), \]

где $W$ – состояние окружения (“мир”), а $P$ – это программа.

Другая особенность ФЯП, прямо следующая из того, что функции не имеют и не изменяют состояния заключается в том, что в ФЯП очень часто нет “переменных”. Любые выражения являются константами, если смотреть с точки зрения императивных языков. Это свойство называется “ссылочной прозрачностью”: если вы видите, что функция принимает переменную, вы всегда точно знаете, какое значение имеет эта переменная.

Подобный подход значительно упрощает “думание” о программах: больше не нужно держать в голове состояние – код работает ровно так, как читается – никаких скрытых параметров.

Использование чистых функций, помимо прочего, позволяет значительно упростить реализацию функций высших порядков, т.е. функций, оперирующих с функциями (которые тоже могут оперировать с функциями, и так далее). Поэтому, большинство ФЯП имеют поддержку функций высшего порядка “встроенными” в язык интуитивным образом. В качестве небольшого примера, приведу сравнение реализаций функции for_each , работающей со списком на C++ и Haskell.

Функции высшего порядка

На Haskell аналогичный код будет выглядеть так:

На самом деле, вызов функции с аргументами в Haskell является настолько фундаментальным, что не имеет специального синтаксиса, поэтому аналогичный код можно записать так:

На самом деле в языке уже есть такая функция, и она называется map . Вернемся к ней чуть позже.

Каррирование

Очень интересным мометном здесь является использование (1+) для добавления 1. Для этого придется рассказать про нотацию Хаскеля Брукса Карри (американского математика, 1900-1982), в честь которого назван язык. Эта нотация называется частичной аппликацией функций или каррирование .

Вкратце, любая функция нескольких аргументов $f(x,y)$ может быть разложена на последовательное применение нескольких функций одного аргумента. Например, $f(2,3)$ может быть разложена как:

\[ g(y) = f(2,y) \] \[ f(2,3) = h(g(3)) \]

Можно заметить, что функция двух аргументов $f(x,y)$ превращается в функцию одного аргумента $g(y)=f(x,y)$ . Это и есть каррирование. Если записать то же самое в нотации Haskell:

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

Какое отношение это имеет к (1+) ? Самое прямое. (1+) . Сложение является функцией двух аргументов и может быть записано как x+y = (+) x y . Тогда применение к одному аргументу (+) 1 даст нам функцию одного аргумента, которая прибавляет к аргументу 1. (1+) – это просто синтаксическое соглашение (“сахар”), которое сводится к (+) 1 .

Порядок применения функции

Чтобы каррирование работало, аргументы функции применяются слева направо (или лево-ассоциативно). Таким образом, выражение вида

Означает то же самое, что

Это отвечает на вопрос, почему нельзя записать print for_each (1+) и ожидать адекватных результатов (на самом деле такой код просто не скомпилируется, поскольку print for_each не может принимать аргументы)

Существует оператор $ , который является право -ассоциативным применением функции. Поэтому код можно записать так:

Это позволяет слегка экономить на скобках, однако применимость зависит от конкретного случая.

Эта-редукция, композиция функций и pointfree-нотация

Другой способ экономии – это эта-редкукция.

Эта-редукция позволяет писать достаточно компактный и при этом вполне понятный код, опуская “лишние” переменные. Такая нотация называется “pointfree” (аргументы иногда называют “точками”, отсюда такое название). Напишем программу, которая читает строки и выводит их в обратном порядке.

Пока не обращая внимания на последнюю строчку (считаем что там магия), рассмотрим функцию revlines. Очевидно, что x здесь вполне избыточен. В математике есть нотация композиции функций, обозначаемая точкой:

\[ f(g(x)) = (f\cdot g)(x) \]

Haskell имеет аналогичную нотацию: f (g x) = (f . g) x . Тогда мы можем переписать revlines в виде

Или, применяя эта-редукцию:

Использование функций высшего порядка возможно и в этом контексте. Скажем, мы можем хотеть не только вывести строки в обратном порядке, но и произвести каую-то другую операцию над массивом строк. Тогда мы можем написать:

Аннотации типов

Можно заметить, что во всем до сих пор написанном коде нигде не указаны типы. Haskell является строго типизированным языком, но типы указывать не обязательно. Это потому, что Haskell выводит типы автоматически. Тем не менее, для повышения читаемости кода (и для уменьшения вероятности ошибки), типы можно указывать . Запишем типы некоторых функций, и обсудим что это значит:

По соглашению, типы начинаются с заглавной буквы. Если тип обозначен маленькой буквой, то Haskell автоматически выводит его исходя из контекста. Так, например, мы использовали for_each с целыми. Тогда a=Int , b=Int . С тем же успехом, мы могли бы использовать ее со строками и т.д.

Оператор -> – право -ассоциативен (ввиду каррирования), поэтому

т.е. “функция принимает два аргумента”, эквивалентно

т.е. “функция принимает один аргумент и возвращает функцию одного аргумента”

map как функция высшего порядка

Попробуем написать свою функцию для работы со строками. Допустим, мы пишем программу, автоматически форматирующую код.

Получаем чудовищное, по виду, сообщение об ошибке

Couldn"t match type ‘Char’ with ‘’ Expected type: -> Actual type: -> In the first argument of ‘withLines’, namely ‘indent’ In the expression: withLines indent

Почему это происходит? Давайте запишем типы всех функций.

Ошибка становится вполне очевидна: withLines ожидает функцию типа -> , а мы ему даем String->String . Вообще, String определен как , т.е. список символов. Это объясняет сообщение компилятора.

Вспомним про функцию map , которая производит операцию над каждым элементом массива. Ее тип

Подставляя a,b=String , обнаруживаем то, что ищем:

Оказывается, map – это функция высшего порядка, которая преобразует функцию над элементами в функцию над массивами (списками). Подобные операции называются “поднятием” (lift), поскольку “поднимают” функцию из более простой категории типов в более сложную. Вообще, система типов Haskell сильно основана на теории категорий. Однако про теорию категорий сейчас не будем.

Секционирование операторов

Еще один пример использования функций высшего порядка

Здесь есть достаточно странный синтаксис. Для начала будем иметь ввиду, что любой бинарный оператор (а вообще говоря любая бинарная функция) может быть частично применен как

Вообще, `op` – это использование бинарной функции op как бинарного оператора

C тем же успехом можно частично применить второй аргумент:

Этот синтаксический сахар называется “секционирование операторов”

. – это бинарная функция высшего порядка:

Соответственно, если мы перепишем, скажем, withLines с аргументом, то получим:

Типы данных

В примерах раннее мы использовали тип данных списка (массива). Как этот тип устроен? Давайте попробуем сделать пользовательский тип списка.

Теперь мы можем записать что-то такое, например:

В Haskell, естественно, есть встроенный тип списка. Он определен следующим образом:

Можно просмотреть параллели. : – это Добавить, или cons , – это Пусто, или nil , а Список а – это [a] . Мы можем легко определить собственные операторы:

Или использовать их сразу в определении типа.

Единственное, что встроено в язык – это синтаксис вида , который автоматически преобразуется в x:y:...: .

Здесь Добавить и Пусто называются конструкторами типа Список . Это функции, которые “конструируют” значение типа Список. Не имеют практически ничего общего с конструкторами объектов в C++/Java.

Несколько примеров с нашим пользовательским типом:

С mystery1 , mystery2 все должно быть понятно. mystery3 – это бесконечный список, и Haskell все устраивает (поскольку это ленивый язык – значения вычисляются только при использовании), mystery4 – это ошибка типа. Int и String не могут находиться в одном списке.

Аналогично пишутся прочие типы данных.

Шаблоны аргументов

Для простоты, переопределим наш тип списка в латинице и сразу используем оператор:

Напишем несколько функций для нашего пользовательского списка:

Выглядит как какая-то черная магия. На самом деле все просто, мы определяем функцию, которая работает только для конкретного конструктора . _ означает только что мы игнорируем это поле. Мы так же могли бы конкретизировать аргументы, например:

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

Если мы не указываем все возможные варианты, то компилятор сообщает об этом, например:

Приводит к сообщению

Pattern match(es) are non-exhaustive In an equation for ‘isOne’: Patterns not matched: Nil

Нужно иметь ввиду, что программа аварийно завершится, если такой частично определенной функции передать значение, которое она не может обработать.

Тип Maybe

Немного странно кажется, что наша функция takeOne возвращает список, а не значение. Аналогичная библиотечная функция head возвращает значение, однако на пустом списке кидает исключение (да, в Haskell есть исключения, но их стараются избегать по очевидным причинам). Ее можно было бы записать в виде

undefined – ключевое слово, которое подходит под любой тип и аварийно завершает программу при попытке вычисления. Другой вариант undefined – это error x , где x имеет вид String . error выведет строку x перед завершением.

На помощь приходит тип Maybe . Он определен так:

В целом похоже на список, только без списка. takeOne можно переписать в виде:

Выглядит несколько более осмыслено, чем вариант со списком и гораздо более безопасно, чем undefined .

Попробуем написать поиск символа в строке с использованием типа Maybe:

Pattern guards

Предыдущий код можно переписать несколько короче:

Этот синтаксис называется “pattern guards”, или ограничители шаблонов в вольном переводе на русский. По сути, если выражение после | вычисляется как True , то шаблон срабатывает. Если нет – то проверяется следующий ограничитель, или следующий шаблон, если это был последний. otherwise – это просто более читаемый синоним для True .

В ограничителях так же возможно производить сравнения шаблонов. Синтаксис для этого:

Тогда код выше можно переписать в виде:

Классы типов

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

Мы изменили только сигнатуру типа, остальное осталось прежним. Сигнатура выглядит странновато: в ней появилось выражение Eq a => . Оно означает, что тип a принадлежит классу Eq – классу типов, для которых определена эквивалентность, т.е. опреатор (==) .

Eq определен следующим образом:

Видно, что это просто сигнатура типа. Чтобы определить реализацию для конкретного типа, определяется экземпляр класса:

Каким конкретно образом реализовано сравнение символов – довольно долгая история. Примитивные типы типа Int , Char или скажем Double достаточно глубоко встроены в язык. Мы, однако, можем определить экземпляры для более сложных типов:

Здесь мы опять вводим ограничение на класс. По сути мы утверждаем, что для всех типов a в классе Eq существует тип Maybe a , так же в классе Eq . Ничто не мешает добавлять собственные типы.

Классы типов позволяют писать обобщенные, и при этом типобезопасные функции.

Опять про Maybe

Тип Maybe достаточно простой и при этом удивительно полезный. Очень многие функции, которые возможно определены могут использовать этот тип в качестве возвращаемого значения. Например:

Это гораздо лучше, чем возвращать NULL , как в C/C++ . Во-первых, глядя на сигнатуру типа, сразу становится ясно, чего можно ожидать от функции. Во-вторых, компилятор не позволит производить вычисления с несуществующим значением. Если в “классических” языках типы в основном служат компилятору, то в функциональных типы служат в первую очередь программисту.

Очевидный вопрос с Maybe заключается в следующем: допустим у нас есть функция

Рассмотрим такой код:

Каков результат такого кода? Правильный ответ – ошибка типа. 1 имеет тип Int , в то время как takeOne возвращает тип Maybe Int . Проблема очевидна. Наивное решение этой проблемы в том, чтобы написать условие:

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

Теперь давайте вспомним, что, когда я говорил про map , я сказал, что эта функция “поднимает” свой первый аргумент в категорию списков. Эта же концепция применима ко всем производным типам. В языке сущесвтует обобщенная функция fmap . Посмотрим, как она работает:

Это выражение возвращает Just 2 . fmap “поднимает” свой аргумент в категорию производных типов. Каких именно – компилятор выводит автоматически из контекста.

Тип fmap определен как

Здесь используется класс Functor , единственное требование которого – чтобы был определен fmap . Для Maybe экземпляр определяется тривиально:

В общем случае класс Functor – это класс типов, принимающих один аргумент типа. Другой пример функтора – список. Таким образом, map является всего лишь частным случаем fmap .

Монады

Пока скажу только, что Maybe , и список являются монадами. Понятие монады происходит из теории категорий. Это понятие в большинстве функциональных языков является ключевым, поскольку, например, Haskell, инкапсулирует состояние окружения (то, которое функции не изменяют) в монаде IO (ввод-вывод). Наконец мы можем записать сигнатуру для main:

Функция main возвращает “пустоту” (на самом деле читается как unit, и аналогично по смыслу void в С) в монаде IO . IO , в свою очередь, где-то “внутри” содержит информацию о состоянии окружения.

Сточка, которая часто нам встречалась

использует следующие функции:

return и (>>=) (читается как bind) определены в классе Monad . return просто “поднимает” значение в монаду, а bind берет значение в монаде и передает его в функцию, возвращающую монаду. При этом некое “состояние”, инкапсулированное монадой (если оно есть), может неявно передаваться из функции в функцию через оператор bind.

Для интересующихся, хорошее объяснение:

Если есть интерес, выделим лекцию на продолжение.

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

Продолжая эту просветительскую работу, я бы хотел остановиться сегодня на — замечательном функциональном языке программирования. Мне уже трижды прислали один и тот же вопрос: с чего начать (продолжить) изучать Haskell?

Наверное, пора дать короткий ответ-совет. Вот общий алгоритм захода в эту тему от меня.

0 этап — Введение. Haskell? Чо за хрень?

Хорошо известный в среде рекрутеров программистов парадокс, часто называемый как « », и он формулируется примерно так:

Если компания выбирает в качестве основного языка программирования некий малораспространенный эзотерический язык программирования, то у такой компании наибольшие шансы получить самых лучших программистов на рынке. Почему? Дело в том, что наняться в такую «странную компанию» захотят в первую очередь те программисты, для которых изучение нового не проблема; те, для которых малоизвестное и труднодоступное не является препятствием; и, наконец, те, у кого достаточно высокая самооценка, чтобы предлагать себя в таких заведомо жестких условиях.

И главное: есть два типа программистов: те, кто учатся, чтобы получить хорошую работу, и они всегда выбирают мэинстрим , ибо это значительно повышает их шансы на трудоустройство; и те — кому просто нравится учиться чему-то новому, развиваться, и они всегда выбирают самое лучшее , что зачастую далеко не самое выгодное , как делают их коллеги-карьеристы. Итак, Парадокс питона утверждает, что начиная разработку на передовой экзотике, вы подобно пылесосу притянете вторую категорию программеров (верно и обратное, насчет компаний предлагающих работу).

Могу привести в качестве отвлеченного примера полностью аналогичного скрытного таргетирования фокус-групп с заданными свойствами, историю из своей недавней юности. Когда я ещё учился, у нас был припод "со странностями", который демонстративно при изложении матанализа никогда не обращал внимание на правую сторону аудитории. То есть в аудитории было два ряда — левый и правый, — и вот он читает лекцию, объясняет что-то, но при этом НИКОГДА не смотрит на правый ряд — всё внимание только на студентов с левого ряда. Также и с ответами на вопросы — правого ряда для него не существовало. Оттуда он ни-че-го не слышит.

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

3. Этап — поиск глубины и чувства нового языка

Третья стадия, — это уже копание вглубь. Тут я предлагаю немножко поломать традиционные шаблоны (а я это ох как люблю делать) и перейти к принципиально другому формату подачи информации: это не только разнообразит задачу изучения языка, но и задействует новые, доселе не активированные участки вашего головного мозга (особенно напряжем ваше растащенное программистское левое полушарие). Я имею в виду отличную видео-лекцию по Haskell от очень умного дядьки с английскими корнями.

Вот её выходные данные:

The Functional Programming Using Haskell course
(Language: English)
35 hours | 1280×720 | XviD — 1326Kbps
25.00fps | Mp3 — 96Kbps | 20.06 GB

Выкачать эту большую видео-лекцию можно . Советую поспешить, пока возмущенные правообладатели не сбежались и не прибили этот редкий архив нафиг (update : таки да, прибили его: аминь. Предлагаю всем заинтересованным воспользоваться этой мега-ссылкой).

4. Завершающий этап — практика

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

Вот, примерно такой вот, отчасти очевидный для многих алгоритм я хотел дать всем желающим изучить Haskell, и не только. Дерзайте!

И в заключение для приверженцев других языков программирования:

Haskell — священный язык программирования, дарованный шаманам Бубенлэнд их верховным божеством Комонада как универсальное средство для общения и духовного очищения, подходящее как божественным сущностям, так и (некоторым) простым смертным, переболевшим тяжёлыми стадиями интеллекта. Из-за своего происхождения язык всегда был функционально чист. В среднем обучение Haskell’у начинается в 10-12 лет. Своевременное начало обучения гарантирует, что вы достигнете третьего уровня Силы уже к 75 годам. Не стоит откладывать на следующую жизнь то, что можно по крайней мере начать в этой.