7 августа 2011 в 01:07

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

Введение

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

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

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

Содержание

  1. Категория
  2. Функтор
  3. Естественное преобразование
  4. Монада
  5. Монады исключения и состояния
  6. Монады в программировании
  7. Ссылки

Категория

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

Неважно, чем является объект или стрелка, важно только выполнение следующих свойств:

Стрелка рисуется между объектами (при этом объект может быть одним тем же); это обозначается следующим образом: f: a → b, где f это стрелка, а a и b — объекты.
  1. Для стрелок f: a → b и g: b → c существует такая стрелка h: a → c называемая композицией: h = g ° f.
  2. Для каждого объекта a существует единичная стрелка, ida: a → a, такая, что для любого f: a → b следующее верно:
    f ° ida = f и для любого g: c → a мы имеем ida ° g = g.
  3. Композиция ассоциативна: f ° (g ° h) = (f ° g) ° h.
Замечание. В виду чрезвычайно абстрактной природы этой записи, мы не можем ожидать, что «все объекты» или «все стрелки из a к b» образуют множество. Категории, где они являются множествами называются «малые» или «локально малые».

Примеры категорий

Примеры «классических» категорий:
  1. Set — категория всех множеств. Её объекты это все множества, а морфизмы — функции над множествами.
  2. Setf — категория всех конечных множеств и функций между ними.
  3. Rel — категория, где объекты это все множества, а бинарные отношения играют роль морфизмов. Композиция объедена через внутеннее объединение.
  4. Part — категория всех множеств и частичных функций как морфизмов. Частичная функция из X к Y это функция из подмножества Xo ⊂ X к Y:
  5. Top — категория всех топологических пространств и непрерывных функций между ними.
Существуют также категории, являющиеся не просто общими теориями:
  1. Любая группа может быть рассмотрена как категория: группа элементов это морфизмы над единственным объектом.
    Тождественная функция это нейтральный элемент группы. А композицией является умножение.
  2. Частично упорядоченное множество может быть представленно как категория. Элементы множества это объекты. Добавим одну стрелку a → b для каждой пары a, b так, что a < b и единичную стрелку a → a для каждого a.
    Для каждой пары объектов существует не более, чем одна стрелка и, так как частичный порядок транзитивен, мы имеем композицию (a < b, b < c => a < c), то есть можно не переживать о его ассоциативности.
  3. Как особый случай прошлого примера — множество целых чисел [N… M] можно считать категорией.
  4. Любой ориентированный граф может быть преобразован в категорию, если считать его пути стрелками. Пустой путь является единичным морфизмом, а конкатенация путей будет композицией.
  5. Натуральные числа как объекты, матрицы как стрелки. Любая матрица NxM будет стрелкой N → M. Перемножение матриц будет играть роль композиции, а единичная матрица NxN будет единичной стрелкой N → N.

Дополнительный материал

Просто определить изоморфизм в категории — им является тот, что имеет инверсию. То есть, в том случае, если мы имеем f: a → b и g: b → a, и выполняется f ° g = idb и g ° f = id a. Это определение потребуется нам позже. Также возможно определить мономорфизм и эпиморфизм, это несколько сложнее и выходит за рамки данной статьи.

Помните объекты [0… N] из прошлой главы? Существуют особые категории: 1 = [0] и 2 = [0… 1]. Первая является одним объектом с единственным морфизмом, вторая — двумя объектами и тремя морфизмами.

Образуют ли сами категории категорию? Да, но тогда нам следует дать определение стрелок между ними. Они являются стрелками второго порядка и называются функторами.

Функтор

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

Какую непротиворечивость мы ожидаем? Пусть X и Y будут двумя категориями; определим функтор F: X → Y. Теперь нам нужно отобразить объекты из X в Y, имея для каждого a в X объект F(a) в Y и для каждой стрелки f в X мы должны иметь стрелку F(f) в Y.

Для непротиворечивости должны выполняться следующие правила:
  • для f: a → b имеем F(f): F(a) → F(b) — сохраняются домен и кодомен;
  • для ida: a → a имеем F(ida) = idF(a): F(a) → F(a) — сохраняется единица;
  • для f: a → b и g: b → c F(g ° f) = F(g) ° F(f) — сохраняется композиция.
Очевидным образом определена композиция функторов: в начале применяется первый функтор, затем остальные.

Примеры функторов

  1. Тождественный функтор для категории X. Хотя тождественность X → X сохраняет объекты и стрелки неизмененными это всё еще функтор.
  2. Setf ↪ Set — функтор, который включает Setf в Set, отображая конечные множества в самих себя, то же самое с функциями. Обратите внимание, что это не тождественный функтор.
  3. Set → Top аналогично предыдущему примеру, этот функтор делает Set частью Top. Каждое множество отображается в дискретное топологическое пространство.
  4. Для любого множества A мы можем определить следующий функтор:
    (- xA): SetSet — он отобразит любое множество X в декартово произведение X × A.
  5. Для любого множества A можно определить функтор PA: SetSet, который отобразит любое множество X в XA — множество функций из A в X.
  6. Set ↪ Part вводит множеста в множества с частичными функциями — отображает множества и функции в них самих.
  7. Обратным к п.6 является функтор +Null: PartSet — этот функтор добавляет «расширение» Null к каждому множеству X ↦ (X + Null) так, что частичная функция X → Y отображается в функцию (X + Null) → (Y + Null).
Упражнение. Определите такое же расширение для частичных функций.

Посмотрим на малые категории и их функторы.
  1. Если мы примем группы за категории, то чем же будут их функторы? Функтор должен сохранять единичный морфизм и композицию. Следовательно, функтор это гомоморфизм группы.
  2. Любая функция сохраняющая порядок (т.н. монотонная) между двумя частично упорядоченным множествами является функтором.
  3. Возьмем пару ориентированных графов и отображение, которое сохраняет ребра. Мы можем расширить это отображение до функции, что отображает путь из одного графа в пути на другом графе. Эта функция, по определению, сохраняет связи и пустые пути, таким образом это функтор из одной созданной по графу категории в другую.
  4. Помните категорию 1? И так, как будет выглядеть функтор из 1 в категорию C? 1 имеет всего лишь один объект и тождественный морфизм. Таким образом определение этого функтора равносильно выбору объекта из C и наоборот — для любого объекта X в категории C мы можем определить функтор PointX: 1C.

Естественное преобразование

Должно быть, это самая сложная часть. Предположим, что мы имеем два функтора F, G: XY. Естественное преобразование η: F → G определено, когда для каждого объекта x ∈ X существует стрелка η(x): F(x) → G(x) в Y и мы имеем следующее свойство:
  • для всех f: a → b верно равенство: G(f) ° η(a) = η(b) ° F(f).

По этому оно называется «естественным» — оно действует непротиворечиво с действиями функторов на стрелки.

Примеры естественных преобразований

  1. Помните функтор точки? И так, если в категории C мы имеем стрелку f: a → b, эта стрелка определяет естественное преобразование из Pointa в Pointb. Это отношение один-к-одному между преобразованием функтора точки и стрелками категории.
  2. Возьмем два множества A и B и функцию f: A → B. Эта функция определяет естественное преобразование между функторами (- xA),(- xB): SetSet. (- xf): (- xA) → (- xB) по следующей формуле: (x, a) ↦ (x, f(a)).

    Можно записать это определение в следующем виде:
    (define (cartesian f)
        (lambda (x a) (list x (f a))))
    
    Так как для каждого множества A существует функция A → (.), где (.) синглетон, мы имеем естественное преобразование (- xA) → 1, что является для каждого объекта X проекцией: X ⨯ A → X.
Для каждого A в Set существует естественное преобразование 1 → PA. Возьмём любое X в Set; нам требуется функция из X в XA. Естественным выбором будет та, что отображает каждый элемент x из X в константную функцию из A в X, которая возвращает x.

