Haskell *

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

Статья постарается быть относительно real-world, но при этом не утомлять читателя объёмом или экзотическими предметными областями. «Графика и игры в обучении — это всегда sexy», как завещал великий В. С. Луговский, поэтому я набросаю простую игру, всенародно любимый «Сапёр». Разработка будет вестись «сверху вниз» — это удручающе малораспространённая, но заслуживающая пристального внимания (как и сам хаскель) методология, которая когда-то давно встретилась в отличной статье о шашках в «Практике функционального программирования», и с тех пор запала в душу.

Читая М. Липовача «Изучай Haskell во имя добра!», я поначалу не понимал, чем частичное применение отличается от каррирования. Потратил некоторое время на разбор данного вопроса и набросал себе «шпаргалку» по обозначенной теме.

Композиция логирования

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

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

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

В 2001 году, Эдсгер Дейкстра написал письмо экономическому совету университета Техаса. В нем знаменитый ученый призывает членов совета задуматься о смене языка программирования для вводного курса. К сожалению, язык был заменен на Java. Примерно в то же время MIT сменили язык курса «Структура и интерпретация компьютерных программ» с функционального Scheme (диалекта LISP) на Python.

Сегодня мы публикуем перевод этого письма.

Членам Экономического Совета

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

Имя любого идентификатора в Haskell начинается с буквы, за которой следует
ноль или более букв, цифр, символов подчёркивания _ и одинарной кавычки '. В качестве буквы рассматриваются только латинские символы в интервалах a..z и A..Z. Символ _ принято считать буквой, в следствии чего имя функции может начинаться с этого символа, но не может состоять только из него, в виду того, что в образцах Haskell он обозначает любое значение. Имена функций, составленные не из символов набора ascSymbol, обязательно должны начинаться со строчной буквы или символа _. Имена пространств имён, типов данных, конструкторов данных и классов типов составленные не из символов набора ascSymbol должны начинаться с прописной буквы. В данной заметке даётся некоторая информация об использовании символов набора ascSymbol в идентификаторах Haskell.

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

ghci> 3 * sqrt(24 ^ 2 + 16 ^ 2) == sqrt(72 ^ 2 + 48 ^ 2)
False

Причина такого нарушения в том, что выражения в этом равенстве вычисляются лишь приближенно:

ghci> 3 * sqrt(24 ^ 2 + 16 ^ 2)
86.53323061113574
ghci> sqrt(72 ^ 2 + 48 ^ 2)
86.53323061113575
ghci> sqrt(72 ^ 2 + 48 ^ 2) - 3 * sqrt(24 ^ 2 + 16 ^ 2)
1.4210854715202004e-14

Различие здесь только в последнем (четырнадцатом!) знаке после запятой, но этого уже достаточно, чтобы сравнение оказалось ложным.

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

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

Это четвертая статья в цикле «Теория категорий для программистов».

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

Без объектов

Самая простая категория — без объектов и, как следствие, без морфизмов.

Это третья статья в цикле «Теория категорий для программистов».

Категория типов и функций играет важную роль в программировании, так что давайте поговорим о том, что такое типы, и зачем они нам нужны.

Кому нужны типы?

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

Маленькая Лямбда решила, что уборку в комнате можно отложить и на потом.

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

foldl (+) 0 [1..10^8]

потребует для своего вычисления гигабайты памяти.

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

Тема ленивых вычислений рассматривалась во многих учебниках (например, в книге Саймона Томпсона «Haskell — The Craft of Functional Programming»), но информацию о них, кажется, всё ещё проблематично найти в сети. Надеюсь, моё руководство посодействует решению этой проблемы.

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

Это вторая статья в цикле «Теория категорий для программистов».

Категория — очень простая концепция.

Категория состоит из объектов и стрелок, которые направлены между ними. Поэтому, категории так легко представить графически. Объект можно нарисовать в виде круга или точки, а стрелки — просто стрелки между ними. (Просто для разнообразия, я буду время от времени рисовать объекты, как поросят а стрелки, как фейерверки.) Но суть категории — композиция. Или, если вам больше нравится, суть композиции — категория. Стрелки компонуются так, что если у вас есть стрелка от объекта А к объекту B, и еще одна стрелка из объекта B в C, то должна быть стрелка, — их композиция, — от А до С.

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

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

Доброго времени. Ранее мы делали пост «Новая книга по Haskell на русском?»
В итоге книга вчера пришла из типографии



Изучаем Haskell. Библиотека программиста
Автор: Алехандро Мена
Прототип: Beginning Haskell: A Project-Based Approach

