Введение

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

Обозначения

В прошлый раз я хотел обозначить морфизм/функцию буквой f, но она была занята для обозначения функтора/переменной типа f – никакой проблемы с точки зрения языка Haskell в этом нет, но при невнимательном прочтении это может вызвать путаницу, и я использовал для морфизма букву g. Пустяк, но всё же, я считаю, что полезно визуально разделять сущности, имеющие разную природу. Обычные типы я буду называть их обычными именами, а вот переменные типов я буду называть маленькими греческими буквами, причём простые (∗) – буквами из начала алфавита, а параметрические (∗ → ∗) – буквами из конца алфавита (θ не из конца, но она смотрится лучше, чем χ, которая слишком похожа на X). Итак, в терминологии категории Hask:

• Объекты: α, β, γ, δ ∷ ∗
• Функторы: θ, φ, ψ, ω ∷ ∗ → ∗
• Морфизмы: f, g, h ∷ α → β

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

Ещё одно замечание, касательно терминологии: как вы уже заметили, то, что я в прошлый раз называл словом “кайнд” (kind), я теперь называю словом “сорт” – это считается общепринятым переводом.

Категория с объектом Hask

Давайте рассмотрим категорию, в которой будет только один объект – сама категория Hask. Что же будет морфизмами в такой категории? Это должны быть какие-то отображения Hask → Hask, и мы уже знаем такой тип отображений – это эндофункторы категории Hask, то есть типы сорта ∗ → ∗, воплощения класса Functor. Теперь нужно продумать как устроены единичный морфизм и композиция в этой категории, так чтобы они удовлетворяли аксиомам.

Вступление

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

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

Эта статья во многом повторяет (в том числе заимствует иллюстрации) раздел из английской Haskell Wikibook, но тем не менее не является непосредственным переводом.

Что такое категория?

Примеры

Для наглядности рассмотрим сначала пару картинок изображающих простые категории. На них есть красные кружочки и стрелки:

Красные кружочки изображают «объекты», а стрелки – «морфизмы».

Я хочу привести один наглядный пример из реальной жизни, который даст какое-то интуитивное представление о природе объектов и морфизмов:

Можно считать города «объектами», а перемещения между городами – «морфизмами». Например, можно представить себе карту авиарейсов (как-то не нашёл я удачную картинку) или карту железных дорог – они будут похожи на картинки выше, только сложнее. Следует обратить внимание на два момента, которые кажутся в реальности само собой разумеющимися, но для дальнейшего имеют важное значение:

• Бывает, что из одного города в другой никак не попасть поездом или самолётом – между этими городами нет морфизмов.
• Если мы перемещаемся в пределах одного и того же города, то это тоже морфизм – мы как бы путешествуем из города в него же.
• Если из Санкт-Петербурга есть поезд до Москвы, а из Москвы есть авиарейс в Амстердам, то мы можем купить билет на поезд и билет на самолёт, “скомбинировать” их и таким образом попасть из Санкт-Петербурга в Амстердам – то есть можно на нашей карте нарисовать стрелку от Санкт-Петербурга до Амстердама изображающую этот скомбинированный морфизм.

Надеюсь, с этим примером всё понятно. А теперь немного формализма для чёткости.

Данный текст является переводом документации Template Haskell, написанной Булатом Зиганшиным. Перевод всего текста разбит на несколько логических частей для облегчения восприятия. Далее курсив в тексте — примечания переводчика. Предыдущие части:

• Часть 1. Необходимый минимум
• Часть 2. Инструменты цитирования кода

Материализация

Материализация (reification) — это средство Template Haskell, позволяющее программисту получить информацию из таблицы символов компилятора. Монадическая функция reify ∷ Name → Q Info возвращает информацию о данном имени: если это глобальный идентификатор (функция, константа, конструктор) – вы получите его тип, если это тип или класс – вы получите его структуру. Определение типа Info можно найти в модуле Language.Haskell.TH.Syntax.
Материализация может быть использована для того, чтобы получить структуру типа, но таким образом нельзя получить тело функции. Если вам нужно материализовать тело функции, то определение функции нужно процитировать и дальше можно будет работать с этим определением с помощью другого шаблона. Например так:

$(optimize [d| fib = … |])

или так

fib = $(optimize [| … |])

На самом деле, в оригинальной статье больше ничего не говорится про материализацию. Не знаю, насколько это содержательная тема – необходимый минимум знаний о ней ограничивается функцией reify и типом Info, но есть некоторые тонкости, связанные например с тем, что можно получить информацию не о любом имени. Если эта тема интересна, я могу собрать какую-нибудь информацию и написать об этом отдельную заметку (или вклеить сюда).

Облегчённое цитирование имён

