Pull to refresh

Монады с точки зрения теории категорий

Programming *
Translation

Введение

Кажется, монады в программировании стали загадкой века. И для этого есть две причины:
  • недостаточное знание теории категорий;
  • многие авторы стараюстся не упоминать категории вообще.
Это как говорить об электричестве не используя мат. анализ. Достаточно для замены предохранителя, не хватит, чтобы спроектировать усилитель.

Мы начнём с простого введения в категории и функторы, затем дадим определение монады, приведём простые примеры монад в категориях и в конце приведём монадическую терминологию используемую в языках программирования.

Я уверен, что монады с точки зрения категорий почти элементарны.

Содержание

  1. Категория
  2. Функтор
  3. Естественное преобразование
  4. Монада
  5. Монады исключения и состояния
  6. Монады в программировании
  7. Ссылки
Читать дальше →
Total votes 126: ↑105 and ↓21 +84
Views 32K
Comments 150

Категория Hask

Haskell *

Вступление


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

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

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

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



Примеры


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

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

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

Можно считать города «объектами», а перемещения между городами – «морфизмами». Например, можно представить себе карту авиарейсов (как-то не нашёл я удачную картинку) или карту железных дорог – они будут похожи на картинки выше, только сложнее. Следует обратить внимание на два момента, которые кажутся в реальности само собой разумеющимися, но для дальнейшего имеют важное значение:
  • Бывает, что из одного города в другой никак не попасть поездом или самолётом – между этими городами нет морфизмов.
  • Если мы перемещаемся в пределах одного и того же города, то это тоже морфизм – мы как бы путешествуем из города в него же.
  • Если из Санкт-Петербурга есть поезд до Москвы, а из Москвы есть авиарейс в Амстердам, то мы можем купить билет на поезд и билет на самолёт, “скомбинировать” их и таким образом попасть из Санкт-Петербурга в Амстердам – то есть можно на нашей карте нарисовать стрелку от Санкт-Петербурга до Амстердама изображающую этот скомбинированный морфизм.
Надеюсь, с этим примером всё понятно. А теперь немного формализма для чёткости.
Читать дальше →
Total votes 52: ↑49 and ↓3 +46
Views 15K
Comments 101

Эндофункторы категории Hask и их моноидальная структура

Haskell *

Введение


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

Обозначения


В прошлый раз я хотел обозначить морфизм/функцию буквой f, но она была занята для обозначения функтора/переменной типа f – никакой проблемы с точки зрения языка Haskell в этом нет, но при невнимательном прочтении это может вызвать путаницу, и я использовал для морфизма букву g. Пустяк, но всё же, я считаю, что полезно визуально разделять сущности, имеющие разную природу. Обычные типы я буду называть их обычными именами, а вот переменные типов я буду называть маленькими греческими буквами, причём простые () – буквами из начала алфавита, а параметрические (∗ → ∗) – буквами из конца алфавита (θ не из конца, но она смотрится лучше, чем χ, которая слишком похожа на X). Итак, в терминологии категории Hask:
  • Объекты: α, β, γ, δ ∷ ∗
  • Функторы: θ, φ, ψ, ω ∷ ∗ → ∗
  • Морфизмы: f, g, h ∷ α → β
Ввиду того, что GHC довольно давно поддерживает unicode, эти обозначения ничего не меняют в отношении синтаксиса и носят чисто косметический характер.

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

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


Давайте рассмотрим категорию, в которой будет только один объект – сама категория Hask. Что же будет морфизмами в такой категории? Это должны быть какие-то отображения HaskHask, и мы уже знаем такой тип отображений – это эндофункторы категории Hask, то есть типы сорта ∗ → ∗, воплощения класса Functor. Теперь нужно продумать как устроены единичный морфизм и композиция в этой категории, так чтобы они удовлетворяли аксиомам.
Читать дальше →
Total votes 29: ↑28 and ↓1 +27
Views 8.1K
Comments 44

Теория категорий для программистов: предисловие

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