Опять же, это определение можно записать следующим образом:
(define (return x) (lambda (a) (x)))

Монада

Монада в категории C это эндофунктор T: CC с двумя естественными преобразованиями: η: 1 → T и μ: T ° T → T.Обозначим за T(η): T → T ° T преобразование, результатом которого является применение T к η и T(μ): (T ° T) ° T → T ° T.
Пользуясь этими определениями запишем две аксиомы монад:
  1. T(η) ° μ это тождество T → T
  2. T(μ) ° μ равносильно μ ° μ:

Примеры монад

  1. Для любой категории C может быть определена тождественная монада, состоящая из тождественного функтора и тождественного морфизма.
  2. Предположим, что у нас есть группа G. Определим монаду MG в Set. Функтор монады будет следующим:
    X ↦ X × G.
    u(X): X → X × G отображает элемент x в пару (x, e), где e это единица группы.
    MG(MG(X)) = (idX, mG), где mG это умножение групп.
  3. Списки в Set. Результатом применения функтора, назовем его List, для множества X является множество всех списков (x1, x2, x3...) элементов из X, включая пустое. Этот функтор станет популярной монадой, если мы добавим u и m. Пусть uX: X → List(X) создает список из единственного элемента для каждого x ∊ X и mX: List(List(X)) → List(X) отображает список списков в плоский список.

Операция замыкания. Не уверен, много ли она имеет общего с той же операцией из «computer science».

Помните, что мы можем считать частично-упорядоченные множества и их функции, сохраняющие порядок, как категории и функторы?

Монотонная (сохраняющая порядок) функция C: X → X называется замыканием, если ∀ x ∊ X x <= C(x) и C(C(x)) = C(x).

Эти два условия являются ни чем иным, как аксиомами монад, применёнными к частично-упорядоченным множествам, считая, что монады в частично-упорядоченных множествах и есть замыкания. Также можно попытаться применить это к частично-упорядоченным множествам путей графа.

Монады исключения и состояния


Монада исключения

Мы в категории Part. Возьмём множество A и определим следующий функтор:
PlusNull: X ↦ (X+Null)

Мы уже рассматривали этот функтор, в прошлый раз он был из Part в Set. На этот раз мы создадим его с включением Set в Part, то есть получим эндофунктор.

Почему он является монадой? Нам потребуется ещё uX: X → (X+Null) и mX: ((X+Null)+Null) → (X+Null).

В первом случае это простое включение, а во втором мы отображаем оба Null синглтона в Null. На Lisp это выглядит следующим образом:
(define (ux x) x)

(define (mx x) x)
Как вы видите, это монада (а если нет, то, в качестве упражнения, докажите это).

Монада состояния

Мы в категории Set. Возьмём множество A и определим следующий функтор:

X ↦ (X × A)A

Об A можно думать, как о множестве состояний некоторого автомата, тогда (X × A)A включает в себя все состояния автомата на X с выводом в X, то есть всех функций A → (A × X), первый компонент является преобразованием, а второй выводом в X.

Почему это монада? uX: X → (A × X)A отображает любой элемент x ∊ X в функцию, являющуюся тождественной на A и константой x на X.

Опишем это на Lisp:
(define (ux x)
    (lambda (a) (list a x)))

А что на счёт mX: (A × (A × X)A)A → (A × X)A?

Имея коллекцию автоматов mX: (A × (A × X)A)A, которая имеет A как множество состояний, которое выводится в другую коллекцию автоматов (эти тоже имеют A как множество состояний, но X как множество выводов). Каким образом, для такого составного автомата, можно найти соответствие в множестве A?

Опишем это на Lisp:
(define (mx f)
    (let (tr1 out1)
        ((car f) (cadr f))) ;два компонента f: A → (A × (A × X))^A
    (lambda (a)
        (let a1 (tr1 a))    ;состояния после первого преобразования
        (let f2 (out1 a))   ;отображение состояния в другой автомат
        (let (tr2 out2) ((car f2) (cadr f2))) ;составные части второго автомата
            (list (tr2 a1) (out2 a1))))
Здесь происходит следующее: у нас есть функция из A в A × (A × X)A, которая состоит из преобразования A → A и вывода A → (A × X)A, то есть для каждого a мы имеем другое состояние a1 и вывод в виде функции, результирующая функция из A в A × X должна просто применить эту выходную функцию к новому состоянию.
Скучное упражнение. Докажите, что это действительно монада.

Монады в программировании

С точки зрения категорий, функциональное программирование состоит из представления программ как морфизмов в категории f: X → Y, где X это «ввод», а Y это «вывод».
Преимущество такой модели состоит в том, что мы можем погрузить все наши высказывания относительно программ в очень стабильную теорию категорий; возможно менять сущность объектов и категорий, изменять логику лежащего в основе топоса и быть на 100% уверенными в том, о чем мы говорим. Например, вместо «нечёткой логики» можно использовать интуиционистскую логику или семнтику Крипке.

Кажется, что некоторые техники программирования не подходят для такой модели, например исключения или побочные эффекты.

Одно из решений проблемы исключений это введение NullObject или числового значения NaN.
Например, если наша функция не определена на всей области X, мы можем расширить её используя значения из (Y+Null), также как и в монаде исключения.

А для функций имеющих состояние подойдёт, соответственно, монада состояния.

Монада IO в Haskell

В Haskell ввели монаду IO, чтобы избежать сложности с описанием того, каким образом функции могут иметь побочные эффекты.

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

В этой модели каждое состояние автомата становится функцией. Далее A представляется как декартово произведение двух множеств String, где первый компонент это «ввод», а второй «вывод».
Для этого введение специальные функции преобразования, первая, getc, забирает символ из ввода, а другая, putc, добавляет символ к выводу.

Интересно, чего же конкретно они пытались этим добиться.

Ссылки и примечания

  1. Википедия как основной источник ссылок.
  2. Эта статья как сложное, скучное, но исчерпывающее объяснения монадической терминологии используемой в программировании.
  3. “Comprehending Monads” от Frederik Eaton — трехстраничный словарик терминов и обозначений.
  4. В Haskell u называют return, а m называют комбинатором или join
  5. Многие книги по Haskell упоминают List как пример монады имея в то же время особую реализацию монады состояния.
  6. Еще один пример монады это map/reduce от Google.
+84
8697
191
sylvio 16,7

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

