Haskell *

Любой программист, изучающий haskell, рано или поздно встречается с таким непостижимым понятием как монада. Для многих знакомство с языком заканчивается монадами. Существует множество руководств по монадам, и постоянно появляются новые (1). Те немногие, кто понимает монады, тщательно скрывают свои знания, объясняя монады в терминах эндофункторов и естественных преобразований (2). Ни один опытный программист не может найти монадам место в своей устоявшейся картине мира.

В результате java-программисты только посмеиваются над хаскелем, не отрываясь от своего миллионострочного энтерпрайзного проекта. Разработчики на С++ патчат свои сверх-быстрые приложения и придумывают ещё более умные указатели. Веб-разработчики листают примеры и огромные спецификации по css, xml и javascript. А те из них, кто в свободное время изучает haskell, сталкивается с труднопреодолимым препятствием, имя которому монады.

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

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

Нашей целью является описать последовательность приёма и отправок сообщений при общении с некоторым собеседником, а также иметь возможность использовать ввод/вывод (например, обращение к базе) между приёмами и отправками сообщений.

Как бы в коде на вашем предпочитаемом языке выглядел, например, такой диалог, с учётом того, что в любой момент (между любыми из этих пунктов) могут прийти какие-то другие запросы, которые тоже надо обработать, но не впутать случайно в этот диалог:
1. Посылаем число
2. Приходит число в ответ
3. Посылаем число из п.2 в квадрате
4. В ответ опять число
5. Выводим на консоль сумму чисел п.2 и п.4

Вот как это будет выглядеть на Haskell (функция example, разумеется, неблокирующая):
example :: Int -> AIO ()<br>
example v = do<br>
    x <- request v<br>
    y <- request (x * x)<br>
    io $ print (x + y)<br>

Сравните это с блокирующей похожей функцией, которая, к примеру, запрашивает ответ у пользователя:
example :: Int -> IO ()<br>
example v = do<br>
    x <- request v<br>
    y <- request (x * x)<br>
    print (x + y)<br>


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

Я отношу себя к категории ленивых фотолюбителей. У меня есть неплохая «беззеркальная зеркалка», иногда на меня нападает желание пощёлкать чего-нибудь вокруг себя. Однако я ленив, и ковыряться потом в полученном фотоархиве у меня ни времени, ни желания нет. Как правило фотографии просматриваются один-два раза сразу после съемки путём подключения фотоаппарата к телевизору через HDMI кабель. Затем фотографии отправляются в небытие каталог ~/Pictures/Photos/Unsorted и, как правило, остаются там навсегда. С различным спец. ПО я как-то не сдружился, посему этот бардак просуществовал почти два года. И вот, на волне изучения Haskell, я созрел для решения проблемы.

Странно, что это пришло мне в голову — я просто смотрел на Common Lisp и объяснение принципов его работы, ну еще немного на инструментарий Haskell.

И да придет Haskell…

Haskell — она как «та девчонка», ну вы знаете…

Прочитав статью решил проверить, насколько пригоден для этого Haskell. Сразу скажу, сам Haskell пригоден весьма неплохо, но вот, пробежавшись по hackage.haskell.org, я сразу обнаружил проблемы с библиотеками для работы с PDF, что и поставило крест на полноценной реализации.
Но я решил всё же проделать часть работы, дабы показать, как та же задача могла бы быть сделана на Haskell, если бы да кабы…

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

Наиболее удобным способом является определение по Пеано. Однако оно определяет счетные множества, но не даёт определенного сконструированного множества. Другой подход — определить натуральное число как специальное кардинальное, а именно мощность конечного множества. Третий — нумералы Чёрча.

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

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

Вместо вступления (перевод начался):

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

В данной статье речь пойдёт о небольшой программке, которая репостит твиты в статус во вконтакте.
Задача довольно простая и совершенно неоригинальная. Началось всё с того, что я прочитал статью на Хабре о том, как это решается на python'е и аналогичную статью про php. В интернетах вроде бы даже какие-то онлайн сервисы есть специально для этой задачи. Но тут весь цимус в том, чтобы решить эту несложную задачу самому, используя свои любимые инструменты. Собственно решение на php появилось позже и с такой же целью.

Ну и на чём же писал я? На haskell, natürlich!
Дальше подробно расскажу о том, как я всё сделал и как это повторить. Никаких особых знаний для понимания, пожалуй, не требуется.

Эта статья объясняет, как выполнять ввод и вывод в Haskell, не пытаясь дать никакого понимания о монадах в целом. Мы начнём с простейшего примера, а затем постепенно перейдём к более сложным. Вы можете дочитать статью до конца, а можете остановиться после любого раздела: каждый последующий раздел позволит вам справиться с новыми задачами. Мы предполагаем знакомство с основами Haskell, в объёме глав с 1 по 6 книги «Programming in Haskell» Грэма Хаттона. [Прим. переводчика: главы «Введение», «Первые шаги», «Типы и классы», «Определение функций», «Выборки из списков», «Рекурсивные функции»]

Когда мне впервые задали вопрос о том может ли существовать функция вида Func<Func<T,T>,T> без использования конструкций вида default(T) он поверг меня в глубокий когнитивный диссонанс.
Как может существовать функция у которой неоткуда взять значения? Об очевидном варианте

T Fix<T>(Func<T,T> func){
   return func(Fix(func));
}

я не мог даже подумать. Разве возможно делать такие функции? Она будет вызываться бесконечно и не даст результата. В языках типа C# такая конструкция и правда вызовет зацикливание, но вполне может работать в языках вроде питона или хаскеля. Сейчас будет немного кода на Haskell, надеюсь синтаксис будет более-менее понятен всем.