Чтобы получить имя (∷ Name), соответствующее интересующему идентификатору, можно использовать функцию mkName, но это не безопасное решение, потому что mkName возвращает не квалифицированное имя, которое может интерпретироваться по-разному в зависимости от контекста. А вот код VarE id ← [| foo |] безопасен в этом смысле, так как цитирование квалифицирует имена (получится что-то типа My.Own.Module.foo), но этот код слишком многословный и требует монадический контекст для использования. К счастью, Template Haskell, имеет другую простую форму цитирования имён: 'foo (одинарная кавычка перед foo) имеет тип Name и содержит квалифицированное имя, соответствующее идентификатору foo, так что код let id = 'foo эквивалентен по смыслу коду VarE id ← [| foo |]. Обратите внимание, что эта конструкция имеет простой тип Name (а не Q Exp или Q Name), так что она может быть использована там, где не возможно использование монад, например:

f ∷ Exp → Exp
f (App (Var m) e) |  m == 'map  =  …

Эта новая форма тем не менее является цитированием и подчиняется тем же правилам, что и цитирующие скобки [| … |]. Например, она не может быть использована внутри этих скобок (так нельзя: [| 'foo |]), но и вклеивание к ней не может быть применено (так тоже нельзя: $( 'foo )), потому что для вклейки нужен тип Q …. Более важно то, что эта форма определяется статически, возвращая полностью квалифицированное имя, с однозначной интерпретацией.
Haskell’евские пространства имён немного всё усложняют. Цитата [| P |] означает конструктор данных P, в то время как [t| P |] означает конструктор типа P. Поэтому для “облегчённого цитирования” необходим такой же способ разделения этих сущностей. Для контекста типов используется просто две одинарные кавычки:

• 'Foo означает “конструктор данных Foo в контексте выражения”
• 'foo означает “имя foo в контексте выражения”
• ''Foo означает “конструктор типа Foo в контексте типов”
• ''foo означает “переменная типа foo в контексте типов”

Облегчённая форма цитирования используется в примере генерации воплощений класса Show, который разбирается в конце.

Данный текст является переводом документации Template Haskell, написанной Булатом Зиганшиным. Перевод всего текста разбит на несколько логических частей для облегчения восприятия. Далее курсив в тексте — примечания переводчика. Другие части:

• Часть 1. Необходимый минимум
• Часть 3. Прочие аспекты TH

Монада цитирования

Поскольку шаблоны должны возвращать свои значения обёрнутыми в монаду Q, для этого имеется набор вспомогательных функций, которые “поднимают” (оборачивают в Q) конструкторы типов Exp, Lit, Pat: lamE (соотв. LamE), varE, appE, varP и т.д. В их сигнатурах так же используются переобозначенные поднятые типы: ExpQ = Q Exp, LitQ = Q Lit, PatQ = Q Pat… (все их можно найти в модуле Language.Haskell.TH.Lib). Используя эти функции, можно значительно сократить код, реже используя do-синтаксис.
В TH также есть функция lift, которая поднимает до Q Exp значение любого типа из класса Lift.
В некоторых редких случаях, вам может понадобиться не генерация уникального имени, а использование точного имени идентификатора из внешнего (по отношению к шаблону) кода. Для этих целей есть (чистая) функция mkName ∷ String → Name. Есть также вспомогательная функция dyn s = return (VarE (mkName s)), которая возвращает значение Exp представляющее переменную с данным именем (dyn ∷ String → Q Exp).

Цитирующие скобки

Построение значений Exp, представляющих абстрактное синтаксическое дерево — трудоёмкая и скучная работа. Но к счастью, в Template Haskell есть цитирующие скобки, которые преобразуют конкретный Haskell-код в структуру, представляющую его.

Данный текст является переводом документации Template Haskell, написанной Булатом Зиганшиным. Перевод всего текста разбит на несколько логических частей для облегчения восприятия. Далее курсив в тексте — примечания переводчика.

Template Haskell (далее TH) — это расширение языка Haskell предназначенное для мета-программирования. Оно даёт возможность алгоритмического построения программы на стадии компиляции. Это позволяет разработчику использовать различные техники программирования, не доступные в самом Haskell’е, такие как, макро-подобные расширения, направляемые пользователем оптимизации (например inlining), обобщённое программирование (polytypic programming), генерация вспомогательных структур данных и функций из имеющихся. К примеру, код

yell file line = fail ($(printf "Error in file %s line %d") file line)

может быть преобразован с помощью TH в

yell file line = fail ((\x1 x2 -> "Error in file "++x1++" line "++show x2) file line)

Другой пример, код

data T = A Int String | B Integer | C
$(deriveShow ''T)

может быть преобразован в

data T = A Int String | B Integer | C
instance Show T
    show (A x1 x2) = "A "++show x1++" "++show x2
    show (B x1)    = "B "++show x1
    show C         = "C"

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

1. Как Haskell-код представляется в шаблонах (TH-функциях)
2. Как монада цитирования используется для унификации имён
3. Как сгенерированный TH-код вставляется в программу

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

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