+30
eyeofhell, #
Странная сейчас математика пошла :(. Раньше как было — на основе примитивных терминов и аксиом выводим более сложные термины и так далее. Сейчас — «функтор это ...». А затем сразу «монада — это эндофунктор, который ...». При этом чем «функтор» отличается от «эндофунктора» никого не интересует, и так сойдет. Главное, чтобы стрелочек побольше :(.
0
sylvio, #
Это презентация — набросок пути, по которому вам придется пройти самому. Все понятия легко находятся в википедии или соответствующих учебниках, если хотите, могу расставить ссылки.

Никто не говорил, что будет просто :)
+1
kibitzer, #
Хорошо написанная статья, не обращайте внимание. Людям с высшим техническим образованием понять ее вообще не составит труда (даже если не было курса по теории категорий). И отдельное спасибо, за ОЧЕНЬ качественное оформление.
+4
megalol, #
Эндофунктор не меняет категорию
+1
qrazydraqon, #
Что сложного в определении функтора? Очень естественное понятие.

>При этом чем «функтор» отличается от «эндофунктора» никого не интересует, и так сойдет.
«Эндо» — на себя. Там так и написано: эндофунктор T: C → C.

И лучше стрелочки, чем адские нагромождения символов. В этом отношении алгебра гораздо легче для изучения, чем большинство аналитических дисциплин — именно благодаря свободному использованию диаграмм.
+7
jtootf, #
Раньше — это когда? Книга Маклейна вышла в 1971 году, изобретены функторы и естественные преобразования (Эйленбергом и Маклейном) были в 1942 году, представление функции стрелкой появилось в лекциях Гуревича в 1940 году; основы алгебры морфизмов были заложены Эмми Нётер ещё двадцатью годами ранее.
0
magmoro, #
абстрактное изложение в стиле Бурбаки
–2
Nashev, #
Меня убило раньше: f: a → b, где f это стрелка, а a и b — объекты. Если тут «стрелка» — это f, то что такое значок "→", нарисованный между a и b??? А двоеточие тут что обозначает? Если f — это намёк на функцию, то почему двоеточие, а не скобочки, и почему ни слова, объясняющего этот намёк??.. :(((

А вообще, основная беда таких разделов математики в том, что они используют неизвестные из обычной практики слова — монады, морфизмы, функторы… наблы там всякие… Эти все слова не имеют известного и привычного смысла в обычной жизни, и потому очень затрудняют понимание предмета. Особенно, когда значение каждого из них определяется через значение одного а то и нескольких других таких же «новых» слов. Сепулькарий какой-то навороченный получается…
+1
eyeofhell, #
Это я тоже заметил, но это вопрос стиля изложения. Излагать ясно и четко — это мало кто умеет, тут ИМХО не имеет смысл придираться. В целом понятно о чем речь. А вот объяснять обозначенное в топике через сущность которая до этого не упоминалась — это да, сильно :).

Особенно, когда значение каждого из них определяется через значение одного а то и нескольких других таких же «новых» слов. Сепулькарий какой-то навороченный получается…


Ну это во всех областях так… Но в том же программировании, прежде чем написать что «assignment expression is an expression that assigns a value to an object» введут термины «expression», «assign», «value» и «object». А тут этого как бы не видно. Что очень огорчает :(. Раньше трава была зеленее, деревья выше а заклятья — сильнее O_O.
+2
nikitad, #
Вы в универе учились? Отображения обозначаются точно также, но почему-то ни у кого вопросов к записи f: x → y не возникает.
0
Exabiche, #
Порекомендуйте какую-нибудь толковую книжку по хаскелу, что ли.
+6
Nekuromento, #
Learn You a Haskell for Great Good
Real World Haskell
+3
wlan, #
Лучше толковую книжку по теории категорий.
+5
jtootf, #
держи. это крайне щадящий учебник с бездной примеров
–1
afiskon, #
learnyouahaskell.com и книги Романа Душкина.
+1
rushter, #
Напомнило:
+4
rushter, #
+12
Skiminok, #
Все-таки лучшее введение в теорию категорий, которое я когда-либо видел, это «Розеттский камень».
+4
sylvio, #
Да, это очень крутая книга и невероятно объемная работа по её переводу, спасибо автору.
Я еще могу порекомендовать классику (кажется, пока не переведенную) — учебник Пирса.
+4
grep0, #
Автор как-то не убедил, что сам понимает теорию категорий. Конечно, можно переписать определения из книжки, но в таком виде — не мотивирует
+2
sylvio, #
У меня нет причин сомневаться в компетентности автора.

Если вы достаточно хорошо понимаете тему, то хотелось бы услышать комментарии непосредственно по статье.
+1
vpatryshev, #
Я не ставил себе целью убедить кого-либо в чём либо; а также не ставил целью мотивацию. Написал это для людей, которые сами себя мотивируют, но которым лень продираться через сотни страниц МакЛейна.
–1
egorinsk, #
По, моему какое-то запутанное и нелогичное объяснение.

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

А так, какая-то хрень получилась.
+3
sylvio, #
Монады реализованы не только в Хаскелле. Это объяснения конецпции монад, я не думаю, что может быть что-то более логичное, чем объяснения их на том языке, на котором они придуманы — языке математики.

Какой момент вас смутил и чему стоит уделить большее внимание?
+1
egorinsk, #
В статье употребляются термины, и не разъяснено, что вы под ними понимаете. Например, «морфизм», «Частично упорядоченное множество». Также, приводятся безлдоказательные двусмысленные утверждения, например:

> «Любая группа может быть рассмотрена как категория: группа элементов это морфизмы над единственным объектом.»

Почему группа элементов это морфизмы над единственным объектом? Это вы сами так придумали?

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

Ну и тем более, странно выглядит попытка привязать эти самые множества и категории к языку программирования, который никакими абстрактными множествами и категориями не манипулирует, а манипулирует банальными байтами, числами и последовательностью операций.
+4
jtootf, #
Морфизм — это стрелка от (ровно) одного объекта к (ровно одному) другому. Частично упорядоченное множество — это множество, часть элементов которого упорядочены (т.е. для некоторых пар элементов можно сказать, какой из элементов больше).

Что касается эквивалентности категориального и теоретико-множественного определения группы, то проверяется она тривиальной подстановкой и проверкой выполнения аксиом. И нет, это не автор так придумал, это видно из определений. И ещё раз нет, банальными байтами оперируют только языки низкого уровня; уже на уровне C появляются такие страшные и далёкие от железа вещи, как функции и типы.
0
voidlizard, #
Как это реализовано на нижнем уровне это — детали реализации, могут меняться от версии к версии компилятора, быть разным для разных монад и вообще ничего не объяснят в принципе.
0
megalol, #
Если понимать под реализацией раскрытие join и bind для разных монад, это объясняет многое. Очередной туториал я бы из одной такой строчки и составил: возьми карандаш и подставь.
+2
vpatryshev, #
Значит, этот текст не для Вас. В теории категорий нет куч и стеков.
+1
sectus, #
Много фраз(особенно определения) можно было сформулировать гораздо понятнее.
+44
qmax, #
Клёво. Теперь что такое монады стало ещё более непонятно.
+6
MarcusAurelius, #
Эйнштейн: «Если учёный в двух словах не может объяснить ребёнку, чем он занимается, то этот учёный — шарлатан».

Понижайте уровень изложения, а то ведь бритва Оккама по автору плачет.
+1
qrazydraqon, #
Во-первых, насколько мне известно, эта фраза принадлежит не Эйнштейну.

Во-вторых, она не относится к математике. :]
+2
MarcusAurelius, #
Вы могли прочитать это у Воннегута, но я говорю про первоисточник. А чем математика не такая?
0
shai_xylyd, #
Математика не такая, потому что изучает то, что не существует. Нельзя сказать, что математик занимается изучением X и это будет понятно, так как X существует только в сознании математика; чтобы объяснить — нужно дать определение X, а так как X может зависеть от Y, то очевидно, что в двух словах это не рассказать.
+1
rachiu, #
Есть два вида изложения:

1. От теории к практике (его предпочитают математики, но он непонятен инженерам)
2. От практики к теории и снова к практике, т. е. частное -> общее -> другие примеры частного. Именно так знания обычно и образуются.
+1
MarcusAurelius, #
Программирование — это одна из редких дисциплин, которые лежать на пересечении искусства и инженерии, другой пример — архитектура. Поэтому критериями в программировании я считаю два: полезность и эстетическую ценность.
0
MarcusAurelius, #
Предмет любой науки существует только в сознании исследователя. Это хорошо показывает философия Буддизма и философия Суфизма. Не у кого не может быть аргумента за то, что поступающие в наше сознание сигналы не плод нашего же воображения (см. критерий фальсифицируемости Поппера), т.к. нет возможности поставить эксперимент, который отличит поток сигналов от реальности от потока сигналов от иллюзии. А то, что поток выглядит непротеворечивым, правдоподобным и последовательным ни как не может являться признаком его реальности (реальность не следует из логичности).

Более того, Умберто Эко показывает нам в «Поисках совершенного языка» то, что понятие X принципиально не может быть точно передано из сознания человека A в сознание человека B, т.к. для его расшифровки его в сознании B требуется весь набор знаний A. Так что, мы все живем в своей собственной реальности, в своем заблуждении. Разница только в том, осознаем ли мы иллюзорность или упорствуем в строгой научности наших логических потуг.
0
shai_xylyd, #
Бла-бла-бла, сбежать в солипсизм очень просто, но абсолютно не продуктивно. Кстати, интересно, существует ли критерий фальсифицируемости в математике?

Я писал о том, что если физика, биология, экономика изучает то, что существует в сознании большинства людей или на основе этого знания построено то, что они используют, то объяснить это в двух словах намного проще, чем, например, теорию категорий, являющейся абстракцией над абстрактной алгебре, являющейся абстракцией над числами, которые нельзя потрогать)
0
MarcusAurelius, #
При чем тут солипсизм, я говорю про иллюзорность в первую очередь собственного сознания. А Поппер говорил про всю науку в целом, но как-то упустил, что реальность собственного сознания не фальсифицируема, а потому, любой ученый, чтобы начать цепочку аксиом, теорем и выводов, должен сначала принять на веру поток поступающей информации на вход в его сознание.
0
megalol, #
Иллюзорность в приличном обществе упоминать все равно, что предлагать человеку посмотреть на нос, а потом: «вот видишь, ты его не замечал все это время». Вот это новость.
Наука субъект никогда и не изучала, чтобы это делать.
+1
Nashev, #
Как это при чём тут солипсизм, если Вы о нём и говорите? Или Вы просто не знаете такого слова?
0
MarcusAurelius, #
Я не сторонник «печального солипсизма», а моя точка зрения — это «Вахдад альВудж» (теория единства бытия, изложенная Ибн Аль Араби). С невозможностью же доказать объективность бытия поспорить невозможно, согласитесь. Поэтому то математические понятия имеют такую же степень реальности, как и физический предмет (например, яблоко, которое мы кусаем) или Баба Яга. Нет другой возможности отличить научное от ненаучного, объективное от не объективного и реальное от вымысла, кроме одного пути — бездоказательной веры.
0
Qbit, #
> Предмет любой науки существует только в сознании исследователя.

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

> Это хорошо показывает философия Буддизма и философия Суфизма.

А философия действительно существует только в сознании человека, и передаётся от одного к другому воздушно-капельным путём. Посади двух философов отдельно — они никогда не родят в точности одинаковое, предсказуемое внешним наблюдателем знание.
–1
Habroche, #
Поддерживаю qrazydragon'а. В приведённом виде это, действительно, воннегутовская фраза, которую Эйнштейн, видимо, не высказывал. В англ. Викицитатнике есть подробное описание — Misattributed: You do not really understand…
+3
Habroche, #
Прошу прощения за оффтоп, для полноты картины более подробно.

Если перейти по приведённой ссылке, то можно убедиться, что различные варианты этого высказывания приписываются Эйнштейну ошибочно (вообще, это очень частое явление, и, к сожалению, не только по отношению к нему; надеюсь, изложенное здесь будет напоминанием об этом). Конкретно данный вариант, с «шарлатаном», как верно отметил цитирующий, — фраза из произведения Воннегута. Там же, по ссылке, указывается и куда более достоверная схожая по смыслу цитата, с предположением насчёт её первоисточника. Этот же вариант приведён и в наиболее полном, пожалуй, на сегодня сборнике эйнштейновских цитат Alice Calaprice, The Ultimate Quotable Einstein, Princeton University Press, 2011 (4-ое издание, стр. 380-381) с указанием того же первоисточника — воспоминаний Луи де Бройля, а точнее — его книги Nouvelles Perspectives en Microphysique и её переводного английского издания. Приведём его на всех трёх языках:
«…il me disait que toute théorie physique devrait pouvoir, en dehors de tout calcul, être illustrée par des images si simples “qu’un enfant même devrait pouvoir les comprendre”.»
— Louis de Broglie Louis, Nouvelles Perspectives en Microphysique, Paris: Editions Albin Michel, 1956, p. 236

«…he told me that all physical theories, their mathematical expressions apart, ought to lend themselves to so simple a description “that even a child could understand them”.»
— Louis de Broglie, New Perspectives in Physics, New York: Basic Books, 1962, p.184

«[…он сказал мне, что]* всякая физическая теория должна быть такой, чтобы ее, помимо всяких расчетов, можно было проиллюстрировать с помощью простейших образов, чтобы даже ребенок мог ее понять.»
— Льоцци, Марио. История физики, пер. Э.Л. Бурштейна, М.: Мир, 1970 (Mario Gliozzi, Storia della fisica, Torino: Storia delle scienze • Volume secondo, 1965), стр. 401 (там же примечание: «Цитируется по книге L. De Broglie, Nouvelles Perspectives en Microphysique, Paris, 1956, p. 236.»)
* доб. моё

Кроме рассмотренного варианта, в уже упомянутом сборнике цитат Эйнштейна более близкого ничего нет. Опять же, там есть раздел псевдоцитат и ошибочных присвоений, в который помещён самый близкий вариант (стр. 482): «You do not really understand something unless you can explain it to your grandmother.»
Отсюда следует, что утверждение MarcusAurelius «Вы могли прочитать это у Воннегута, но я говорю про первоисточник.» ошибочно. Возможно, подразумевался общий смысл, соответствующий достоверному высказыванию, а не сам неверный вариант его, но в таком случае оно не более уместно, поскольку относится к другой предметной области.

Как говорил Ленин, «главная проблема цитат в интернете в том, что люди сразу верят в их подлинность».
+1
MarcusAurelius, #
Почему бы просто не назвать вещи, естественными для ИТ словами: Callback, анонимный делегат, перегрузка оператора класса?
0
rachiu, #
И эти слова должен понять ребенок? :-)

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

–4
MarcusAurelius, #
Ну если математики пришли в чужой монастырь к программистам, то будьте любезны изъясняться терминологией программистов или же сделать адекватный словарь, понятный программистам. Ребенку тоже можно объяснить теорию категорий, поверьте, но для этого нужны: понимание предмета и педагогическая гениальность, я бы не рискнул даже пробовать.
–4
ansl, #
Насколько мне известно, программирование является разделом математики. По крайней мере, так было, когда я учился.
+1
MarcusAurelius, #
Мы о разных программированиях говорим, есть "математическое программирование" — это раздел математики, который изучает задачи комбинаторной оптимизации, нахождения экстремумов, задачи целочисленного программирования, задачей линейного и нелинейного программирования, динамическое программирование, стохастическое, параметрическое программирование.

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

Математика и физика, например, тоже долгое время развивались внутри философии и теологии, обслуживая их задачи, но мы же не относим сейчас математику к разделу теологии — это смешно, но поверьте, в 12-ом веке это было не смешно.
+1
jtootf, #
Ой, да бросьте. Программирование как прикладная инженерия размазано настолько тонким слоем по предметным областям, что пересечения с сугубо абстрактной математикой возникают сплошь и рядом — от кватернионов в 3D-моделировании и динамического программирования в кодогенерации до лямбда-исчисления и SKI-комбинаторов в задачах проектирования (и реализации) DSL.

Вчера монады были уделом алгебраистов как модель теории, а нынче любой C#-программист без математического образования радостно использует LINQ, а то и Rx Framework. Да, программирование и математика — это не одно и то же, но самые интересные вещи происходят именно там, где они пересекаются. Stay tuned! :)
0
nikitad, #
Математика — всего лишь стандартизированный язык для обмена знаниями различных областей. Неважно, откуда ты родом и кто по профессии — если ты изучал этот язык, то сможешь понять, какую информацию тебе пытаются передать. Например, инженер-строитель, работая в паре с программистом (нормальным программистом!) при разработке какого-нибудь CAD, передает ему знания своей предметной области как раз с помощью математики.
+1
vpatryshev, #
Я вообще-то программист; но изъясняться на примитивном уровне пэхэпэшников и вижуал бейсиков не планирую. Эти поколения тупых быдлокодеров приходят и уходят; зачем бы это им загружать мозги излишними знаниями, если им самим не треба? И вы не дети. Вы взрослые люди.
+1
Nashev, #
эти слова должен понять программист
+3
jtootf, #
Ну так программисты должны развиваться, не? Программисту на FORTRAN слова «класс», «объект», «делегат» или «замыкание» тоже были бы непонятны.
+4
Qbit, #
> Почему бы просто не назвать вещи, естественными для ИТ словами: Callback, анонимный делегат, перегрузка оператора класса?

Это примерно так: «Да что вы мне про какие-то вещественные числа рассказываете, непрерывные притом. Я программист, у меня двойная точность, экспонента/мантисса, IEEE 754, все дела.»

> анонимный делегат

Применение «термина» «анонимный делегат» на собеседовании на должность .NET-разработчика в некоторых конторах является достаточным основанием для отказа соискателю.
–2
Nashev, #
я сочувствую этим конторам. Но отчасти они правы — если соискатель и сотрудники конторы разговаривают на разных уровнях абстракции, и не способны подняться до уровня соискателя — им обоим проще разойтись, чем ему одному переучивать контору.
+3
Qbit, #
> я сочувствую этим конторам.

Это что-то из разряда «Мне вас жаль»?

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

Есть «делегат», есть «анонимный метод». «Анонимный делегат» — это что-то типа прийти на турнир гроссмейстеров, и в обсуждении называть ферзя королевой, ладью турой а слона офицером. Какие уж тут «разные уровни абстракции» и «подняться до уровня соискателя», лол.
–1
Nashev, #
> Это что-то из разряда «Мне вас жаль»?
именно.
+1
vpatryshev, #
Ваши кучи и делегаты тут ни при чем. Попробуйте выучить несколько новых слов и понятий; может оказаться интересным; если ж не хотите — значит, этот текст не для Вас.
0
alexkolzov, #
Эта фраза принадлежит не Энштейну, его работы при жизни мало кто понимал, да и сейчас понимают далеко не все. Вы можете объяснить теорию относительности ребенку, или хотя бы неподготовленному взрослому? Автор попытался максимально кратко и полно изложить суть сложной математической теории. Задача не из легких, но попытка хорошая.
0
rapkasta, #
win!
>Еще один пример монды это map/reduce от Google.
+5
EvgK, #
Мне кажется, все кто хотел понять, что такое монады — уже давно понял. У тех же, кому это не нужно, или кто не понял по другим источникам — по такой статье разобраться в этом все равно нет никаких шансов.
+1
DustCn, #
А может кто то объяснить — нахрена нужен матан для проектирования усилителя?
+7
halyavin, #
Потому что AЧХ усилителя зависит от дифференциального уравнения которому он подчиняется.
0
DustCn, #
Ииии…
Вот матан, вот куча рассыпухи — транзисторы там, всякая мелочь типа конденсаторов резисторов и тп.
Как мне спроектировать усилитель? Вы уверены что вам для этого нужен матан а не скажем аналоговая схемотехника?
+2
Goder, #
Проектирование и реализация — разные вещи. Для проектирования вам транзисторы не нужны.
+3
Goder, #
матан а не скажем аналоговая схемотехника?

Аналоговая и цифровая схемотехника не использует матан? :)
+2
DustCn, #
Для рассчета усилителя достаточно алгебры и уже рассчитаных до вас схемотехнических решений.
+1
Goder, #
Вы проектировали усилитель?:)
0
halyavin, #
Нет, я пытался читать по ним книжку. Это то немногое, что я из нее понял.
+2
halyavin, #
Теперь я знаю определение монады. Осталось понять что это такое…
+4
bw3d, #
«Это как говорить об электричестве не используя мат.» O_o
НЛО прилетело и опубликовало эту надпись здесь
+3
megalol, #
Мне кажется, что начинать объяснять монады надо всё же так, как это делает подавляющее большинство популярных туториалов

