haskell - 是否存在将类别理论/抽象代数与计算复杂性相结合的理论？

Question

范畴论和抽象代数处理函数可以与其他函数组合的方式。复杂性理论涉及函数的计算难度。我很奇怪，我没有看到任何人将这些研究领域相结合，因为它们看起来像是天生的对。有人做过吗？

作为一个激励性的示例，让我们看一下monoid。众所周知，如果一个操作是一个monoid，那么我们可以并行化该操作。

例如在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在恒定时间内运行。如果不是这种情况怎么办？例如，列表是等分体，其中mappend的运行时间不是恒定的(或空格!)。我猜这就是为什么Haskell中没有默认的并行mconcat函数。最佳的实现取决于类半体动物的复杂性。

似乎应该有一种方便的方法来描述这两个类半体动物之间的差异。然后，我们应该能够使用这些差异来注释我们的代码，并让程序根据Monoid的复杂性自动选择最佳算法来使用。

Answer 1

我并没有声称自己是这些主题的专家，但是我也许可以阐明这个想法。

让我们首先考虑类别理论。范畴理论是对数学结构的高度研究。类别的概念非常笼统，许多数学对象构成了类别。类别理论最初被认为是令人难以置信的纯粹和抽象，但是随着这些事物在数学中的发展，它在计算机科学和even quantum mechanics等应用学科中被证明具有许多用途。事实证明，Monads在推理功能程序的语义时非常有用，这些功能程序通常以符号表示(因此，不强制执行任何形式的命令，仅强制执行结果)。由此，人们还认识到monad还是用于编写功能程序的一种非常好的设计模式，它的用处使它在Haskell的设计(即do表示法等)中非常突出。函子，贴片式，Monoids之后都稍晚一些，它们的对象不如单核那么强大，因此也更具贴贴性(没有双关语!)。

但是，范畴论以一种更为通用的方式研究了这类结构，事实证明这与数学(和物理学等)的许多领域都息息相关。作为非专家，目前尚不清楚其中有多少与复杂性理论有关，但让我们开始吧。

复杂性理论与计算的可行性有关。 Turing和其他人已经表明，有些函数通常是不可计算的(例如，停顿问题，繁忙的海狸问题等)，但是从原理上讲，特定计算的难易程度通常是一个较难的问题。您可能已经知道，可以根据算法的渐近运行时间将算法(可以表示为图灵机)放入复杂性类中。已经确定了很多复杂性类(请参阅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

注意，这允许实现和并行化的分离。我认为这种概念不可能轻易实现自动化，尤其是仅通过描述单个算法复杂性的注释即可。

总而言之，类别理论可能会成为将来进行复杂性研究的有用工具。但是，我认为这不会导致自动生成并行化策略。