17

圏論と抽象代数は、関数を他の関数と組み合わせる方法を扱います。複雑さの理論は、関数の計算がどれほど難しいかを扱います。これらの研究分野がそのような自然なペアのように見えるので、誰もこれらの研究分野を組み合わせているのを見たことがないのは私には奇妙です。誰かがこれを以前にやったことがありますか？

やる気を起こさせる例として、モノイドを見てみましょう。操作がモノイドである場合、操作を並列化できることはよく知られています。

たとえば、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関数がない理由だと思います。最適な実装は、モノイドの複雑さに依存します。

これら2つのモノイドの違いを説明する便利な方法があるはずです。次に、これらの違いでコードに注釈を付け、モノイドの複雑さに応じて、使用する最適なアルゴリズムをプログラムに自動的に選択させることができるはずです。

4

3 に答える 3

10

私はこれらのテーマの専門家であるとは主張していませんが、この考えに光を当てることができるかもしれません.

まず、圏論について考えてみましょう。圏論は、非常に高いレベルでの数学的構造の研究です。カテゴリの概念は非常に一般的であり、非常に多くの数学的オブジェクトがカテゴリを形成します。圏論は当初、信じられないほど純粋で抽象的であると考えられていましたが、これらはしばしば数学で行われるため、コンピューター サイエンスや量子力学などの応用分野で多くの用途があることが判明しました。モナドは、関数型プログラムのセマンティクスについて推論する際に非常に役立つことが判明しました。関数型プログラムは一般に表示形式で表現されます (したがって、計算にいかなる種類の順序も強制せず、結果だけを求めます)。このことから、モナドも非常に優れた設計パターンであることもわかりました関数型プログラムを書くためのものであり、その有用性により、Haskell の設計 (do 記法など) で非常に目立つようになりました。ファンクター、アプリカティブ、モノイドはすべて、モナドよりも強力ではないが、よりアプリカティブなオブジェクトとして後に続きました (しゃれは意図されていません!)。

ただし、圏論はこの種の構造をより一般的な方法で研究し、数学 (および物理学など) の多くの分野に関連することが判明しています。専門家ではないので、これがどれだけ複雑性理論に関連するかはすぐにはわかりませんが、試してみましょう。

複雑性理論は、計算の実現可能性に関係しています。チューリングなどは、一般には計算できない関数がいくつかあることを示しました (たとえば、停止問題、ビジー ビーバー問題など) が、特定の計算が原則としてどれほど簡単かという問題は、一般に難しい問題です。おそらくご存じのとおり、アルゴリズム (チューリング マシンとして表すことができます) は、漸近的な実行時間に基づいて複雑さのクラスに分類できます。非常に多くの複雑性クラスが特定されていますが ( The Complexity Zooを参照)、これらのクラスの構造についてはほとんど知られていません。有名なP = NP問題は、複雑さを推論することがいかに難しいかを示しています。

複雑性クラスの性質と、それらの間の関係を証明することがどれほど難しいかについての直感から、複雑性クラス内にカテゴリを確立するのは難しいと思っていました。明らかに、チューリング マシンのセットはカテゴリを形成しますが、O(n) のマシンのセットは? または P のマシンのセット? これは、複雑さの専門家にとって良い研究の方向性かもしれませんが、そうではないかもしれません! 個人的には、もっと頑張らないとなんとも言えません。

次に、モノイド内の複雑さと並列化戦略の例を考えてみましょう。この 2 番目のセクションが最初のセクションとほとんど関係がないように思われる場合、それは、これらが非常に異なる概念であると考えているためです。1 つ目はカテゴリと複雑さの数学、2 つ目は特定の設計パターン内でのアルゴリズムの並列化の詳細です。

特定のタイプがモノイドであることがわかっている場合、それを扱う複雑さについてどのような理由が考えられるでしょうか? これはからのクラス定義です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

これにより、実装と並列化を分離できることに注意してください。この種の概念は、特に個々のアルゴリズムの複雑さを説明する注釈から簡単に自動化できるとは思いません。

要約すると、圏論は将来の複雑さの研究に役立つツールになる可能性があります。しかし、これが並列化戦略の自動生成につながる可能性は低いと思います。

于 2012-07-31T09:09:25.510 に答える
0

クイックグーグルは論文を示しています：

Safe Recursion Revisited: 低複雑性のためのカテゴリセマンティクスと型システム

また、Japaridze による多項式時間演算に関する研究も覚えています。http://arxiv.org/abs/0902.2969 を参照してください。

そこから始めて、参考文献を見ていくことができると思います。

于 2012-09-01T18:07:59.973 に答える