Я постараюсь в нескольких параграфах убедить вас, что эта книга написана для вас, и развеять все ваши сомнения в необходимости изучения этой, одной из самых абстрактных областей математики, в свое драгоценное свободное время.
Читать дальше →
Total votes 55: ↑51 and ↓4 +47
Views 105K
Comments 25

Категория: суть композиции

Programming *C++ *Haskell *Functional Programming *
Translation
Это вторая статья в цикле «Теория категорий для программистов».

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

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

image
Читать дальше →
Total votes 37: ↑36 and ↓1 +35
Views 59K
Comments 128

Типы и функции

Programming *C++ *Haskell *Mathematics *Functional Programming *
Translation
Это третья статья в цикле «Теория категорий для программистов».

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

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


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

image


Читать дальше →
Total votes 42: ↑39 and ↓3 +36
Views 54K
Comments 102

Категории, большие и малые

Programming *C++ *Haskell *Mathematics *Functional Programming *
Translation
Это четвертая статья в цикле «Теория категорий для программистов».

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

Без объектов


Самая простая категория — без объектов и, как следствие, без морфизмов.
Читать дальше
Total votes 36: ↑33 and ↓3 +30
Views 34K
Comments 29

Категории Клейсли

Programming *C++ *Haskell *Mathematics *Functional Programming *
Translation

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


Вы видели, как сделать категорию типов и чистых функций. Я также упомянул, что есть способ смоделировать побочные эффекты, или нечистые функции, в рамках теории категорий. Давайте рассмотрим пример: функции, которые логируют или записывают ход своего выполнения.
Читать дальше →
Total votes 15: ↑14 and ↓1 +13
Views 25K
Comments 20

Произведения и копроизведения

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

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

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


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

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

Этот процесс можно сравнить с поиском в сети. Запрос пользователя — это наш шаблон. Если запрос не очень специфичен, то в ответ поисковая система выдаст множество подходящих документов, только часть из которых релевантны. Чтобы исключить нерелевантные ответы, пользователь уточняет запрос, что увеличивает точность поиска. В конце концов поисковая система проранжирует совпадения и, если повезет, искомый результат будет в самом начале списка.
Читать дальше →
Total votes 19: ↑17 and ↓2 +15
Views 18K
Comments 18

Простые алгебраические типы данных

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

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

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

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


Каноническая реализация произведения типов в языках программирования — это пара. В Haskell пара является примитивным конструктором типов, а в C++ это относительно сложный шаблон из стандартной библиотеки.
Pair
Строго говоря, произведение типов не коммутативно: нельзя подставить пару типа (Int, Bool) вместо (Bool, Int), хотя они и содержат одни и те же данные. Однако произведение коммутативно с точностью до изоморфизма, задаваемого функцией swap, которая обратна самой себе:
swap :: (a, b) -> (b, a)
swap (x, y) = (y, x)

Можно рассматривать такие пары как различные форматы хранения одной и той же информации, как big endian и little endian.
Читать дальше →
Total votes 29: ↑28 and ↓1 +27
Views 33K
Comments 7

Функторы (глава книги «Теория категорий для программистов»)

C++ *Haskell *Mathematics *Functional Programming *
Tutorial
Translation

Это седьмая статья из цикла «Теория категорий для программистов». Предыдущие статьи уже публиковались на Хабре:



Функторы


За понятием функтора стоит очень простая, но мощная идея (как бы заезжено это ни прозвучало). Просто теория категорий полна простых и мощных идей. Функтор есть отображение между категориями. Пусть даны две категории C и D, а функтор F отображает объекты из C в объекты из D — это функция над объектами. Если a — это объект из C, то будем обозначать его образ из D как F a (без скобок). Но ведь категория — это не только объекты, но еще и соединяющие их морфизмы. Функтор также отображает и морфизмы — это функция над морфизмами. Но морфизмы отображаются не как попало, а так, чтобы сохранять связи. А именно, если морфизм f из C связывает объект a с объектом b,


f :: a -> b

то образ f в D, F f, связывает образ a с образом b:


F f :: F a -> F b

(Надеемся, что такая смесь математических обозначений и синтаксиса Haskell понятна читателю. Мы не будем писать скобки, применяя функторы к объектам или морфизмам.)


