Функциональное программирование *

На новый год купил племяннику головоломку Галакуб. Задача собрать из разных деталей куб размером 4х4х4. Суммарный объём деталей, как раз, 4х4х4. Прежде, чем дарить надо было собрать головоломку. Красивое симметричное решение нашлось достаточно быстро. Но стало интересно единственное это решение или нет. Интуиция подсказывала, что единственное, но хотелось проверить.


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

Код получился на удивление красивый и понятный. Его удобно объяснять. Может быть, текст будет полезен, например, изучающим Питон.

В первой статье мы познакомились с Эрлангом и фреймворком n2o. В этой части мы продолжим делать наш блог:

• добавим авторизацию через фейсбук, для этого будем из клиента вызывать функции на сервере;
• будем сохранять комментарии и посты в NoSQL базе;
• развернем наш блог на DigitalOcean и замерим производительность (спойлер — 1300 запросов в секунду).

Код из статей https://github.com/denys-potapov/n2o-blog-example, готовый проект можно посмотреть по адресу http://46.101.118.21:8001/.

Это шестая статья из цикла «Теория категорий для программистов». Предыдущие статьи уже публиковались на Хабре:
0. Теория категорий для программистов: предисловие
1. Категория: суть композиции
2. Типы и функции
3. Категории, большие и малые
4. Категории Клейсли
5. Произведения и копроизведения

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

Рассмотрим подробнее место произведения и копроизведения типов в программировании.

Произведение типов

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

Строго говоря, произведение типов не коммутативно: нельзя подставить пару типа (Int, Bool) вместо (Bool, Int), хотя они и содержат одни и те же данные. Однако произведение коммутативно с точностью до изоморфизма, задаваемого функцией swap, которая обратна самой себе:

swap :: (a, b) -> (b, a)
swap (x, y) = (y, x)

Можно рассматривать такие пары как различные форматы хранения одной и той же информации, как big endian и little endian.

Продолжение о базе данных и деплое во второй статье.

Я начинаю публиковать серию статей о веб-разработке на Эрланге. Многие хотят попробовать Эрланг, но сталкиваются с проблемой, что вводные курсы в основном касаются Эрланга как функционального языка и далеки от реальных проектов (Learn You Some Erlang for great good! — хорошая и подробная книга). С другой стороны все обучающие материалы по веб-разработке подразумевают, что читатель уже хорошо знает Эрланг.

Эта серия статей рассчитана для разработчиков, у которых есть опыт в веб-разработке (PHP, Ruby, Java), но не имеют опыта разработки на Эрланге.

Задачей будет сделать блог. Код из статей https://github.com/denys-potapov/n2o-blog-example, готовый проект можно посмотреть по адресу http://46.101.118.21:8001/. Особенности проекта:

• обновление комментариев в реальном времени;
• авторизация через фейсбук;
• данные храним в mnesia.

В основе проекта феймворк n2o. Выбор довольно субъективен, но из живых Эрланг фреймворков, n2o мне показался наиболее «эрлангоподобным», в тоже время ChicagoBoss больше похож на MVC фреймворки в других языках.

Автор: Игорь Литвиненко, Senior Mobile Developer.

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

Экскурс в историю

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

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

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

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

Шерлок Холмс и доктор Ватсон летят на воздушном шаре. Попадают в густой туман и теряют ориентацию. Тут небольшой просвет — и они видят на земле человека.
— Уважаемый, не подскажете ли, где мы находимся?
— В корзине воздушного шара, сэр.
Тут их относит дальше и они опять ничего не видят.
— Это был математик, – говорит Холмс.
— Но почему?
— Его ответ совершенно точен, но при этом абсолютно бесполезен.
(анекдот)

Когда древние египтяне хотели написать, что они насчитали 5 рыб, они рисовали 5 фигурок рыб. Когда они хотели написать, что насчитали 70 людей, они рисовали 70 фигурок людей. Когда они хотели написать, что насчитали в стаде 300 овец, они… — ну, в общем, вы поняли. Так и мучились древние египтяне, пока самый умный и ленивый из них не увидел нечто общее во всех этих записях, и не отделил понятие количества того, что мы подсчитываем, от свойств того, что мы подсчитываем. А потом другой умный ленивый египтянин заменил множество палочек, которыми люди обозначали количество, на значительно меньшее количество знаков, короткой комбинацией которых можно было заменить огромное количество палочек.

То, что сделали эти умные ленивые египтяне, называется абстракцией. Они подметили нечто общее, что свойственно всем записям о количестве чего-либо, и отделили это общее от частных свойств подсчитываемых предметов. Если вы понимаете смысл этой абстракции, которую мы сегодня называем числами, и то, насколько она облегчила жизнь людям, то вам не составит труда понять и абстракции языка Haskell — все эти непонятные, на первый взгляд, функторы, моноиды, аппликативные функторы и монады. Несмотря на их пугающие названия, пришедшие к нам из математической теории категорий, понять их не сложнее, чем абстракцию под названием «числа». Для их понимания совершенно не требуется знать ни теорию категорий, ни даже математику в объёме средней школы (арифметики вполне достаточно). И объяснить их тоже можно, не прибегая к пугающим многих математическим понятиям. А смысл абстракций языка Haskell точно такой же, как и у чисел — они значительно облегчают программистам жизнь (и вы пока даже не представляете, насколько!).

