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

В прошлый раз мы провели ознакомительную встречу. Собралось около 25 человек, мы узнали кто в Москве занимается разработкой на Scala и какие есть интересные проекты. Главной темой выбрали курс по реактивному программированию на Coursera, который как раз тогда подходил к концу.

В этот раз мы соберёмся послушать и обсудить два доклада:

1. Алексей Иванов приедет из Питера и расскажет доклад «Monadic Bakery with Spray and Scalaz»,
   про то почему Spray и ScalaZ — не страшные звери, а хорошие друзья;
2. Владимир Успенский расскажет про теорию типов и тем, как она связана с обычной разработкой в докладе:
   «Теория типов, или как мы занимаемся математикой, программируя на Scala».

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

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

Это статья попытка показать, что сила функциональных языков и в первую очередь Хаскеля — это в том числе и силе функторов и монад.

Введение

В мире функционального программирования есть один большой пробел, а именно почти не освещена тема высокоуровневого дизайна больших приложений. Я решил для себя изучить этот вопрос. Есть ли существенные отличия дизайна приложений в ФП-мире от оного в мире императивном? Что такое «каноничный ФП-код»? Какие существуют идиомы разработки, есть ли смысл вообще говорить о паттернах проектирования в применении к ФП? Эти и другие важные вопросы часто вспыхивают то там, то здесь, но покамест мне не известно ни одной книги, аналогичной книге Банды Четырех. Вероятно, мои изыскания уже кто-то повторил, однако тем лучше: схожие результаты подтвердят правильность, иные — укажут на место в теории, которое необходимо доработать.

Доброй ночи, Хабр! Мы продолжаем изучение Erlang для самых маленьких.

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

А сейчас нужно обязательно дунуть, потому что если не дунуть, то ничего не получится.
—Цитаты великих

И здравствуйте!

Сегодня мы поговорим о неявном в языке Scala. Кто еще не догадался — речь пойдет об implicit преобразованиях, параметрах, классах и иже с ними.Все новички, особенно любители питона с зеновским Explicit is better than Implicit, обычно впадают в кататонический ступор при виде подкапотной магии, творящейся в Scala. Весь компилятор и принципы в целом охватить за одну статью удастся вряд ли, но ведь дорогу осилит идущий?

Добрый день, уважаемое хабрасообщество!

В конце ноября 2013 года мы с коллегой устроили встречу, на которой провели сеанс «интенсивного введения Scala в мозг добровольцев».

Выкладываю на суд общественности наше творчество и краткое описание «эксперимента».

