Ответ 1
Я не претендую на роль эксперта по этим предметам, но я мог бы пролить свет на эту идею.
Сначала рассмотрим теорию категорий. Теория категорий - это исследование математической структуры на очень высоком уровне. Понятие категории очень общее, и множество математических объектов образуют категории. Теория категорий сначала считалась невероятно чистой и абстрактной, но поскольку эти вещи часто бывают в математике, у нее оказалось много применений в прикладных предметах, таких как информатика и даже квантовой механики. Монады оказались полезными в рассуждениях о семантике функциональных программ, которые обычно выражаются денотационно (и, следовательно, не вызывают никакого порядка вычисления, а только результат). Из этого также было осознано, что монада также является очень хорошим шаблоном проектирования для написания функциональных программ, и ее полезность привела к тому, что она была очень заметной в дизайне Haskell (т.е. Обозначение и т.д.). Функторы, Применения, Моноиды, все это несколько позже, как объекты, менее мощные, чем монады, но, следовательно, также более применимы (каламбур не предназначен!).
Однако сама теория категорий изучает эти структуры гораздо более общим образом, что оказалось актуальным во многих областях математики (и физики и т.д.). Как неспециалист, не сразу понятно, сколько из этого может относиться к теории сложности, но пусть уйдет.
Теория сложности связана с осуществимостью вычисления. Тьюринг и другие показали, что существуют некоторые функции, которые вообще не могут быть вычисляемыми (например, проблема с остановкой, проблема с занятым бобром и т.д.), Но вопрос о том, насколько простой конкретный расчет был в принципе, представляет собой более сложный вопрос в целом. Как вам известно, алгоритмы (которые могут быть представлены как машины Тьюринга) могут быть помещены в классы сложности на основе их асимптотического времени работы. Существует много классов сложности, которые были идентифицированы (см. The Complexity Zoo), но относительно немного известно о структуре этих классов. Известная проблема P = NP показывает, насколько сложно рассуждать о сложности.
Из интуиции о природе классов сложности и о том, как сложно доказать отношения между ними, я бы подумал, что было бы сложно установить категории в классах сложности. Очевидно, что множество машин Тьюринга образует категорию, но множество машин в O (n)? или набор машин в P? Это может быть хорошим направлением исследований для экспертов по сложности, а затем это может и не быть! Лично я не мог сказать, не делая больше работы.
Теперь рассмотрим ваш пример сложности в рамках стратегий моноидов и параллелизации. Если кажется, что этот второй раздел имеет мало общего с первым, это потому, что я думаю, что это очень разные понятия. Во-первых, это математика категорий и сложности, во-вторых, есть особенности параллелизующих алгоритмов в определенных шаблонах проектирования.
Если мы знаем, что определенный тип является моноидом, что мы можем объяснить сложностью работы с ним? Это определение класса из Data.Monoid
class Monoid a where
mempty :: a
mappend :: a -> a -> a
mconcat :: [a] -> a
mconcat = foldr mappend mempty
Конечно, мы не можем сказать ничего о сложности, потому что все, что мы знаем, это тип, как вы догадались. В документации есть это, чтобы сказать о реализации по умолчанию mconcat в Data.Monoid:
-- ^ Fold a list using the monoid.
-- For most types, the default definition for 'mconcat' will be
-- used, but the function is included in the class definition so
-- that an optimized version can be provided for specific types.
То, что я пытаюсь сделать, состоит в том, что mconcat не обязательно может быть обобщено на сложности других операций. Во многих случаях было бы трудно доказать, что какого-то более быстрый алгоритм не существует. mconcat может быть реализован вручную в таком случае.
Вы также указываете автоматическое определение параллельных стратегий. Haskell, безусловно, позволяет определить различные стратегии, из которых многие полезные уже находятся в Control.Parallel.Strategies. Например, parList применяет стратегию параллельно каждому элементу списка:
parList :: Strategy a -> Strategy [a]
parList strat [] = ()
parList strat (x:xs) = strat x `par` (parList strat xs)
отсюда можно определить функцию параллельного отображения.
parMap :: Strategy b -> (a -> b) -> [a] -> [b]
parMap strat f xs = map f xs `using` parList strat
using :: a -> Strategy a -> a
using x s = s x `seq` x
Обратите внимание, что это позволяет разделить реализацию и параллелизацию. Я не думаю, что такое понятие может быть легко автоматизировано, особенно из аннотаций, описывающих сложность отдельных алгоритмов.
Таким образом, возможно, что теория категорий может быть полезным инструментом для будущих исследований сложности. Однако я не думаю, что это, вероятно, приведет к автоматической генерации стратегий параллелизации.