Think of a monad as a spacesuite full of nuclear waste in the ocean next to a container of apples. now, you can't put oranges in the space suite or the nucelar waste falls in the ocean, *but* the apples are carried around anyway, and you just take what you need. — Dons

Thought an illustration might be useful:
НЛО прилетело и опубликовало эту надпись здесь
+1
jtootf, #
It depends — и от целей, и от конкретного человека. Лучшим средством понять монады в теоретическом смысле лично для меня стала книга Лейнстера по n-категориям (хотя казалось бы); ну а в практическом — опыт проектирования с их использованием в Haskell.

Учитывая, что в последнем категориальные конструкции весьма ограничены (за пределы категории типов Hask тебя никто не выпустит), пересекаются эти две области — теоретическая и практическая — если и часто, то в весьма небольшой области.
+13
voidlizard, #
Такая статься на Хабре — прекрасный троллинг!
+2
sylvio, #
Вы считаете это не относится к computer science? Или слишком сложно?
Конечно, это не очередная новость про патентны или css-хаки, но и полезность у неё значительно выше. Достаточно только приложить немного усилий для понимания.
+4
Goder, #
Честно говоря, полезность этой статьи сомнительна, т.к. вместо объяснения или хотя бы полноценных определений автор пробежался «галопом по европам», собрав все в кучу. Если кто-то, не знакомый с теорией категорий и Haskell, поймет что-нибудь после этой статьи, я очень удивлюсь.
0
sylvio, #
Да, от читателя требуются некоторые усилии, чтобы разобраться в неизвестных терминах и определениях.
Это презентация оформленная статьей, она не претендует на исчерпывающее описание теории категорий или монад, а показывает путь, по которому можно получить монады в понятиях теорката.