Питонисты Новосибирска, приглашаем вас на встречу сообщества Python сообщества — PyNSK.

12-го декабря (суббота) состоится пятая встреча. Она пройдет в новом для нас месте — Культурный Центр «Этаж» и начнется 13-00.
На встрече вас ждет море общения и 2 доклада:

Это пятая статья из цикла «Теория категорий для программистов». Предыдущие статьи уже публиковались на Хабре в переводе Monnoroch:
0. Теория категорий для программистов: предисловие
1. Категория: суть композиции
2. Типы и функции
3. Категории, большие и малые
4. Категории Клейсли

На КДПВ поросенок Петр заводит по одному трактору в каждый объект категории.

Следуй по стрелкам

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

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

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

Несколько последних месяцев я программирую преимущественно на Scala (по работе) и на Haskell (для души). На этой неделе я, правда, ещё немного пописал на Ruby (по работе) и Clojure (для души).

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

Но вот что касается моего новенького, с иголочки, проекта-любимца на Clojure… О, Clojure! Глоток свежего воздуха! Благодатная земля хорошо скомпонованных функций, иммутабельных структур данных и всего такого. Как прекрасен твой синтаксис и как мудра твоя чувствительность! Вся твоя суть в функциях, принимающих мэпы и возвращающих мэпы. И твой SQL-генератор, и слой доступа к БД, и HTML-парсер, и URL-роутер являют собой одну и ту же завораживающую картину мэпов, гоняемых туда-сюда тактами процессора, прекрасную с своём ритме хорошо собранных швейцарских часов.

Вернуться к Clojure после долгого времени это всё равно, что почувствовать себя дома. Это просто окрыляет программиста. Но почему-то в этот раз я ощутил и ещё одно, неожиданное для себя чувство: неопределённость.

Привет, Хабр!

Мы в Хекслете учим людей программировать, но стараемся хитрить: например, под видом простого, на первый взгляд, курса по PHP, рассказываем людям про абстракции, рекурсии, функции первого класса, замыкании, свертку и вообще начинаем «Основы программирования» с МИТ'шного СИКПа, а не с классов и формочек. В этом и других курсах, а также в наших регулярных вебинарах рассказываем о функциональном программировании, о проблемах современных подходов и о главном зле: состоянии. В нашем чате постоянно поднимаются крупные дискуссии, в которых выясняется, что изменяемое состояние в разы повышает сложность в системе.

Сегодня мы публикуем перевод статьи, в которой Пиотр Солница, один из создателей популярного DataMapper для Ruby, рассуждает в подобном ключе о взаимодействии с базой данных.

* * *

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

Но что это вообще означает в Ruby? Запретить изменять любые объекты? Будет слишком медленно, так что — нет. Иммутабельно-ориентированный дизайн означает, что вы избегаете те интерфейсы, которые могут изменять объекты. Да, много методов в Руби изменяют состояние, но когда вы разрабатываете интерфейсы объектов, вы можете создавать их таким способом, что объекты не будут изменяться.

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

Часть 4. Суровая действительность

Как заставить Parboiled работать еще быстрее? Каких ошибок лучше не допускать? Что делать с наследством в виде Parboiled1? На эти, а так же другие вопросы призвана ответить заключающая статья серии.

Структура цикла:

• Часть 1. Почему Parboiled?
• Часть 2. Сопоставление текста
• Часть 3. Извлечение данных
• Часть 4. Суровая действительность

Часть 3: Извлечение данных

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

Структура цикла:

• Часть 1. Почему Parboiled?
• Часть 2. Сопоставление текста
• Часть 3. Извлечение данных
• Часть 4. Суровая действительность

Часть 2. Сопоставление текста

Во второй части цикла мы поговорим об основных правилах сопоставления символов в Parboiled. Мы не будем касаться всех правил — для этого есть документация, я всего лишь хочу, чтобы вы чувствовали себя уверенно с базовым синтаксисом правил, используемым в Parboiled.

Для закрепления знаний мы напишем простой распознаватель для несложной грамматики. Именно распознаватель (recognizer), а не полноценный парсер, так как он будет только сопоставлять входной текст c описанными нами правилами (также называемыми продукциями), но не будет извлекать из сопоставленного текста какие-либо значения. Распознаватель может быть полезным и сам по себе, так как может работать в качестве валидатора: если вход оказался некорректным, распознаватель даст об этом знать и расскажет, что пошло не так и где. А совсем классным наш распознаватель станет тогда, когда мы узнаем, как извлекать разобранные значения и причем тут какой-то «value stack». Ну что, поехали?

Структура цикла:

• Часть 1. Почему Parboiled?
• Часть 2. Сопоставление текста
• Часть 3. Извлечение данных
• Часть 4. Суровая действительность

Часть 1. Почему Parboiled?

