类别理论和抽象代数处理函数可以与其他函数组合的方式。复杂性理论处理函数的计算难度。我很奇怪，我没有看到有人将这些研究领域结合起来，因为它们看起来像是如此自然的一对。有没有人这样做过？
作为一个激励性的例子，让我们来看看幺半群。众所周知，如果一个操作是一个幺半群，那么我们可以并行操作。
例如在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
但是，并行化这个monoid只是因为mappend在恒定的时间内运行。如果不是这样怎么办？例如，列表是maoids不会运行不定时间（或空间！）的幺半群。我猜这就是Haskell中没有默认的并行mconcat函数的原因。最佳实现取决于幺半群的复杂性。
似乎应该有一种方便的方法来描述这两种幺半群之间的差异。然后，我们应该能够使用这些差异来注释我们的代码，并让程序根据monoid的复杂性自动选择要使用的最佳算法。
我并不是自称是这些主题的专家，但我或许可以对这个想法有所了解。
我们首先考虑类别理论。范畴理论是一种非常高水平的数学结构研究。类别的概念非常笼统，许多数学对象构成了类别。类别理论首先被认为是非常纯粹和抽象的，但由于这些事物经常用于数学，因此它在应用主题中有很多用途，例如计算机科学和even quantum mechanics。 Monads在推理功能程序的语义方面发挥了很大的作用，这些语义通常是用语言表达的（因此不会强制任何类型的计算顺序，只是结果）。由此可以看出，monad也是用于编写函数式程序的非常好的设计模式，其实用性使其在Haskell的设计中非常突出（即符号等）。函数，应用程序，幺半群，后来都作为比monad更强大的对象，但因此也更适用（没有双关语！）。
然而，范畴理论本身是以更为一般的方式研究这种结构，这已经证明在数学（和物理学等）的许多领域都是相关的。作为一个非专家，目前还不清楚这有多少可能与复杂性理论有关，但让我们有所作为。
复杂性理论关注计算的可行性。图灵和其他人已经表明，有些功能一般不可计算（例如暂停问题，繁忙的海狸问题等），但原则上特定计算有多容易的问题是一个更难的问题。您可能已经意识到，算法（可以表示为图灵机）可以根据其渐近运行时间放入复杂性类中。已经确定了很多复杂性类（参见The Complexity Zoo），但对这些类的结构知之甚少。着名的P = NP问题表明了解复杂性是多么困难。
从直觉上了解复杂性类的本质以及证明它们之间关系的难度，我认为在复杂性类中建立类别会很棘手。显然，图灵机的集合形成一个类别，但是O（n）中的机器集合？还是P中的一套机器？对于复杂性专家来说，这可能是一个很好的研究方向，然而它可能不会！就个人而言，如果没有更多的工作，我不能说。
现在让我们考虑一下Monoid中的复杂性和并行化策略。如果看起来第二部分与第一部分几乎没有关系，那是因为我认为这些是非常不同的概念。首先是类别和复杂性的数学，其次是在某些设计模式中并行算法的细节。
如果我们知道某种类型是Monoid，我们可以解释使用它的复杂性吗？这是Data.Monoid的类定义
class Monoid a where
mempty :: a
mappend :: a -> a -> a
mconcat :: [a] -> a
mconcat = foldr mappend mempty
当然，我们不能说复杂性，因为我们所知道的就是你所推测的类型。文档中有关于Data.Monoid中mconcat的默认实现的说法：
-- ^ 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
请注意，这允许实现和并行化的分离。我不认为这种概念可以轻松自动化，特别是仅从描述个别算法复杂性的注释中。
总而言之，类别理论可能是未来复杂性研究的有用工具。但是，我不认为这可能导致自动生成并行化策略。
在肤浅的层面上，复杂性理论家已经做了类别理论 - 事物，他们只是用他们自己的语言来表达它。例如，复杂性类NP是一种类别，其中对象是NP语言，而态射是多项式时间缩减。然后一个完整的问题是这个类别中的初始对象，并且所有NP完全问题都是同构的。像维克的回答一样，将图灵机视为物体并不是很合理。这主要是因为图灵机的形状如何（它们是图灵机的许多不同型号，对于相同的问题具有完全不同的时间和空间复杂性）。但是类别理论的论点观点，即一个范畴的主要兴趣在于态射，告诉我们态射应该是算法。
另一种观点是层次结构。复杂性类在包含下形成一个poset类别，并且有一些很好的限制对象，如P，PSPACE，NC，AC等。
当然，目前尚不清楚分类视角如何帮助我们证明复杂性理论中的定理，以及通过类别理论解决问题是否比解决原始问题更容易。例如，我会考虑从复杂类的poset类别中存在一个非平凡的仿函数，比如说，组的类别是一个极其变革的结果。它有可能将复杂性类别分开，在这个领域当然是非常困难的。
快速谷歌搜索显示一篇论文：
Safe Recursion Revisited: Categorical Semantics and Type Systems for Lower Complexity
我还记得Japaridze关于多项式时间算法的作品，请参阅http://arxiv.org/abs/0902.2969
我想你可以从那里开始，并参考参考。