Если кто-то заинтересовался, это будет хорошей отправной точкой, как было для меня.
+2
voidlizard, #
Скажите, каким мат. аппаратом надо владеть, что бы понять статью?
И сами ответите на свой вопрос
+1
jtootf, #
Матаппаратом первого курса математического факультета (можно прикладного) практически любого ВУЗа. Единственно сложные вещи — отсылка к топологическим пространствам и парадоксу Рассела, но ни на первом, ни на втором внимание в статье не заостряется.
–2
voidlizard, #
Да ладно, теоркат и теорию групп дают на первом курсе?
+2
jtootf, #
Весь необходимый для понимания объём теории категорий дан в этой статье. Впрочем, если вам что-то непонятно — задавайте конкретные вопросы, чего время терять.

Что касается теории групп, то её здесь просто нет. Прочитать определение группы — дело десяти секунд, гомоморфизма — ещё десяти. Неужели это так сложно? При реализации, скажем, тривиального парсера вам придётся столкнуться с куда более сложными абстракциями.
0
mikhanoid, #
Про парсер — это вы загнули. Там, наоборот, абстракции менее высокие, потому более понятные и простые. Деталей — больше, но они проще. А вот эта теория категорий и монады. Я даж экзамен на отлично по ней сдавал, и регулярно перечитываю статьи, но блин, не чувствую и не понимаю, нафига это всё надо, и какой в этом смысл.
+1
jtootf, #
Понятие конечного автомата проще понятия группы? На минуточку, первое — это пятёрка (множество состояний, начальное состояние, множество заключительных состояний, алфавит, функция переходов); второе — тройка (множество, бинарная операция, нейтральный элемент) плюс аксиома наличия обратного элемента. Это окромя иерархии Хомского, (E)BNF-нотации, PEG и прочих Iteratees. Вы либо неискренни, либо обладаете исключительным складом ума, упрощающим понимание CS-специфики.

Как вы могли сдавать (на отлично!) экзамен по теории категорий и не знать, зачем оная теория нужна — я не знаю. Видимо, так оно вам нужно.
+3
mikhanoid, #
Оно действительно не нужно :) И там не было вопроса, зачем она нужна, там были определения и теоремы. Которые легко воспроизвести, но понять их суть… Вот фиг поймёшь, как мне кажется.