Эта книга поможет вам быстро освоить базовые концепции языка программирования Haskell, его библиотеки и компоненты, а также заложит основы функциональной парадигмы программирования, которая становится все более значимой в современном мире разработки ПО. Книга предлагает проектный подход к освоению материала, используя в качестве прототипа проект реализации интернет-магазина. Здесь рассматривается экосистема языка Haskell и его вспомогательных средств, инструменты Cabal для управление проектами, модули HUnit и QuickCheck для тестирования программ, фреймворк Scotty для разработки веб-приложений, Persistent и Esqueleto — для управления базами данных и многие другие компоненты и библиотеки Haskell.

Статья будет состоять из 3х частей:
Пальчиковые деревья (часть 1. Представление)
Пальчиковые деревья (часть 2. Операции)
Пальчиковые деревья (часть 3. Применение)

Пальчиковые Деревья как Последовательности

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

Вышла недавно статья на Хабре о том, как можно самому создать на функциональном языке такие структуры как Очередь (первый зашёл, первый вышел) и Дек (напоминает двусторонний стек — первый зашёл, первый вышел с обоих концов). Посмотрел я на этот код и понял, что он жутко неэффективен — сложность порядка O(n). Быстро сообразить, как создать структуры с O(1) у меня не вышло, поэтому я открыл код библиотечной реализации. Но там была не лёгкая и понятная реализация, а <много кода>. Это было описание пальчиковых деревьев, необходимость и элегантность которых для этой структуры данных хорошо раскрывается текущей статьёй.

Пальчиковые деревья

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

Статья будет состоять из 3-х частей:

Пальчиковые деревья (Часть 1. Представление)
Пальчиковые деревья (часть 2. Операции)
Пальчиковые деревья (Часть 3. Применение)

Разрабатывая структуру данных

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



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

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

Многие слышали про тайловые оконные менеджеры, некоторые даже слышали о XMonad. А ребята из Google даже променяли Unity/Gnome на XMonad. Что же это такое, как это настраивать и как с этим жить? Краткий workaround для любителей кастомизировать всё подряд.

Всем привет! Недавно вышел перевод статьи о том, как TJ Holowaychuk прощался с Node.js, решив двигаться в сторону Go. В конце статьи была ссылка на посвящённый сравнению и критике языка Go пост Уилла Ягера, который просили перевести — собственно, с результатами перевода я и предлагаю ознакомиться. Я пытался более-менее сохранить как многословный стиль изложения, присущий автору, так и оригинальную разбивку на предложения и параграфы.
Буду очень рад любым конструктивным замечаниям и предложениям по переводу, опечаткам и/или оформлению, но очень прошу помнить, что точка зрения переводчика может не совпадать с позицией автора переведённой статьи.

Одним вечером я наткнулся на статью о реализации одномерного клеточного автомата с помощью комонад, однако материал неполон и немного устарел, в связи с чем решил написать русскоязычную адаптацию (заодно рассмотрев двумерные клеточные автоматы на примере Game of Life):

Данная статья составлена преподавателем Академического университета Валерием Исаевым по материалам практики по курсу функционального программирования.

Полагаю, ни для кого не секрет, что написание многопоточных приложений связано с целым рядом проблем, отсутствующих при разработке однопоточных программ.
Одна из проблем заключается в тестировании приложения.
Мы не можем контролировать порядок, в котором выполняются операции, следовательно, не поддается контролю и результат выполнения программы. Даже если мы получим ошибку, наступить на те же грабли второй раз будет не так-то просто.
Хочу предложить небольшой рецепт того, как можно протестировать многопоточное приложение.
Из ингредиентов нам понадобятся: haskell, QuickCheck, немного монад, соль/перец по вкусу.

За применение в бизнесе мнимых величин уже дали премию. Теперь интересно что-нибудь поиметь с дуальных.
Дуальное число — это расширение поля действительных чисел (или любого другого, например комплексных) вида a + εb, где a и b — числа из исходного поля. При этом полагается, что ε ε = 0.
Оказывается, у таких странных чисел есть практическое приложение.

Основным полезным свойством дуальных чисел является
f(a + εb) = f(a) + εf'(a)b.
Когда у нас есть формула для f(x), получить производную f'(x) труда не составит. Но часто f(x) доступно только в виде алгоритма — например как решение специальным образом составленной системы линейных уравнений. Запустив алгоритм с исходными данными, в которые добавлена ε мы получим результат и значение производной по одному из параметров.

Свойства и законы. Сценарии. Inversion of Control в Haskell.

Совсем немного теории

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