На Хабре много статей по монады с примерами для Haskell (http://habrahabr.ru/post/183150, http://habrahabr.ru/post/127556), но не так много статей, которые описывают, что такое монады с примерами на Scala. По сколько большинство разработчиков на Scala пришли из мира объектно ориентированного программирования, то для них, по началу, сложно понять что такое монады и для чего они нужны, эта статья как раз для таких разработчиков. В этой статье я хочу показать, что это такое и навести примеры использования монады Option, в следующих статьях будут описаны монады Try и Future.

В этой статье мы попытаемся рассмотреть всё разнообразие Алгебраических Типов Данных.

Надо сказать, задача это достаточно неподъёмная, и понять человеку, если он ранее с Алгебраическими Типами не имел дело — не очень просто.
АТД были впервые использованы в языке Hope, но основную популярность они приобрели благодаря языкам ML, такими как Standart ML, OCaml, F#, и языку Haskell.
Ныне АТД в той или иной мере поддерживаются в значительно большем количестве языков: Scala, Rust, Nemerle, Racket,…
АТД — это универсальный тип данных. С помощью него можно представить большинство типов данных.
АТД называются алгебраическими, потому что их можно представить как некую алгебраическую композицию типов его составляющих. Это знание даёт своё преимущество: понимая свойства алгебраической композиции, можно посчитать какой тип необходим для построения тех или иных данных.
Будем рассматривать типы на основе языка Haskell, однако подобного с лёгкими изменениями можно добиться в других языках с поддержкой АТД.

Признаюсь. Я не очень любил курс структур данных и алгоритмов в университете. Все эти стеки, очереди, кучи, деревья, графы (будь они не ладны) и прочие “остроумные” названия непонятных и сложных структур данных ни как не хотели закрепляться в моей голове. Как истинный “прагматик”, я уже на втором — третьем курсе свято верил в стандартную библиотеку классов и молился на дарованные нам (простым смертным) коллекции и контейнеры, бережно реализованные отцами и благородными донами CS. Казалось, все что можно было придумать — уже давно придумано и реализовано.

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

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

Всем программистам рано или поздно приходится передавать данные. Ни для кого не секрет, что библиотек сериализации в Java существует примерно >9000, а в C++ они вроде и есть, а вроде их и нет. К счастью для большинства, несколько лет назад появился Google Protobuf, который принёс достаточно удобный способ определять структуры данных и быстро завоевал всенародную любовь. Это была фактически первая, доступная широким массам библиотека, позволяющая гонять по сети готовые структуры данных, не связываясь при этом с чем-то вроде XML. На дворе был 2008 год.

Вернёмся немного назад. В 2006 году простой индийский программист (как бы подозрительно это ни звучало!) Анил Мадхавапедди, один из самых известных сейчас в мире OCaml-разработчиков и автор свежевышедшей книги Real World OCaml, защищал в Кембридже кандидатскую диссертацию. Именно о ней я сегодня вам и расскажу.

Анил сразу пошёл дальше, чем Google. Он сразу подумал, для чего люди обычно пересылают по сети какие-то формализованные структуры данных? Чтобы реализовать какой-то протокол. А что такое протокол? Это какой-то конечный автомат. А где мы можем взять хороший пример сложного, хорошо спроектированного и проверенного временем протокола? Да прямо в обычном сетевом стеке! Итак, были взяты набор сетевых структур данных и протоколов: Ethernet frame, IPv4, ICMP, TCP, UDP, SSH, DNS и DHCP и постановка задачи: большая часть этих протоколов (особенно SSH и DNS) реализуются, что называется «руками», а хочется, чтобы не было типичных для C переполнений буфера, все переходы совершались автоматически, это всё можно было верифицировать, и чтобы работало быстро, а не как обычно.

Поскольку никто не будет читать диссертацию, сразу скажу: это более чем удалось. По результатам работы были написаны референсные реализации DNS и SSH-сервера и произведено сравнение с BIND и OpenSSH. OCaml-реализации давали по сравнению с традиционными прирост производительности от незначительного, до почти двухкратного. Кроме того была найдена ошибка в RFC на SSH (рабочая группа была уведомлена и RFC исправлен). О том, что было сделано, и как с этим жить, читайте под катом.

Добрый день, сегодня хотелось бы рассказать, как наша команда работает с базами данных. У нас в компании в основном используется Oracle и в нашей команде много людей, кто умеет хорошо его готовить. Нам изначально хотелось получить полный доступ к его возможностям: иерархическим запросам, аналитическим функциям, передаче объектов и коллекций, как параметров запросов, и, может быть, если не будет другого способа — хинтам. Модель у нас не очень сложная, поэтому сознательно отказались от ORM.

В качестве основы взяли Apache DbUtils и сделали для него простую обёртку на Scala. Ниже я расскажу, как возможности Scala, особенно её последней версии 2.10, помогли упростить работу с базой данных.

А пытливых читателей, кто дочитает до конца, ждёт сюрприз.

Привет Habr! Сегодня мы поговорим о полиморфизме функций, операторах и карринге. Напоминаю, что лекции рассчитаны на новичков, а конспект предпологает сжатую форму изложения. Если все еще интересно…

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

Этот факт находит отражение и в изменении учебных курсов. Сассман, автор SICP, самого известного курса по программирование, сказал: " инженерное дело в середине 90-ых, а уж тем более в 2000-ых сильно отличается от инженерного дела 80-ых. В 80-ых хорошие программисты проводили много времени в размышлениях, а потом писали немного кода, который работал. Код работал близко к «железу», даже Scheme — все было прозрачно на всех стадиях. Как с резистором, достаточно посмотреть на цветную маркировку, чтобы узнать номинальную мощность, допустимые отклонения, сопротивление и V=IR — это все, что нужно знать. 6.001 был задуман как курс для обучения инженеров тому, как из маленьких кубиков, в которых они досконально разбираются, посредством простых техник составлять сложные конструкции, которые делают то, что от них хотят. Но программирование сейчас далеко не то же самое. Теперь вы ковыряетесь в непонятной или несуществующей документацией для софта, даже неизвестно, кем написанного. Вы должны досконально исследовать библиотеки, чтобы узнать, как они работают, пробовать разные исходные данные и смотреть, как реагирует код. Это в корне иная работа, и для нее требуется иной курс обучения."

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

Привет Habr! Сегодня я достал свои старые конспекты по курсу «Haskell как первый язык программирования» Сергея Михайловича Абрамова и попробую максимально доходчиво и с примерами рассказать об этом замечательном языке тем, кто с ним еще не знаком. Рассказ ориентирован на неподготовленного читателя. Так что, даже если вы впервые услышали слово Haskell…

Это достаточно вольный перевод статьи. Дело в том, что несмотря на конструкции в одну строчку, материал сложен для понимания.
Беря во внимание то, что в комментариях Прелюдия или как полюбить Haskell просили, чтобы код был понятный, я внёс достаточно ремарок, и, надеюсь, код будет понятен и тем, кто далёк от Хаскеля.

Давайте начнём с самого трудного — с самого заголовка: многим непонятны все его слова.
Хаскель — это чистый и ленивый функциональный язык.
Лёб — это немецкий математик, о котором мы поговорим чуть позже.
Ну, и наконец, самое интересное — странные петли.

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

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

Немецкий математик Лёб мигрировал в 39-м году ХХ-го столетия в Великобританию. Лёб, в частности, развивал математическую логику и миру прежде всего известен Теоремой Лёба. Это теорема развивала труды Гёделя о неполноте математики. Теорема Лёба о взаимосвязи между доказуемостью утверждения и самим утверждением, она гласит, что

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

Всю эту сложность высказывания можно записать символически:


Можно ли такую функцию написать на Хаскеле?! Можно! И всего в одну строчку!

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

J – самый ненормальный и самый эффективный язык из известных мне языков. Он позволяет быстро разрабатывать, а также вызывать ненормативную лексику у людей, незнакомых с ним и смотрящих на код.

J слишком необычный. И сложный для изучения. У людей, сталкивающихся с J не хватает мотивации, чтобы его изучить. Синтаксис непривычный.
В этом посте я хотел помочь вам заглянуть дальше, что будет, если вы его изучите и чем он интересен. По своему опыту знаю, что преимущества этого языка сразу не очевидны. В посте я не собираюсь останавливаться на разборе конструкций. Только в обзоре. Предлагаю просто окунуться в примеры, попробовать ощутить мощь языка. Узнать, чем прекрасен язык, без изучения. Писать статьи, обучающие программированию на нем – дело сложное и думаю, не нужное. Он не так прост, чтобы это сделать кратко, а с обучающими материалами на официальном сайте нет никаких проблем. Главное – желание. Им и займемся.

Так уж завелось на хабре, что на каждую холиварную статью «Pro» всегда найдётся статья «Contra».
Я тоже решил не оставлять в одиночестве пост «Что не так с ООП и ФП».



Прямо противоречить написанному смысла не имеет, там ведь описан «вкус», а, как известно, на вкус и цвет… каждый любит свой ЯП.
Нет никакой проблемы с ООП и ФП. Чистота функций — это всего лишь инструмент, равно как и «всё является объектом».
Критика права лишь в одном — в борьбе за миллиметры хорошо видны яркие прорехи, а в любых вырожденных методах недостатки ярко проявляются.
Другое дело, что любые невырожденные методы так же имеют недостатки, только их больше, зато они не так легко заметны.
Любители С++ гнобят полное ООП, Javа гнобит Си++ за неполное ООП, Haskell гнобит другие ФП за грязные функции, остальные ФП гнобят Haskell за излишне чистые функции.
Всё имеет свою оборотную сторону медали.
Тогда почему досталось всё объектам и функциям, а не массивам и указателям?!

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

Если кратко, то как ООП, так и ФП неэффективны, если доходить в их использовании до крайности. Крайностью в ООП считается идея о том что “все что угодно является объектом” (чистое ОП). Крайностью для ФП можно рассматривать чистые функциональные языки программирования.

Известно, что задача определения того, истинна ли некоторая функция Integer -> Bool хотя бы для одного числа вычислительно неразрешима. Однако, нечто, на первый взгляд кажущееся как раз таким оракулом (а именно, функцией (Integer -> Bool) -> Maybe Integer) будет описано в этой статье.

Для начала, зададим свой тип натуральных чисел, практически дословно следуя их обычному математическому определению (почему это нужно будет видно в дальнейшем):

data Nat = Zero | Succ Nat deriving (Eq, Ord, Show)

Другими словами, натуральное число — это либо ноль, либо некоторое натуральное число, увеличенное на единицу (Succ от слова successor).

Также, для удобства, определим основные операции (сложение, умножение, конвертация из Integer) над числами в таком представлении:

instance Num Nat where
    Zero + y = y
    Succ x + y = Succ (x + y)

    Zero * y = Zero
    Succ x * y = y + (x * y)

    fromInteger 0 = Zero
    fromInteger n = Succ (fromInteger (n-1))