А насчёт автоматов. Там же вполне естественные пятёрки. Понятно, какая материя под ними находится, зачем они нужны, из каких задач взялись и что дают. Алфавит — это алфавит, переход — это переход.

А в теории категорий? Ну определили свойства… Ну вот даже с той же монадой. Хорошо, определили. Но это совершенно не даёт понимания того, как механизм работает. Следовательно, это абстракция гораздо более высокого уровня, чем автомат.

Ведь, в принципе, я могу монадой считать и pipe в Bash, и какой-нибудь pass в Ruby, и вот тот же LINQ. Огромное количество различных объектов подпадает под определение… При чём, их ничего кроме этого определения не связывает, ничего из того, что pipe — монада, вывести нельзя (ну, я не встречался с таким).

И… Ну хорошо, есть очень мудрое определение. И что с ним делать? Зачем мне его надо изучать?
+3
jtootf, #
Значит, так учили. Функторы естественным образом возникли в топологии, а аппарат теории категорий помог достичь существенных достижений в объединении различных областей математики (доказательство эквивалентности расширений Галуа и накрытий, например). Почитайте, чем занимаются Лейнстер, Баец, Мазур, Лури. Почитайте про недавнее доказательство гипотезы Баеца-Долана, про кобордизмы и TQFT.

И не надо передёргивать, я вас прошу, замечание о простоте было в сторону используемых определений из теории групп. Что касается «я могу монадой считать», то это уже гуманитарщина какая-то: абстракции вида «эта конструкция встречается часто, её надо обобщить» в программировании встречаются направо и налево — от функций и классов до параметрического полиморфизма и шаблонов проектирования. Что такого особого в понятии монады? Тот факт, что её корни растут из абстрактной алгебры, волшебным образом отключает мозг?

И что, блин, значит «надо изучать»? Вы «изучаете» понятия объекта и класса? Штудируете работы Карделли? Для алгебраиста монада — это модель теории; для программиста — тривиальный паттерн проектирования, не более того. Вполне естественная тройка, выражаясь вашим языком.
+2
mikhanoid, #
Естественно я изучаю понятие класса и объекта. Без понимания того, как это всё работает нормально писать эффективные программы сложно.

А монады, сколько не изучай, не знаю… Не укладываются они в мою интуицию. И дело совсем не в алгебраическом их происхождении. С векторами, группами, полями Галуа я общаюсь вполне себе спокойно, и даже pi-исчеслениями и теорией следов :)

Но монады и категории взрывают мне мозг. Он лихорадочно ищет каких-нибудь материальных примеров, и ничего не находит… Я знаю, что IO — это монада. Знаю, что вызов с текущим продолженем можно описать монадой… Но как-то знания не наполнены эти ничем.

Про топологическую QFT спасибо, почитаю… Но я так немного на неё смотрел… При чём там категории? Но посмотрю внимательнее.

Ну. И про Галуа тоже надо посмотреть. А вообще, я вот знаю про факт объединения — изоморфизм Кэри-Говарда. Ну, хорошо, мощный результат. А польза-то от него какая? Проще программировать не стало. Новых методов тоже не прибавилось. Всё это слишком абстрактно. Хотя, наверное, в данном случае, поля Галуа решают проблему с представлением покрытий? В этом соль?
0
mikhanoid, #
Ой. Накрытий.
+1
jtootf, #
Соль в том, что результаты из одной области оказываются применимыми к другой — и vice versa. Когда что-то множно получить задаром — это, как правило, хорошо.

Я не понимаю, в чём ваша проблема с монадами. Вот функтор — однопараметрический тип, предоставляющий нам map. Вот функтор с отмеченной точкой, предоставляющий нам return (pure). Вот монада, предоставляющая нам join (или bind) и позволяющая инкапсулировать поток выполнения. В ООП-языке у вас объект подключения к БД, в Haskell у вас соответствующая монада. В ООП-языке у вас объект парсера, здесь — монада парсера (или аппликативный функтор парсера, если интерфейс монады избыточен); в ООП-языке у вас объект исключения, здесь — монада исключения. Попробуйте спроектировать хотя бы одно приложения в таком стиле, и вы получите тот же набор базовых навыков, которым вы пользуетесь в ООП. Более того — вы сможете использовать эти навыки и в ООП-языке (реализуя нечто вроде LINQ или элементарно копозицию операций с выбором потока выполнения в рантайме).

А наполнять знания надо практикой. Замените «монады и категории» у мебя на «классы и объекты» — вы получите настолько же осмысленную критику (с которой сталкивается каждый второй студент, познающий ООП). Пока он не начнёт проектировать и применять свои знания в жизни, они для него и останутся ничем не наполненными — независимо от качества учебного материала.

И, кстати, а как вы изучаете понятия класса и объекта? Меня вот на Абади и Карделли не хватило, я на второй-третьей странице засыпать начинаю.
+2
mikhanoid, #
Я классы и объекты снизу изучаю. Как устроены таблицы поиска и всё такое, порождение. Понятно, что можно смотреть сверху, и давать строгое определение тому, что есть такое наследование. Но в ООП (которое я, кстати, очень не люблю), всегда найдётся язык, который не укладывается. Или всегда такой язык можно построить, и от этого fun прибавляется.

Пользоваться же монадами — понятно, как. А вот проектировать… Не знаю. В голове-то есть знания о том, что бывают агенты, бывают call-cc, которые семантически проще… И вот, видимо, это мешает размышлять в монадном стиле.

Вот простой, казалось бы вопрос: хочу я кооперативную многозадачность. Вроде, инструмент для этого, как раз монады. Но я могу запросто это сделать на C или JavaScript, а с монадами — просто вынос мозга какой-то: слишком большой контекст надо хранить, и нифига не понятно, как добиться именно нужной семантики.

Даже систему событий во Frag себе на бумажке по полочкам разложил, а воспроизвести с минимальными, казалось бы, изменениями — фига, не получается. Видимо, не дано.

Зато узнал, где в TQFT используется теоркат. Интересный у них подход с тем, чтобы заявлять, что категория — это данные об объекте. Спасибо за имена.
+1
jtootf, #
Ну так это ведь не изучение классов и объектов — это изучение их реализации. В таком случае надо было бы смотреть на реализацию классов типов в GHC, например.

Рад, что тем-то помог :) удачи!
0
Arris, #
Немного?

Честно говоря, было бы неплохо, чтобы авторы подобных статей писали маленькую сводочку на тему «что это такое, для чего оно нужно и кому оно нужно… а кому не нужно». Неважно, до статьи, после — главное чтобы писали :)

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

Да, возможно это очень интересная штука… для тех кто в этом разбирается. Ну так сделайте же что-нибудь, чтобы эта штука стала чуть более интересной для тех, кто в ней не разбирается!

P.S. Возможно я слишком категоричен. И извините за некропостинг :)
0
Arris, #
P.P.S. Вообще по поводу сводки — пожелания относится к авторам любых статей, но часто это ненужно — предмет статьи очевиден.
0
sylvio, #
Тут такое дело, что если вы не знаете зачем, то оно вам и не нужно. А если с монадами вы сталкивались (в других статьях или на практике), то вам уже интересно и мотивировать вас не надо :)
Эта статья не из категории «Введение в программирование».
+3
vics001, #
Статья напоминает книжку для аспирантов для математических факультетов.
На первых 2 страницах выписываются все школьные определения и определения 1-3 курса, а дальше со словами эта, эта и эта теорема очевидна, продолжается рассмотрение топологических пространств.

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

Пока осилил одну треть теории :) Есть замечания:
1.

+1
vics001, #
Натуральные числа как объекты, матрицы как морфизмы. Перемножение матриц будет играть роль композиции, а единичная матрица NxN будет единичным морфизмом N → N.

Наверно имелось в виду вектор N из натуральных чисел, иначе как действует морфизм (матрица) на число?

