有没有一种理论结合了范畴理论/抽象代数和计算复杂性？

Question

范畴理论和抽象代数处理函数可以与其他函数结合的方式。复杂性理论研究一个函数的计算难度。对我来说很奇怪，我没有看到任何人把这些研究领域结合起来，因为它们看起来像是如此自然的组合。以前有人这么做过吗？

作为一个激励的例子，让我们来看看MonoIds。众所周知，如果一个运算是一个半群，那么我们可以并行化这个运算。

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

foldl1' (+) [0..999]

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

似乎应该有一个方便的方法来描述这两个单元体之间的区别。然后，我们应该能够用这些差异来注释我们的代码，并让程序自动选择最佳算法来使用取决于一个半群的复杂度。

Answer 1

我并不声称自己是这些问题的专家，但我可能会对这个想法有所启发。

让我们首先考虑范畴理论。范畴理论是一种在很高水平上对数学结构的研究。范畴的概念是非常普遍的，许多数学对象构成范畴。范畴理论最初被认为是极其纯粹和抽象的，但由于这些东西经常出现在数学中，它在应用学科中有许多用途，如计算机科学，甚至量子力学。单子被证明在推理函数程序的语义方面有很大的用处，函数程序通常是用指称的方式表示的（因此不强迫计算任何顺序，只强迫计算结果）。由此也认识到单子也是编写函数程序的一个非常好的设计模式，它的有用性导致它在Haskell的设计中非常突出（即do符号等）。函子、应用子、单子都是后来出现的对象，功能不如单子强大，但因此也更适用（没有双关语！）。

然而，范畴理论以一种更普遍的方式研究这些结构，它已经被证明与数学（和物理等）的许多领域有关。作为一个非专家，目前还不清楚这其中有多少可能与复杂性理论有关，但让我们试试看。

如果我们知道某一类型是一个半群，那么我们对处理它的复杂性有什么理由呢？这是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可以手动实现。

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

总之，范畴理论有可能成为未来复杂性研究的有用工具。然而，我不认为这可能导致自动生成并行策略。