Это шестая статья из цикла «Теория категорий для программистов». Предыдущие статьи уже публиковались на Хабре:
0. Теория категорий для программистов: предисловие
1. Категория: суть композиции
2. Типы и функции
3. Категории, большие и малые
4. Категории Клейсли
5. Произведения и копроизведения

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

Рассмотрим подробнее место произведения и копроизведения типов в программировании.

Произведение типов

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

Строго говоря, произведение типов не коммутативно: нельзя подставить пару типа (Int, Bool) вместо (Bool, Int), хотя они и содержат одни и те же данные. Однако произведение коммутативно с точностью до изоморфизма, задаваемого функцией swap, которая обратна самой себе:

swap :: (a, b) -> (b, a)
swap (x, y) = (y, x)

Можно рассматривать такие пары как различные форматы хранения одной и той же информации, как big endian и little endian.

Это пятая статья из цикла «Теория категорий для программистов». Предыдущие статьи уже публиковались на Хабре в переводе Monnoroch:
0. Теория категорий для программистов: предисловие
1. Категория: суть композиции
2. Типы и функции
3. Категории, большие и малые
4. Категории Клейсли

На КДПВ поросенок Петр заводит по одному трактору в каждый объект категории.

Следуй по стрелкам

Древнегреческий драматург Еврипид писал «Всякий человек подобен своему окружению». Это верно и для теории категорий. Выделить определенный объект категории можно только путем описания характера его взаимоотношений с другими объектами (и самим собой), где отношения — это морфизмы.

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

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

Статья расчитана на новичков в Objective-C и рассказывает об одном способе выстрелить себе в ногу. Мы попытаемся создать два различных объекта NSString с одинаковым текстом, исследуем реакцию на это различных компиляторов, а также узнаем, при каких условиях NSLog(@"%@", @«123456789») выведет совсем не «123456789».

Объекты NSString и указатели

Как вы думаете, что выведет следующий код?

В недавней статье предложена реализация каррирования (currying) и частичного применения (partial function application) на PHP. Ее фундаментальным недостатком является то, что результатом каррирования является не функция, а объект. Он уже не может быть передан в качестве callback-параметра, а для подстановки аргументов приходится использовать специальный синтаксис. В настоящем тексте предлагается новая, прозрачная реализация этих конструкций для PHP 5.3 и выше.

Термин currying происходит от фамилии американского математика Haskell Curry. Второе значение слова currying — выделка дубленой кожи.

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

Эмуляция каррирования и частичного применения на PHP — это один из примеров того, что Макконнелл в «Совершенном коде» (гл. 4.3) называет программированием с использованием языка, а не на языке.

В заметке обсуждаются алгоритмы решета для поиска простых чисел. Мы подробно рассмотрим классическое решето Эратосфена, особенности его реализации на популярных языках программирования, параллелизацию и оптимизацию, а затем опишем более современное и быстрое решето Аткина. Если материал о решете Эратосфена предназначен в первую очередь уберечь новичков от регулярного хождения по граблям, то алгоритм решета Аткина ранее на Хабрахабре не описывался.

На снимке — скульптура абстрактного экспрессиониста Марка Ди Суверо «Решето Эратосфена», установленная в кампусе Стэнфорского университета

Демонстрируем некоторые особенности написания TeX-макросов, встраивая в TeX калькулятор теоретико-числовых функций.

Постановка задачи

Время от времени мне приходится набирать очередной текст, сопровождаемый примерами вычисления теоретико-числовых функций: функция Эйлера φ, функция делителей τ, функция Кармайкла λ. Раньше это делалось так: запускаем любимый калькулятор (мой выбор — PARI/GP), в нем все считаем и копируем выкладки в ТеХ. Изменились исходные данные — снова в калькулятор и обратно. Много возни, много шансов забыть заменить какой-то промежуточный результат. Да и просто мышкой махать надоедает. Хочется автоматизировать этот процесс хотя бы для самых распространенных функций, чтобы можно было написать

$\phi(1001)=\Phi(1001)$

и получить на печати