Data Science/Machine Learning
0,0
рейтинг
19 января 2015 в 16:29

Разработка → Категории, большие и малые перевод

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

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

Без объектов


Самая простая категория — без объектов и, как следствие, без морфизмов. Это очень грустная категория, но она важна в контексте других категорий, например, в категории всех категорий (да, такая есть). Если вы считаете, что пустое множество осмысленно, то почему бы не быть пустой категории?

Простые графы


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

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

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

Порядки


А теперь кое-что совсем другое! Категория, в которой морфизмы — отношения между объектами: отношение меньше или равно. Давайте проверим, действительно ли это является категорией. У нас есть единичные морфизмы? Каждый объект меньше или равен самому себе! У нас есть композиция? Если A <= B и B <= С, то А <= C! Композиция ассоциативна? Да! Множество с таким соотношением называется предпорядок, и мы показали, что предпорядок — это категория.

Можно так же взять более сильную зависимость, которая удовлетворяет дополнительному условию, что если A <= В и В <= A то A должен быть такой же, как B. Это называется частичным порядком.

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

Охарактеризуем эти упорядоченные множества, как категории. Предпорядок — это категория, где есть не более одного морфизма из любого объекта A в любой объект B. Еще одно название для такой категории «тонкая». Предпорядок — это тонкая категория.

Множество морфизмов из объекта a в объект b в категории C называется hom-множество и записывается как C(a, b) (или, иногда, HomC(a, b)). Таким образом, каждое hom-множество в предпорядке либо пустое, либо одноэлементное, в том числе и hom-множество С(a, a), множество морфизмов из a в само себя, которое должно быть одноэлементным и содержать только единичный морфизм. В предпорядке можно иметь циклы, в частичном же порядке они запрещены.

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

Очень важно уметь распознавать предпорядки, частичные и полные порядки из-за сортировки. Алгоритмы сортировки, например, быстрая сортировка, пузырьковая сортировка, сортировка слиянием, и т.д., могут работать корректно только на полных порядках. Частичные порядки могут быть отсортированы с помощью топологической сортировки.

Моноид, как множество


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

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

Например, натуральные числа со сложением и нулем образуют моноид. Ассоциативность означает, что:
(a + b) + c = a + (b + c)

(Другими словами, мы можем опустить скобки при сложении чисел.)

Нейтральный элемент — ноль потому, что:
0 + a = a

и
a + 0 = a

Второе уравнение излишне потому, что сложение коммутативно (a + b = b + a), но коммутативность не является частью определения моноида. Например, конкатенация не является коммутативной но она образует моноид. Нейтральный элемент для конкатенации строк, кстати, будет пустой строкой, которая может быть присоединена с любой стороны строки без ее изменения.

В Haskell мы можем определить класс типов для моноидов — тип, для которого существует нейтральный элемент называемый mempty и бинарная операция с названием mappend:
class Monoid m where
    mempty  :: m
    mappend :: m -> m -> m

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

Обратите внимание, что в Haskell нет никакого способа выразить моноидальные свойства mempty и mappend (то есть то, что mempty нейтральна и что mappend ассоциативна). Ответственность за это лежит на программисте. (прим. переводчика: в GHC есть похожий механизм, предназначенный для другой цели, но он может использоваться, как известный компилятору комментарий: www.haskell.org/haskellwiki/GHC/Using_rules)

Классы Haskell не так навязчивы, как классы C++. Когда вы определяете новый тип, вы не должны указывать его класс заранее. Вы можете полениться и объявить, что данный тип будет экземпляром некоторого класса гораздо позже. В качестве примера, давайте объявим, что тип String — моноид, предоставив реализацию mempty и mappend (это, по сути, сделали за вас в стандартной Prelude):
instance Monoid String where
    mempty = ""
    mappend = (++)

Здесь мы повторно использовали оператор конкатенации списков (++) потому, что строка, на самом деле, — список символов.

Немного о синтаксисе Haskell: любой инфиксный оператор может быть превращен в двухаргументную функцию с помощью заключения его в скобки. Имея две строки, вы можете объединить их, вставив между ними ++:
"Hello " ++ "world!"

или передав их в качестве двух аргументов в функцию (++):
(++) "Hello " "world!"

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

Стоит заметить, что Haskell дает возможность выразить равенство функций напрямую:
mappend = (++)