2. Категории образуют категорию? Тут надо быть крайне осторожным и пояснить, что некоторое множество категорий образуют категорию, потому как в общем случае класс категорий не является множеством и в вашем определение не может образовывать категорию.
+1
jtootf, #
Наверно имелось в виду вектор N из натуральных чисел, иначе как действует морфизм (матрица) на число?


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

Категории образуют категорию?


Лирическое отступление про малые категории в статье присутствует, его недостаточно? Не думаю, что было бы уместно придерживаться строго формальных определений в популярной статье.
+1
vics001, #
Я читал, что не действует. Но как если есть число 5 и (морфизм) матрица [[1,2],[3,4]] определить чему оно соответствует. Или даже так у нас есть 2 числа A=5, B=4 как определить множество морфизмов? А то получается объекты категории могут быть «огурцами», а морфизмами матрицами.

Или имелось в виду скалярное произведение?
+1
megalol, #
А то получается объекты категории могут быть «огурцами», а морфизмами матрицами.

Вы только композицию и единичную матрицу определите, чтобы ассоциативно с огурцами было.
А вообще, вы не можете представить функцию, которая из 5 сделает [[1,2],[3,4]]?
0
megalol, #
Нашел определение (и теперь ясно, почему числа натуральные): каждой паре чисел n, m ставится в соответствие стрелка n->m, которая является множеством всех матриц m x n, что в статье было опущено. То есть главное не сами числа, а размер матриц, который они задают.
+2
megalol, #
(Mat) which has as objects the natural numbers N and for which Hom(Mat)(m; n) is the set of all real (mn)-matrices, idn: n! n is the unit matrix, and the composition is defined by A.B = BA,
where BA is the usual multiplication of matrices.
+1
vics001, #
О, понятно. Тут еще один важный момент в статье опущен:
«причём каждому морфизму соответствует единственные A и B» (Википедия).

Так хотя бы понятно становится, что множество элементов состоит из 1 элемента N, а единичный морфизм единичная матрица. Кстати, пример очень хороший, если понять :)

P.S.: Если объекты все числа, а морфизмы все матрицы (1x2, 2x1, ...), то тогда непонятно что такое единичный морфизм.
+1
vics001, #
Сори, разобрался. Для каждого объекта задается свой тождественный морфизм, поэтому пример что объекты категории все числа абсолютно корректен. А если объект категории одно число, то уже подкатегория получается :)
+1
jtootf, #
Объекты в данном случае не огурцы, а натуральные числа — размерности матриц. Множество стрелок между объектами A и B (A=5, B=4) — это множество всех матриц, размерности AxB (5x4 в данном случае).
+1
vpatryshev, #
Спасибо за замечание; поправил это в английском оригинале.
+2
vics001, #
Любая группа может быть рассмотрена как категория: группа элементов это морфизмы над единственным объектом.
Тождественная функция это нейтральный элемент группы. А композицией является умножение.


Мне кажется этот пример стоило бы записать по-другому, если я правильно понял:
1. Объектами категории — являются элементы группы.
2. Морфизмами категории — являются операции умножения элементов группы справа (операция умножения ассоциативна, а id морфизмом является единичный элемент).

Как я понял может быть несколько категорий? Когда морфизмы это умножение только на единичный элемент справа? Или на специальное подгруппу вводящее все элементы в эту подгруппу.
+3
jtootf, #
Неправильно. Ну то есть это совсем другой пример.

Категория C из одного объекта A — это моноид (тройка вида Hom(A, A) (множество всех стрелок из A в себя же), операция композиции стрелок, единичная стрелка). если потребовать, чтобы все стрелки были изо- (то есть обратимыми), получим группу.

Если таким образом мы определим группу в категории множеств, получим обычную группу. Если таким же образом определим группу, например, в категории гладких многообразий, получим группу Ли.

Что же касается «может быть несколько» — категория это всего лишь (достаточно слабая) алгебраическая структура. Выделить её можно везде, где удовлетворяются её аксиомы.
+2
vics001, #
Уфф, вам бы разъясняющую статью написать :) Кажется мне, примеры должны быть рассмотрены очень обстоятельно с достаточным описанием:
1. Объект категории единственный — целиком группа.
2. Каждой паре объектов категории, а она всего одна, соответствует множество морфизмов, а именно элементы группы.
3. Для морфизмов естественным образом определена композиция, как умножение элементов в группе.
4. Так как объект единственный, то определить можно один тождественный морфизм, это и есть единица группы.

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

+1
jtootf, #
Касательно предложенного определения группы — имейте в виду, что стрелка в категории не является бинарной операцией. У неё есть домен, есть кодомен — и всё. Для того, чтобы задавать бинарные операции на объектах категории, имеющегося определения уже будет мало (для этого нужна моноидальная категория).
+3
jtootf, #
каждое состояние машина становится функцией


Пепервод ужасен: во-первых, подстрочник с английского; во-вторых, изобилует подобными ошибками. И без того не самый простой текст читать в таком виде становится весьма затруднительно.
+2
jtootf, #
Впрочем, я тоже хорош.
+1
sylvio, #
Спасибо, исправил.
Такие ошибки возникают из-за того, что в процессе перевода по-разному формулируешь и переписываешь предложения. Я готов исправить остальные, самому их сложно найти из-за того, что взгляд «замылен» после неоднократного прочтения статьи.
+1
gribozavr, #
state machine — конечный автомат
+1
gribozavr, #
Ой, state machine — просто автомат. А вот finite state machine — конечный автомат.
+1
boxfrommars, #
не очень понятно замечание «мы не можем ожидать, что «все объекты» или «все стрелки из a к b» образуют множество». неужели фраза «все стрелки из a к b» не определяет множество? и что же она тогда определяет?
причём из Баеза: «категория C состоит из… и множеств hom(a,b) морфизмов из a в b для каждой пары a, b»
0
jtootf, #
неужели фраза «все стрелки из a к b» не определяет множество? и что же она тогда определяет?


Класс. Категория — это (как правило) некоторая теоретико-множественная модель метакатегории; в качестве аксиоматики для построения модели используют (опять же, как правило) NBG — сиречь, разделяют множества (set) и классы (proper class). Цель подобного разделения — избежание парадокса Рассела (категория всех категорий подвержена ему в той же мере, что и множество всех множеств).
0
pennanth, #
Как подобное разделение спасает от парадокса Рассела? «Класс» — это то же «множество», только с дополнительным «атрибутом» isClass. Если рассмотреть множество всех классов множеств, получаем ту же историю: «найти класс множеств, который не включен ни в одно множество классов».
+2
jtootf, #
не получаем. если бы вы удосужились хотя бы почитать википедию, вы бы знали, что описанная вами (парадоксальная) конструкция в NBG невозможна
+1
pennanth, #
Спасибо за ссылку. С NBG я действительно не знаком, только с ZFC с аксиомой выбора.
+2
jtootf, #
Тогда приятного чтения. Вселенской справедливости ради замечу, что ZFC — это уже ZF с аксиомой выбора.

Также стоит отметить, что категории можно строить аксиоматически без опоры на теоретико-множественные модели; однако это отдельная и достаточно нетривиальная тема для обсуждения.
+1
vpatryshev, #
Не согласен; категория — это не теоретико-множественная модель. В категориях можно построить теорию множеств (ну точнее, в топосе с NNO); можно и наоборот — но эти две теории независимы.
+1
vpatryshev, #
Нет, не определяет. Теория категорий не нуждается в теории множеств. Теория множеств, как говорят сторонники интеллигентного дизайна — всего лишь теория; и их много разных.
+4
afiskon, #
За статью спасибо. Но если честно, на середине я потерял ход мысли. Возможно, после третьего или пятого прочтения пойму.

