Существует ли теория, сочетающая теорию категорий/абстрактную алгебру и вычислительную сложность?

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

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

Например, в Haskell мы можем тривиально определить, что сложение является моноидом над целыми числами следующим образом:

instance Monoid Int where
    mempty = 0
    mappend = (+)

Теперь, если мы хотим вычислить сумму от 0 до 999, мы можем сделать это последовательно, как:

foldl1' (+) [0..999]

или мы могли бы сделать это параллельно

mconcat [0..999] -- for simplicity of the code, I'm ignoring that this doesn't *actually* run in parallel

Но распараллеливать этот моноид имеет смысл только потому, что mappend работает за константное время. Что, если бы это было не так? Списки, например, являются моноидами, где mappend не работает с непостоянным временем (или пространством! ). Я предполагаю, что именно поэтому в Haskell нет параллельной функции mconcat по умолчанию. Лучшая реализация зависит от сложности моноида.

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