Сегодня, в свете бурного роста популярности функциональных языков программирования, всё чаще находят себе применение комбинаторы парсеров — инструменты, облегчающие разбор текста простым смертным. Такие библиотеки, как Parsec (Haskell) и Planck (OCaml) уже успели хорошо себя зарекомендовать в своих экосистемах. Их удобство и возможности в своё время подтолкнули создателя языка Scala, Мартина Одерски, внести в стандартную библиотеку их аналог — Scala Parser Combinators (ныне вынесены в scala-modules), а знание и умение пользоваться подобными инструментами — отнести к обязательным требованиям к Scala-разработчикам уровня A3.

Эта серия статей посвящена библиотеке Parboiled — мощной альтернативе и возможной замене для Scala Parser Combinators. В ней мы подробно рассмотрим работу с текущей версией библиотеки — Parboiled2, а также уделим внимание Parboiled1, так как большая часть существующего кода всё ещё использует именно её.

Структура цикла:

• Часть 1. Почему Parboiled?
• Часть 2. Сопоставление текста
• Часть 3. Извлечение данных
• Часть 4. Суровая действительность

Сейчас я работаю над senjin/gglsl — библиотекой для программирования шейдеров с помощью Groovy, о которой недавно писал.

Здесь я опишу три подхода к анализу AST (abstract syntax tree), все на примерах под-задач, вытекающих одна из другой и связанных общим контекстом: рекурсивные функции, паттерн Visitor, и паттерн-матчинг.
Паттерн-матчинг реализован на Java и доступен на GitHub.

Пару месяцев назад я взяла на себя обязательство по самопросвещению. Есть в иных конторах такая тема — сотрудника, раз в полгода ревьюят и говорят «давай к следующему ревью ты изучишь Spring, паттерны (какие?) и функциональное программирование!» Идея была бы неплоха если бы цели не ставили так размыто. Пропустим пока спринг и паттерны — на выходных я бросилась в атаку на ФП.

Общие-туманные сведения о ФП у меня конечно были — анонимные классы в Java я писать умею — с похожими способностями Python и JavaScript знакома.

Начну с простых упражнений на Scala — решила я. Выбрала Scala поскольку основной рабочий инструмент у нас Java — ну были еще варианты Clojure, Groovy и Java8 (что-то еще?) — но с ними авось попробую потом.

Поставила себе цели (а правильно ли я ФП поняла?):

• Решать задачи в функциональном стиле
• Т.е. по возможности не использовать явных циклов и ветвлений
• А также избегать мутабельных коллекций и т.п.

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

Примечание переводчика. В будущей версии Scala (“Don Giovanni”) анонсирована поддержка типов объединения (union types). Miles Sabin, широко известный в узких кругах как создатель Shapeless, демонстрирует в этой статье 2011 года, как создать типы объединения уже сейчас.
UPD. Представленный в статье подход не позволяет получить настоящих типов объединения и кроме того может существенно повлиять на время компиляции. Типы пересечения (A with B), использованные в статье, также отличаются от классических, поскольку не обладают свойством коммутативности. Подробности об экспериментальном проекте Dotty, в рамках которого будут решены эти и другие проблемы, можно посмотреть в замечательной презентации Дмитрия Петрашко darkdimius — разработчика компилятора Scala в EPFL.

Scala имеет очень выразительную систему типов. Однако она не включает (по крайней мере как примитивы) всех вожделенных элементов. Есть несколько поистине полезных типов, подпадающих под эту категорию — это типы полиморфных функций высшего ранга (higher-rank) и рекурсивные структурные типы. Но о них я расскажу подробнее в следующих постах, а сегодня я собираюсь показать вам, как в Scala мы можем создать типы объединения (union types). В ходе объяснения я пролью немного света на изоморфизм Карри-Ховарда и покажу, как использовать его в наших целях.

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

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

Как должно быть очевидно, одна из целей этого сайта — убедить принимать F# всерьёз в роли универсального языка разработки.

Но в то время как функциональный стиль всё больше проникает в массы, и C# уже получил такие функциональные средства как лямбды и LINQ, кажется, что C# всё больше и больше наступает на пятки F#. Так что, как это ни странно, но я стал всё чаще слышать как высказывают такие мысли:

• «C# уже обладает большей частью инструментария F#, и зачем мне напрягаться с переходом?»
• «Нет никакой необходимости что-то менять. Всё, что нам нужно сделать, так это пару лет подождать, и C# получит достаточно от F#, что обеспечит практически все плюшки.»
• «F# только чуть лучше, чем C#, но не настолько, чтобы в самом деле тратить время с переходом на него.»
• «F# кажется действительно неплох, хоть и пугает местами. Но я не могу найти ему практического применения, чтобы использовать вместо C#.»

Не сомневаюсь, что теперь, когда и в Java тоже добавлены лямбды, подобные комментарии зазвучали в экосистеме JVM при обсуждении «Scala и Closure против Java».

Так что в этой статье я собираюсь отойти от F# и сосредоточиться на C# (а на его примере и на других популярных языках), чтобы показать, что даже с реализацией всех мыслимых средств функциональных языков программирование на C# никогда не будет таким же, как на F#.