Читая Удай Редди ответ на Что такое соотношение между функторов в SML и теории категорий? Удай заявляет
Теория категорий еще не знает, как обращаться с функциями более высокого порядка. Когда-нибудь, это будет.
Поскольку я думал, что теория категорий способна послужить основой для математики, то должна быть возможность вывести все математические функции и функции высшего порядка.
Итак, что подразумевается под теорией категорий, еще не знает, как обращаться с функциями более высокого порядка? Можно ли считать теорию категорий основой математики?
functional-programming
category-theory
Гай Кодер
источник
источник
Ответы:
Проблема с функциями более высокого порядка достаточно проста.
Конструктор типа, подобный , не является функтором. Это должно было быть.T( X) = [ X→ X]
Полиморфная функция типа не является естественным преобразованием. Это должно было быть.т ш я с йИкс: T( X) → T( X) = λ f,е∘ ф
Если вы читали оригинальный Эйленберга и Маклейна теория категории бумаги , (PDF) с интуицией они присутствуют крышка этих случаев. Но их теория не делает. Это была отличная статья для 1945 года! Но сегодня нам нужно больше.
Реакция теоретиков категорий на эти вопросы немного озадачивает. Они действуют так, как будто операции высшего порядка формируют идею информатики; они не имеют никакого значения для математики. Если это так, то фундамент математики не будет достаточно хорош для основы информатики.
Но я серьезно не верю в это. Я полагаю, что функции высшего порядка были бы весьма важны и для математики. Но они не были серьезно изучены. Я надеюсь, что когда-нибудь они будут исследованы, и ограничения теории категорий будут реализованы.
источник
[Этот второй ответ представляет собой схему того, как может выглядеть «Теория категорий 2.0», которая правильно работает с функциями высшего порядка.]
Мы давно знаем, как обращаться с функциями высшего порядка, рассуждая о них.
Когда алгебраическая структура имеет операции высшего порядка, гомоморфизмы не работают. Вместо этого мы должны использовать логические отношения . Другими словами, мы должны перейти от « структуры, сохраняющей функции », к « структуре, сохраняющей отношения ».
Если говорить о «единообразных» или «одновременно заданных» преобразованиях типов высшего порядка, естественность не работает. Вместо этого мы должны использовать реляционную параметричность . Другими словами, мы должны перейти от «семей, сохраняющих все морфизмы » к «семьям, сохраняющим все логические отношения ».
Краткое введение в эти вопросы содержится в разделе Питера О'Хирна «Реляционная параметричность» в « Домены и денотационная семантика: история, достижения и открытые проблемы» (CiteSeerX) .
Первая попытка построения «Теории категорий 2.0» сделана в Параметричности и локальных переменных О'Хирна и Теннента (CiteSeerX) .
Кандидатская диссертация Брайана Данфи: Параметричность как понятие однородности рефлексивных графов (CiteSeerX) строится на их основе и аксиоматизирует реляционную структуру, необходимую для получения результатов параметричности. Я бы порекомендовал тезис Данфи для получения хорошего обзора всех вопросов.
Для полноты картины я должен также упомянуть кандидатскую диссертацию Клаудио Гермиды: Фибрации, логические предикаты и неопределенные (PDF) , которая была первой, чтобы изучить логические отношения в теоретическом сеттинге категорий, но его обработка, возможно, слишком техническая для большинства людей.
Я мог бы также добавить, что рассуждения о состоянии - это то, где функции высшего порядка проявляются заметно. Теоретики автоматов были первыми, кто признал, что гомоморфизмы работают неправильно, в исторической статье под названием « Продукты автоматов и проблема покрытия» . Они использовали такие термины, как «слабые гомоморфизмы» и «охватывающие отношения» для обозначения логических отношений. Со временем такие термины, как «симуляция» и «бисимуляция», использовались для обозначения их. Обзорная статья Давиде Сангиорги: « О происхождении бисимуляции и коиндукции» охватывает всю эту раннюю историю и многое другое.
Необходимость реляционных рассуждений постоянно возникает в рассуждениях о состоянии, в частности, в императивном программировании . Мало кто замечает, что скромная точка с запятой - это операция высшего порядка. Таким образом, вы не можете начать думать об императивных программах, не зная, как обращаться с функциями более высокого порядка. Мы продолжаем игнорировать вопросы государственного и императивного программирования, ошибочно полагая, что у математики есть ответы на все вопросы. Так что, если математики не понимают государство, это не должно быть хорошо! Нет ничего более далекого от правды. Государство находится в центре компьютерных наук. Мы будем продвигать науку в целом, показывая людям, как бороться с государством!
источник