Читать дальше →
Total votes 33: ↑33 and ↓0 +33
Views 30K
Comments 2

Теория категорий на JavaScript. Часть 1. Категория множеств

ООО «ЦИТ» corporate blog JavaScript *ООP *Mathematics *Functional Programming *
Tutorial


Абстракция – это одна из основных техник в ИТ. Любой язык программирования или моделирования, любая парадигма программирования (процедурная, функциональная, ООП, …) дают ответ на вопрос, как и от чего нужно абстрагироваться. Причём, адепты каждого подхода предлагают какой-то свой вариант абстракции.

Если вы хотите увидеть истинную, универсальную абстракцию, то вступайте в нашу… изучайте теорию категорий. В статье на примере категории множеств с картинками и JavaScript-кодом объясняются самые базовые понятия теории категорий: пределы, универсальное свойство. Рассматривается вычислительный аспект теории категорий.

Также немного говорится про классы, примеси и смеси в JavaScript.

Примеры из статьи можно посмотреть тут.
Читать дальше →
Total votes 48: ↑48 and ↓0 +48
Views 33K
Comments 47

Типизируя техническое интервью

Algorithms *Haskell *Functional Programming *

Предлагаю читателям "Хабрахабра" перевод статьи Kyle Kingsbury, a.k.a "Aphyr".
Ранее: Заклиная техническое интервью


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

Читать дальше →
Total votes 27: ↑20 and ↓7 +13
Views 8.9K
Comments 7

Краткий справочник информатики

Programming *Perfect code *Designing and refactoring *Haskell *ООP *

Область ИТ растёт, и легко заблудиться в зоопарке подходов, фреймворков и технологий, которые громко заявляют о своей "новизне" и "эффективности". Но за обёрткой обычно скрываются старые добрые идеи, заново "изобретённые" в другом контексте. В итоге распространяется не самая простая и эффективная, а самая разрекламированная реализация. Разработчики не успевают вдумчиво произвести выбор из-за постоянного недостатка времени, а менеджеры выбирают самое распространённое, чтобы снизить риски при поиске разработчиков.


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

Читать дальше →
Total votes 19: ↑8 and ↓11 -3
Views 5.2K
Comments 64

Тайны сознания и математика

Mathematics *
В Древнем Египте математики не пользовались доказательствами. Все их утверждения были лишь эмпирически обоснованы. Но тем не менее, пирамиды стояли, а самолеты летали. И, наверное, никто бы и не требовал строгих доказательств, если бы не желание что-то опровергнуть. Вместе с греками математика обрела новую жизнь, в которой появились такие задачи, как квадратура круга, иррациональность корня из двух и задача о трисекции угла. С этого момента потребовались аксиомы, законы логики и теоремы. Современную же математику интересует еще и то, что возможно доказать, а что — нет. Продвижением стали теоремы Геделя о неполноте, формализация логики и Теория доказательств. Я предлагаю теорию и одну аксиому, которая поможет ответить на часть оставшихся вопросов и обозначить границы нашего сознания. В частности, это вопросы полноты, проблема равенства и аксиоматизация нашего воображения.

Читать дальше →
Total votes 36: ↑27 and ↓9 +18
Views 11K
Comments 17

Монады с точки зрения программистов (и немного теории категорий)

Programming *Haskell *Mathematics *Functional Programming *

Введение


Как узнать, что человек понял, что такое монады? Он сам вам об этом расскажет в первые 5 минут общения и обязательно попробует объяснить. А ещё напишет об этом текст и по возможности где-нибудь его опубликует, чтобы все остальные тоже поняли, что такое монады.


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


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


Моё изложение во многом основывается на книге Бартоша Милевски "Теория категорий для программистов", которая создавалась как серия блогпостов, доступна в PDF, а недавно вышла в бумаге.


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


Читать дальше →
Total votes 56: ↑52 and ↓4 +48
Views 39K
Comments 267

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

Издательский дом «Питер» corporate blog Programming *Designing and refactoring *Scala *Mathematics *
Translation
Здравствуйте, коллеги.



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