Концептуально, это не то же самое, что и равенство значений, возвращаемых функцией:
mappend s1 s2 = (++) s1 s2

Первое представляет равенство морфизмов в категории Hask (или Set, если игнорировать bottom). Такие уравнения не только более емкие, но и часто обобщаемы и на другие категории. Второе называется экстенсиональным равенством, и заявляет тот факт, что для любых двух входных строк, результаты mappend и (++) равны. Так как значения аргументов иногда называют точками (например: значение f в точке х), это называется точечной нотацией. Функциональное равенство без указания аргументов называется безточечной нотацией. (Кстати, уравнения в безточечной нотации часто включают композицию функций, которую обозначают в виде точки, так что новичкам такое название может казаться странным.)

Ближайшим аналогом объявления моноида в C++ будет предложенный синтаксис для концептов.
template<class T>
  T mempty = delete;

template<class T>
  T mappend(T, T) = delete;

template<class M>
  concept bool Monoid = requires (M m) {
    { mempty<M> } -> M;
    { mappend(m, m); } -> M;
  };

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

Ключевое слово delete означает, что значение по умолчанию не определено: они должны быть указаны индивидуально для каждого случая. Так же, нет реализации по умолчанию для mappend.

Концепт Monoid является предикатом (отсюда тип bool), который проверяет, существуют ли соответствующие определения mempty и mappend для данного типа М.

Реализовать концепт Monoid можно, предоставив соответствующие специализации и перегрузки:
template<> 
std::string mempty<std::string> = {""};

std::string mappend(std::string s1, std::string s2) {
    return s1 + s2;
}

Моноид как категория


Это было «знакомое» определение моноида в терминах элементов множества. Но, как вы знаете, в теории категорий мы пытаемся уйти от множеств и их элементов, а вместо этого говорить об объектах и морфизмах. Так давайте немного изменим наш ход мысли, и подумаем о применении бинарного оператора, как об их «перемешивании» или «сдвиге» внутри множества.

Например, существует операция добавления 5 к любому натуральному числу. Она отображает 0 в 5, 1 в 6, 2 в 7, и так далее. Это функция, определенная на множестве натуральных чисел. Это хорошо: у нас есть функция и множество. В общем, для любого числа n есть функция добавления n — «сумматор» n.

Как эти сумматоры компоновать? Композиция функции, которая добавляет 5, с функцией, которая добавляет 7, является функцией, которая добавляет 12. Таким образом, композиция сумматоров удовлетворяет правилам, эквивалентным правилам сложения. Это тоже хорошо: мы можем заменить сложение композицией функций.

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

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

Проницательный читатель мог заметить, что отображение целых чисел в сумматоры следует из второго толкования сигнатуры типа mappend: m -> (m -> m). Тип говорит нам о том, что mappend отображает элемент множества моноида в функцию, действующую на этом множестве.

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

image


Конкатенация строк интересна тем, что у нас есть выбор правого или левого добавления. Модели зеркально обратны друг другу. Можно легко убедиться, что добавлению справа «bar» к «foo» соответствует добавление слева «rab» к «oof».

Вы можете задать вопрос: каждый ли категориальный моноид — категория одного объекта — определяет уникальное множество с бинарным оператором. Оказывается, мы всегда можем извлечь множество из категории одного объекта. Это будет множество морфизмов — сумматоров в нашем примере. Другими словами, мы имеем hom-множество М(m, m) одного объекта m в категории М. Мы можем легко определить бинарный оператор в этом множестве: моноидальное произведение двух элементов этого множества — это элемент, соответствующий композиции соответствующих им морфизмов. Если вы дадите мне два элемента М(m, m), соответствующие морфизмам f и g, их произведение будет соответствовать композиции g∘f. Композиция всегда существует потому, что источник и результат этих морфизмов — один и тот же объект. И она ассоциативна по правилам категории. Тождественный морфизм является нейтральным элементом этого произведения. Таким образом, мы всегда можем восстановить моноид-множество из категориального моноида. Они, практически, одно и то же.

image


Существует только одна маленькая проблема для математиков: морфизмы не обязаны формировать множество. В мире категорий есть вещи, больше, чем множества. Категория, в которой морфизмы между любыми двумя объектами образуют множество, называется локально маленькой. Как и было обещано, я буду игнорировать такие тонкости, но я решил, что нужно этот факт упомянуть.