// Почему среди математиков так мало людей, умеющих объяснять вещи доступным (нам, простым смертным) языком?
0
vics001, #
Обычно математикам нужно объяснять только другим математикам, а там ценится краткость и умение абсолютно точно выразить некоторую истину.
+1
mikhanoid, #
К сожалению, иногда за этой точностью и краткостью скрывается пустота. Или даже не иногда, а часто… Великие математики, всё же, умели простым языком всё объяснить.
+1
jtootf, #
Великие — это какие? Знаете, через сколько лет работа Галуа была оценена сообществом? А знаете, почему?

Популярное изложение и хорошее научное изложение — разные вещи. Розенфельд писал предельно просто, но сжато и с минимумом учебных примеров — для специалиста его книги на вес золота, но неспециалист вряд ли извлечёт из них много пользы. Означает ли это, что он писал плохо? Не думаю. Арнольд, с другой стороны, минимально использовал формализмы, и делал упор на интуитивные примеры (предполагая множество вещей самоочевидными и не требующими пояснений). Скрывалась ли за его краткостью пустота? Тоже вряд ли.
+1
vpatryshev, #
А вот Вы не хотели бы изучить японский за полчаса, по слайдам?

Требуется время. И не вините японцев, что у них канджи сложная, и катакана ни к чему.
+1
mikhanoid, #
Последнее предложение как-то противоречит начальным заявлениям о том, что монады нужно знать, как матанализ :) Ибо знание не позволяет объяснить то, зачем они в Haskell.

С житейской-то точки зрения всё просто. Монады в Haskell нужны, чтобы автоматически организовать последовательный поток данных между функциями. Для этого у нас есть >>= (bind, а не join, кстати), который позволяет взять функцию и «подшить» её в цепочку вызовов. И это, кстати, не сама mu, а T(mu), ну, если верить сигнатурам.

Ну да, если так делать — получится монада. Но я вот не думаю, что разработчики Haskell прямо так и хотели вшить в язык нечто монадическое. Просто потом оказалось, что придуманный ими механизм — это монада.
0
jtootf, #
join в Haskell тоже есть, определения через join/return и bind/return эквивалентны. А чтобы не думать, чего хотели разработчики Haskell, можно почитать историю языка.
0
mikhanoid, #
Эмс… Ну, спасибо за ссылку, конечно. Я не особо фанат Haskell и всё читать не буду, но раздел 7 подтверждает высказанную мной гипотезу.
+2
vpatryshev, #
Напротив. Была такая проблема, что нечистый код никак не формализовать. И тут появился Моджи с монадической интерпретацией; хаскельцы за него схватились, и таким образом более-менее формально (и не всегда так уж правильно) впендюрили в Хаскель монаду.
–1
rubyrabbit, #
Где аналогии, конкретные примеры и показательные иллюстрации?
Это просто мысли в слух человека, который в этом варится?
Термины не определены, наглядных примеров к определениям нет.
Тройка.
+1
jtootf, #
Наглядных примеров дано шесть — три из программирования, три из математики. Мало? Какие аналогии вас интересуют? Что такое «показательные иллюстрации»?

Если вас смущают какие-то термины — спрашивайте конкретно, я поясню.
+3
yuriv, #
На мой взгляд этой статьей Вы ещё больше всё запутали, нет с точки зрения математики и теории категорий всё верно. А вот с точки зрения прагматики и конкретно разработки ПО нет ничего. Какие задачи в разработке ПО позволяет решать теория категория вообще и монады в частности? Какие аналогии между категориями(монадами) и конкретными программистскими решениями просматриваются? Как мне, проектировщику ПО, эти категории(монады) помогут в моей работе?

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

И при этом, Вы не обижайтесь, изложено всё очень сумбурно — такое ощущение, что Вы сами недавно разобрались с этим предметом и решили представить свои умозаключения в публичном виде. Это похвально, но Вы указали лишь реперные точки своих умозаключений, опустив рассуждения и это делает изложение ещё более запутанным, чем если бы это было описано чисто математическим языком. К сожалению это не только Ваша беда, таким подходам грешат практически все «переводы» академических работ, выкладываемых, якобы для научно-популярного обозрения — ни рыба — ни мясо. Для научной статьи слишком фривольно, для научно-популярной — слишком не понятно — и не понятно — зачем? — В чём практическая польза от использования теории категорий в повседневной жизни, в данном случае, разработчика ПО.
0
jtootf, #
Промахнулся комментарием. Вот это должно было быть здесь.
–1
yuriv, #
И что? А изложено так будто только что разобрались и решили поделиться этим знанием с окружающими. Я ещё раз подчёркиваю, что Вы написали не понятно что — это не научный доклад, и не научно-популярная статья, и даже не ознакомительный материал — на пальцах. Простите, но теория ради теории ценна только для теоритиков, для практиков ценно применение. Я понимаю гугль, мэп-редьюс и всё такое, но это готовое решение и им успешно пользуются люди даже не подозревая о наличии монад. От статьи, лично я, ожидал следующего: В разработке ПО часто встречается следующая задача — далее формулировка, для её решения в относительно общем виде мы применим теорию категорий — объяснение — как, с попутным изложением материала из теории категорий с привязкой к конкретной задаче. Вы же предпочли запостить ссылку на опыт знакомства с теорией категорий.
+1
jtootf, #
Я, если что, ничего кроме комментариев в этом треде не писал. Не надо считать меня автором исходной статьи. Зачем я запостил ссылку, я пояснил.

Что касается ожиданий и недопониманий — в этом треде я уже не менее двух раз предлагал объяснить непонятные моменты. Конкретных вопросов пока не последовало. Если они есть у вас — прошу, не стесняйтесь.

И да — пользователи LINQ могут ничего не знать о наличии монад, но автор LINQ о них прекрасно осведомлён. Именно благодаря этому у LINQ в принципе есть пользователи.
+2
vpatryshev, #
Очень смешные возражения. Я такие слышал в адрес языком программирования (на ассемблере лучше), в адрес ООП, в адрес ФП, в адрес джавы — каждый раз приходит невежественный умник и объявляет, что в народном хозяйстве оно не треба.

Вам не треба, вы и не кушайте. Этот текст не для Вас; Вы прекрасно докантуетесь до пенсии без всех этих сложностей. Скорее всего.
0
yuriv, #
Вы больны дислексией. Я дал отзыв о статье, а не о теории категорий. С теорией категорий я знаком и, более того, использую в своих проектах. А такие умники как Вы учат наизусть талмуды не потрудившись их понять, по одной простой причине: страсть к моде и попугайству заложены с детства. Общаться далее не наумерен: убогим — убогово.
+2
vpatryshev, #
Ой. Извините. Одичал тут в Америке. Отвык уже общаться в таком агрессивном стиле. Вообще зря полез; употребляйте вы себе на доброе здоровьичко, и всего вам хорошего. Как проектировщик ПО, использующий их в своих проектах, Вы могли бы рассказать о своём опыте.

Ну типа там вот у Вас монада крутит динамо-машину, или что-нибудь в таком духе. Токарные станки, бухгалтерия, всё такое.

Извините. Действительно отвык общаться с полоумными идиотами. Вы как-нибудь устаканьтесь, или Вы в курсе, шо це за параша, декартово замкнутые категории (шукайте, шукайте на гугле), или же Вы не знаете, и чешете репу, куда ж бы это их употребить в народном хозяйстве.
0
yuriv, #
Всё-таки дислексия — печально.
+1
jtootf, #
Не особо желая дискутировать по поводу применимости (здесь уже полный топик подобных комментариев), оставлю лишь заметку автора статьи о своих отношениях с теорией категорий. Просто за недавно разобрались глаз зацепился.
+1
mikhanoid, #
Так автора и призывают подробнее вот об этом:

11. Now here in California, the word «monad» rings the bell. So I honesty try to put it in the proper perspective, writing some kind of «tutorials» and «talks», writing again the code that calculates stuff, opening presheaf.com, and ready to talk to anybody willing to listen.
+1
jtootf, #
Об этом его можно попросить директом, думается мне.

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