Haskell *

West of House
You are standing in an open field west of a white house, with a boarded front door.
There is a small mailbox here.

> open mailbox
Opening the small mailbox reveals a leaflet.

> read leaflet
(Taken)
«WELCOME TO ZORK!

ZORK is a game of adventure, danger, and low cunning. In it you will explore some of the most amazing territory ever by mortals. No computer should be without one!»

Содержание:
Приветствие
Часть 1 — Преддверие
Часть 2 — Лес
Часть 3 — Поляна
Часть 4 — Вид каньона
Часть 5 — Зал

Часть 1,
в которой мы познакомимся с не всеми основами языка Haskell и напишем одну полезную для квеста функцию.

Итак, вы стоите в самом начале, перед закрытой дверью и видите почтовый ящик.

Добрый день, любители приключений!

Вы, конечно, играли в текстовую приключенческую игру Zork. Вы еще помните эти недели, когда вы искали вход в подземелье, или думали, как пройти мимо гоблинов с дубинками. Вы помните, как махали мечом, вы даже испробовали различные варианты «hit self» и «kill self». Программа понимала ваши команды, — результат был предсказуем… Весело и удивительно было изучать текстовый мир Zork! И вам, конечно, хотелось создать что-то подобное своими руками. Так может, попробуем? Вместе? В этом руководстве вы будете шаг за шагом создавать свою текстовую игру на замечательном языке Haskell.

Я постараюсь объяснять все используемые концепции так детально, как будто рассказываю это тем, кто ничего не знает о 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, мне удалось взять у него небольшое спонтанное видеоинтервью, которое и предлагаю Вашему вниманию.