Кирпичёв правильно пишет про небрежность интуитивного понимания императивных языков: http://antilamer.livejournal.com/300607.html.

Однако, мне кажется, что важно было бы озвучить, что всё то, что сейчас скрывается под именем «монада» — само по себе достаточно спутанно в плане педагогики и евангелизма.  Классическая шутка SPJ/Вадлера звучит как «нам следовало назвать ЭТО warm fuzzy things, чтобы не пугать людей теоркатом».  Шутка поразительно недальновидная.   Проблема лежит в той же плоскости, что и называние стоящих перед тобой задач словом «stuff» (это то, с чем борется Аллен в своём GTD).  
Монады в настоящий момент являются миру как сложный ком из исторически обусловленных причин, проблем, решений, технических возможностей и теоретических основ (как алгебраических, так и аспектов теории вычислений). 
Все эти наслоения можно (и нужно) расщепить в первом приближении так (порядок приблизительно случайный):

• стремление к экспликации эффектов (чистое внедрение императивно-подобных моментов в вычисление), (см. труды Вадлера);  здесь мы включаем ввод-вывод, STM, параллельные вычисления и проч.)
• удобный механизм для материализации базовых микро-стратегий вычисления — вызов функции (call-by-name/call-by-value), многозначность, смена состояния (присваивания!), обработка исключений, останов при неудаче, continuations, бэктрекинг;

• typeclasses как механизм внесения монад в язык, и как следствие — удобный механизм для мета-перехвата вычисления (невероятно удобно для domain-specific embedded languages);
• строгая проверка типов, проистекающая из использования typeclasses, и позволяющая механически проверять корректность использования объектов;
• существование монадических законов, в которые укладываются монады, что позволяет материализовывать абстрактные комбинаторы; это позволяет находить порой неожиданные изоморфизмы между различными предметными областями, а также помогает при оптимизации и верификации программ;
• проработанная теоретическая основа (теория категорий), на которой базируются монады; это облегчает жизнь создателям базовых библиотек, на которых потом базируется всё реальное программирование;
• монады — лишь один из классов в длинной цепочке интересных алгебраически обусловленных классов, некоторые из которых слабее монад, а некоторые — сильнее: Functor, Applicative, Monoid, Traversable, Foldable, Monad со товарищи, Arrow со товарищи;
• стремление к материализации некоторых видов вычислений в алгебраическую структуру (моноидальные вычисления); это открывает широкий простор для оптимизаций, верификации программ, создания абстрактных комбинаторов, а также устранение unbounded recursion — по мощности результатов это похоже на то, как когда-то ввод-вывод был надежно изолирован в IO Monad;

Потратим по паре абзацев на каждый пункт.

Я долго (несколько лет) не решался составить окончательное мнение о Haskell'e: слишком противоречивы были мысли. И вот, наконец, благодаря этой записи о разборе программки определения двудольности графа я могу это сделать :)

Я понял, что Haskell-программисты — в основном, нужно сказать, хобби-программисты — это те, кто программирует не решение задачи, алгоритм, систему, а Haskell! [1] Посмотрите, какой простой алгоритм описан в заметке, а сколько вокруг него нагромождено языковых конструкций, объяснений и дискуссий. (Чтоб понять, насколько алгоритм прост, можете посмотреть в комментариях варианты на Lisp'е, Python'е).

Мне хорошо знакомо это умонастроение — когда в погоне за максимальным использованием мощи языка забываешь о самой задаче,— поскольку в Lisp-мире оно тоже часто встречается: есть языки, которые способны действительно увлечь. И выражение «это взорвало мне мозг» часто звучат и по поводу Lisp'а, и по поводу Haskell'а. Но это же — фигня! Конечно, не может не радовать узнать что-то новое, но не нужно же радоваться этому, как ребенок новой игрушке. Хороший язык программирования должен быть максимально понятен и прост, должен давать человеку свободу самовыражения. Честно говоря, именно этому я обрадовался, когда открыл для себя Lisp: что нашел то, что искал. А не тому, что увидел какую-то конструкцию или изворот, который не доводилось встречать раньше.

Здесь мы будем разбирать по буквам некую программу (компилятор VM) на Хаскеле. На вход этому компилятору дается бинарный файл с инструкциями некоего процессора, где в этих инструкциях описываются некие вычисления. На выходе нашего компилятора получается текст программы, тоже на Хаскеле, которая производит те же самые вычисления, с большой скоростью. Возможно, это не компилятор, а декомпилятор, не знаю. Сравнение работы результирующих программ на Haskell/Java приводится в предыдущем посте.

Во время недавнего визите в Москву Саймона Пейтона-Джонса, одного из создателей языка Haskell, мне удалось взять у него небольшое спонтанное видеоинтервью, которое и предлагаю Вашему вниманию.

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

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

Предыдущие статьи:
Типы данных, паттернг матчинг и функции
Основы

В данной статье я расскажу как написать свой парсер ini-файлов на Haskell. За основу возьму контекстно-свободную грамматику, построенную в моей предыдущей статье. Для построения парсера будет использоваться библиотека Parsec, которая позволяет строить свои собственные парсеры комбинируя готовые примитивные парсеры при помощи парсерных комбинаторов.

Важно: в данной статье предполагается, что читатель знаком с основами Haskell. Если это не так, то я советую сначала прочитать пару статей для новичков (их можно найти в том числе и на Хабре).

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

Предыдущие статьи:
Основы
Последующие статьи:
Классы типов, монады

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

Последующие статьи:
Типы данных, паттерн матчинг и функции
Классы типов, монады