Тем более приятно, что нам удалось обнаружить сравнительно свежий материал (январь 2020), служащий отличным и при этом максимально кратким введением в теорию категорий. Надеемся, что нам удастся заинтересовать вас этой темой
Читать дальше →
Total votes 24: ↑22 and ↓2 +20
Views 33K
Comments 131

Category theory: начало

Mathematics *
Sandbox
Translation

Всем привет.

В качестве вступления немного о себе.

Меня зовут П., мне 37 и я начал учиться программированию в 33-34 года (старт был размыт в 2016-2017 годах). Я начал с изучения C# для последующего трудоустройства в качестве разработчика игр. Скорее всего на мое решение повлияла жена с её пониманием достижения скорейшей прибыли (ошибка 1: я, в очередной раз в своей жизни, погнался за материальными ценностями в ущерб внутреннему Миру). Учиться я начал на одном крупном онлайн ресурсе, который не заслужил упоминания о себе (ошибка 2: я верил, что за деньги можно получить качественное образование, потому что за него заплачены самое ценное в этом мире - ДЕНЬГИ). Обучение затянулось (по моей вине) и вместо 3-х месяцев продлилось около года. В этот период я занимался ни шатко ни валко. В процессе этого обучения я понял, что разработка игр не мое и я переключился на java (произошло это уже в 2018 году). В процессе самостоятельного изучения java я предпринимал попытки найти себе деятельность связанную с этим языком. Продолжалось мое бессистемное изучение java около 1.5 лет. Я ничего не создал и не нашел деятельность, где могу применить себя как разработчик. Тем не менее, в процессе поиска занятости наткнулся на вакансию команды разработчиков, которая предлагала программу обучения и трудоустройство после этого. Программа была доступна в двух вариантах: фронтенд (JS/TS, React.Js, Redux) и бэкенд (Haskell). Без особых оснований я выбрал бэкенд и Haskell (шел 2019 год). В ходе этой деятельности, я влюбился в Haskell. К сожалению, любовь не кормит, а у меня возрастные особенности и необходимость кормить достаточно большую семью (жена и больше двух детей). В связи с этим в 2020 году (перед мировыми потрясениями) я принял решение пойти на платный курс того же онлайн ресурса по изучению python и программой с уклоном в сторону ИИ (ошибка 3: взвешенное решение: "python высокорелевантный язык"; "по прошествии n лет, предположил, что ресурс изменил свой подход к образованию, так как документально гарантировал трудоустройство"; "по результату обучения выдается диплом о повышении квалификации"; "не хотелось, чтобы деньги обесценились, поэтому хотелось вложить их в себя" - может оказаться совсем невзвешенным, другими словами наивным). На текущий момент я продолжаю обучение на онлайн курсе. Я не подтвердил свое предположение об улучшевшейся модели обучения, но я получил некую программу, которой я могу следовать и которая не позволяет мне забросить обучение на длительный срок.

Статья не обо мне, честно. Жмите сюда...
Total votes 17: ↑9 and ↓8 +1
Views 2.7K
Comments 11

Категория контекста

Search engines *Semantics *Algorithms *Natural Language Processing *

Математической моделью знаковых последовательностей с повторами (текстов) является мультимножество. Мультимножество было определено Д. Кнутом в 1969 году и позже подробно изучено А.Б. Петровским [1]. Универсальное свойство мультимножества – существование одинаковых элементов. Предельным случаем мультимножества при единичных кратностях элементов является множество. Множество с единичными кратностями, соответствующее мультимножеству, называется его порождающим множеством или доменом. Множество с нулевой кратностью – это пустое множество.

Читать далее
Total votes 6: ↑5 and ↓1 +4
Views 1.7K
Comments 1

Конкордантность смысла

Search engines *Semantics *Algorithms *Natural Language Processing *

В [1, 2, 3] тексты (знаковые последовательности с повторами) с помощью матричных единиц, как образов слов, превращались (координатизировались) в алгебраические системы. Координатизация — необходимое условие алгебраизации любой предметной области...

Читать далее
Total votes 9: ↑7 and ↓2 +5
Views 1.8K
Comments 5
1