Категории

Есть такой раздел математики — теория категорий, и ложится она на всё, что мы обсуждаем, как нельзя лучше, — так что мы просто обязаны немного о ней поговорить. Мысль в её основе вызывающе проста: забыть, что лежит внутри математических структур, и смотреть только на связи между ними. Работает теория всего с двумя видами сущностей. Первые — объекты: $A, B, C, \dots$; что они такое, категорию не интересует. Вторые — морфизмы, они же стрелки: у каждой есть источник и цель, $f : A$ $\to B$.

Стрелки могут склеиваться: например, для $f : A$ $\to B$ и $g : B$ $\to C$ определена композиция $g \circ f : A$ $\to C$. Дальше — две аксиомы. Первая: композиция ассоциативна, $h \circ (g \circ f)$ $= (h \circ g) \circ f$. Вторая: у каждого объекта есть тождественная стрелка $\mathrm{id}_A : A$ $\to A$, нейтральная к композиции: $f \circ \mathrm{id}$ $= \mathrm{id} \circ f$ $= f$. Объекты, стрелки и две аксиомы — это и есть категория.

В Haskell этот паттерн выделен в класс типов — $\mathtt{Category}$ из модуля $\mathtt{Control.Category}$:

class Category cat where
  id  :: cat a a
  (.) :: cat b c -> cat a b -> cat a c

-- законы класса — в точности аксиомы категории:
f . id == f
id . f == f
(f . g) . h == f . (g . h)

Здесь $\mathtt{cat}$ — сама стрелка, параметризованная источником и целью (род $*$ $\to *$ $\to *$). В общем-то самый всеобъемлющий инстанс категории — это $Hask$: объекты — типы Haskell, морфизмы — функции между ними, композиция — $\mathtt{(.)}$ из Prelude, тождество — $\mathtt{id}$:

instance Category (->) where
  id x = x
  (g . f) x = g (f x)

show   :: Int -> String      -- морфизм Int -> String
length :: String -> Int      -- морфизм String -> Int

length . show :: Int -> Int  -- их композиция — тоже морфизм

Настоящая ценность теории категорий для нас — то, что все конструкции, которые мы обсудили в этой главе, формулируются на её языке очень чисто и чётко:

• моноид — категория с одним объектом: морфизмы — элементы моноида, $(\mathbin{\mathtt{<>}})$ — композиция, $\mathtt{mempty}$ — тождество;
• функтор — отображение категории в категорию: объекты переходят в объекты, стрелки — в стрелки, а тождество и композиция сохраняются (это в точности законы $\mathtt{fmap}$); наши функторы переводят $Hask$ в него же, поэтому зовутся эндофункторами — приставка «эндо-» по-гречески значит «внутри»: функтор из категории в неё же саму;
• аппликативный функтор — моноидальный функтор: помимо стрелок он переносит и пары, $\mathtt{liftA2}\;(,)$ склеивает $(f\,a,\;f\,b)$ в $f\,(a,\,b)$, а $\mathtt{pure}$ даёт единицу;
• монада — категория стрелок Клейсли $a$ $\to m\,b$ с композицией $(\mathbin{\mathtt{>=>}})$ и тождеством $\mathtt{pure}$;
• Foldable — свёртка в категорию с одним объектом: $\mathtt{foldMap}$ увозит элементы структуры в моноид и там склеивает;
• Traversable — перестановка двух эндофункторов местами: $\mathtt{sequenceA} \mathbin{\mathtt{::}} t\,(f\,a)$ $\to f\,(t\,a)$.

Пункт про монаду можно потрогать руками: категория Клейсли — это newtype-обёртка с инстансом $\mathtt{Category}$:

newtype Kleisli m a b = Kleisli { runKleisli :: a -> m b }

instance Monad m => Category (Kleisli m) where
  id                    = Kleisli pure
  Kleisli g . Kleisli f = Kleisli (f >=> g)

-- знакомый half — теперь как стрелка Клейсли:
half :: Kleisli Maybe Int Int
half = Kleisli (\x -> if even x then Just (x `div` 2) else Nothing)

quarter :: Kleisli Maybe Int Int
quarter = half . half          -- обычная точка склеила эффектные стрелки

runKleisli quarter 12   -- Just 3
runKleisli quarter 6    -- Nothing   (3 нечётно — вторая половинка не взялась)

Проверить законы $\mathtt{Category}$ для этого инстанса — значит проверить законы монады: тождество $\mathtt{pure}$ и ассоциативность $(\mathbin{\mathtt{>=>}})$ мы уже видели в разделе о стрелках Клейсли. Монада и её категория Клейсли восстанавливаются друг из друга: это одна конструкция, записанная двумя способами.

К Haskell мы пришли тропой λ-исчисления: термы, редукции, типы. Но можно было идти и с другой стороны: типизированное λ-исчисление и декартово замкнутые категории — один и тот же предмет на двух языках. Тогда типы — это объекты, программы — морфизмы, а конструкции этой главы — категорные определения.