Много интересных явлений в теории категорий происходит из за того, что элементы hom-множества можно рассматривать и как морфизмы, которые следуют правилам композиции, и как элементы множества. Здесь композиция морфизмов в М соответствует в моноидальному произведению в множестве М(m, m).

Теория категорий для программистов: предисловие
Категория: суть композиции
Типы и функции
Категории, большие и малые
Категории Клейсли
Перевод: Bartosz Milewski
Max Strakhov @Monnoroch
карма
73,5
рейтинг 0,0
Data Science/Machine Learning
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Спецпроект

Самое читаемое Разработка

Комментарии (29)

  • +1
    Заметьте, что аргументы функции не разделены запятыми и не окружены скобками. (Это, наверное, самое сложное, к чему нужно привыкнуть, во время изучения Haskell.)

    И это просто прекрасно. Код из-за этого читается легко и приятно.
    • +1
      АмнекажетсянаоборотэтоубиваетчитаемостькодаЭтокакеслибыпредложениявсегдабылизаписанысплошнякомбезпробеловипрочихзнаковпрепинанияРазделителидлятогоипридумаличтобыглазуивконечномсчетемозгубылолегчевыделятьинформациюизпотокаУверенвамстоилогораздоольшихтрудовчтобыпрочитатьэтопредложениечемеслибыонобылозаписанотак
      Не открывать без прочтения вышеизложенного!
      Я предупреждал
      А мне кажется, наоборот, это убивает читаемость кода. Это как если бы предложения всегда были записаны сплошняком, без пробелов и прочих знаков препинания. Разделители для того и придумали, чтобы глазу (и в конечном счете, мозгу) было легче выделять информацию из потока. Уверен вам стоило гораздо больших трудов, чтобы прочитать это предложение, чем если бы оно было записано так: (кстати, в сплошном тексте грамматическая ошибка. Найдите ее за 10 секунд)

      • +1
        ((Ну) (мы же) (про) (скобки и запятые)), ((а не про) пробелы).
        К *тому (гр, амм, ати, че, скую) [ошибку] [легко] #найдет $$компилятор.
        • 0
          Чем они принципиально отличаются? Или вы думаете, что читать книгу (текст на 10000 знаков, для определенности) без знаков препинания будет комфортно?
          К *тому (гр, амм, ати, че, скую) [ошибку] [легко] #найдет $$компилятор.

          Что делать, если компилятора нет, а ошибку исправить надо?
          • –1
            Хаскел принципиально отличается тем, что я могу написать bind(), а могу >>. Условностей в синтаксисе минимум. Ну и отступы, которые обязательны, хорошо помогают читать короткие строки по 2-3 слова. Можно записать все в одну строчку, но я в реальной жизни таких уникумов не встречал. Практически все пишут простой и понятный код. Ну если монадами не злоупотреблять.
            Сравните

            main = putStrLn «hello»

            и

            def main():
            print «Hello»

            Во втором случае «бесполезных» символом куда как больше. А читаемость ниже.
          • 0
            Никто не говорит, что в Хаскеле нет знаков препинания.
            Ими являются правильные отступы и… скобки.
            Пробелы приводят лишь к тому, что использовать в названиях подчёркнутый_стиль крайне не рекомендуется, так как легко спутать с пробелом.
      • +1
        Лично мне нравится аналогия с командной строкой, то есть когда синтаксис вызова функции соответствует принципу, по которому мы выполняем команды в cli. В таком представлении, скобки выполняют естественную роль границ выражения, а не служат в качестве специального символа-разделителя между именем функции и её аргументами. Сравните гипотетический cat, схожий с одноименной утилитой в Unix:

        cat file1.txt file2.txt
        

        cat "file1.txt" "file2.txt"
        

        cat("file1.txt", "file2.txt")
        


        Очевидно, что в последнем примере скобки не несут никакой смысловой нагрузки, а являются специальными парными символами-разделителями, которые упрощают жизнь разве что только лексеру языка, но не программисту.
  • 0
    Теории тут много, но хорошо сказано про то, что такое моноиды!
  • 0
    А что такое вещи, большие чем множества?
    • 0
      Например, не может быть множества всех множеств и подобных, от этого возникают парадоксы. В то же время, категория всех категорий никаких парадоксов не создает, зато в нее явно входят все множества, плюс такие категории, объекты которых тоже не формируют множества. Так что, она «очевидно» больше, чем любое множество. В каком-то смысле.
      • 0
        Да, парадокс множества всех множеств порождается неформальностью определения множества.
        Если дать формальное определение, то понятие «множество всех множеств» просто нельзя будет описать, т.е. будет противоречить определению множества. IMHO.
    • 0
      В мире множеств есть лишь 3 мощности — конечное, счетное бесконечное и континуум. Сравнивать мощности множеств и категорий, на мой взгляд, не вполне корректно
      • 0
        Вы категорически не правы, мощностей, конечно, бесконечность, никто не знает даже, счетная ли.
        • 0
          Можете привести пример другой мощности, кроме упомянутых?
          • 0
            Да, множество функций f: R -> R имеет мощность больше континуума (есть доказательство).
            В общем случае, множество функций g: A -> A имеет строго большую мощность, чем множество A.
            • 0
              Спасибо, был пробел в знаниях!
  • 0
    Извините, я никак не могу понять про моноид. Если можете, объясните на конкретном примере, что именно является объектом, что — стрелкой.

    Вот у нас есть категория одного объекта. Я правильно понимаю, что объект — это сам моноид, а стрелка — это все его отображения в себя?
    Если все так, то какие есть отображения моноида в себя, кроме тривиального?
    • 0
      Во-первых, не отображение моноида в себя. Теоретико-множественный моноид состоит из множества, фиксированного элемента этого множества и операции m: X -> X -> X. Так что, в себя отображается не моноид, а множество моноида.
      Во-вторых, очень просто, если ваш моноид — целые числа, то для любого числа n функция
      f x = x + n 
      

      будет отображением множества моноида в себя (тут m = +).
      Теоретико-категориальный моноид никуда не отображается, а имеет множество морфизмов, которое изоморфно множеству вышеупомянутых функций, которое, в свою очередь, изоморфно множеству теоретико-множественного моноида.
      • 0
        И нас, получается, не беспокоит, что отображение не «на», а «в», и что в частности может после такого отображения легко может пропасть ноль? Мы не пытаемся из нового множества снова сделать моноид?

        «Теоретико-категорный морфизм имеет множество морфизмов». Морфизмов чего и во что? Я правильно это себе представляю, что объект — это множество моноида, а стрелка — это все его морфизмы. И объект плюс стрелка являются теоретико-категорным моноидом?
        • 0
          Да не отображаем мы ничего никуда в ТК. Мы просто умеем компоновать морфизмы в новые морфизмы. А стрелка — это просто другое название морфизма. И не морфизм имеет морфизмы, а моноид. Вы невнимательно прочитали. А морфизмы из себя в себя. Автор же так и написал.
          • 0
            Ок. Т.е. нас вообще не волнует, что из себя представляет объект, что из себя представляют стрелочки, лишь бы компоновались?
            • 0
              Возможно, вам стоит почитать весь цикл с начала. Вот этот ваш комментарий — это, по сути, неформальное определение категории, которое было еще в первой статье, а вы так написали, как-будто удивились.
              • 0
                Я читал ваш цикл с начала и даже несколько часов медитировал над википедией. Но видимо я еще не вполне смирился с тем, что объект и морфизм не обязаны нести какой-либо смысл. Особенно учитывая, что бывают «нормальные» категории типа категорий множеств, где известна природа объектов.
            • 0
              Тео́рия катего́рий — раздел математики, изучающий свойства отношений между математическими объектами, не зависящие от внутренней структуры объектов.
              • 0
                Что совершенно не мешает теоркатегорщикам постоянно говорить о категориях таких-то объектов и сяких-то объектов.
                • 0
                  Да, в качестве примеров и аналогий для лучшей интуиции формализмов.
  • 0
    В конце статьи я немного поплыл в абстракциях. :-)
    Надо будет еще раз внимательнее расставить точки над i.
    P.S. Было бы неплохо в начале статьи (или отдельной статьей) предоставлять глоссарий терминов, которые вы же сами определяли. Мне в свое время очень помогало в освоении универовской программы. :-)
  • 0
    Самое главное, что удалось почерпнуть — это понимание того, каким образом математики занимаются рукоблудием ;)
    А если серьезно, то то, что Haskell — это не средство приобщить программистов к математике, а приобщить математиков к программированию.
    • 0
      Haskell — это инструмент отладки мышления. (я не помню кто автор этого утверждения)

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.