問題タブ [abstract-algebra]

モノイドがプログラミングで驚くほど遍在していることはよく知られています。それらは非常に遍在し、非常に便利なので、私は「趣味のプロジェクト」として、それらの特性 (分散データ集約) に完全に基づいたシステムに取り組んでいます。システムを便利にするためには、便利なモノイドが必要です :)

私はすでにこれらを知っています：

• 数値または行列の合計
• 数値または行列積
• 最上位要素または最下位要素を含む全次数の下での最小値または最大値 (より一般的には、有界格子での結合または会合、またはさらに一般的には、カテゴリ内の積または共積)
• セットユニオン
• モノイドを使用して競合する値が結合される写像結合
• 有限集合の部分集合の交点 (半群について言えば集合交点)
• 境界のあるキー ドメインとのマップの交差 (ここでも同じ)
• ソートされたシーケンスのマージ。おそらく、異なるモノイド/セミグループでキーが等しい値を結合します
• ソートされたリストの制限付きマージ (上記と同じですが、結果の上位 N を取得します)
• 2 つのモノイドまたは半群のデカルト積
• リスト連結
• 自己同形組成物。

ここで、操作の準プロパティを同値関係を維持するプロパティとして定義しましょう。たとえば、同じ長さのリスト、または順列まで同一の内容を持つリストを同等と見なす場合、リストの連結は準交換可能です。

いくつかの準モノイドと準可換モノイドと半群があります:

• 任意 (a+b = a または b、キャリア セットのすべての要素が同等であると見なす場合)
• 満足する述語 (a+b = a と b のうち、null ではなく、何らかの述語 P を満たすもの。述語がない場合は null; すべての要素が P の等価性を満たすと見なす場合)
• ランダム サンプルの限定された混合 (xs+ys = xs と ys の連結からのサイズ N のランダム サンプル。データセット全体と同じ分布を持つ任意の 2 つのサンプルが同等であると見なす場合)
• 重み付けされたランダム サンプルの有界混合
• これを「トポロジー マージ」と呼びましょう。2 つの非循環的で矛盾のない依存関係グラフが与えられた場合、両方で指定されたすべての依存関係を含むグラフです。たとえば、各リストの要素が順番に続く順列を生成する「連結」リスト (たとえば、123+456=142356)。

他にどのような存在がありますか?

最近、関数型プログラミング (Haskell と Scala) について知りました。その機能と優雅さは非常に魅力的です。

しかし、モノイドという代数構造を利用したモナドに出会い、数学で学んだ理論的知識がプログラミングに生かされていることに驚き、嬉しく思いました。

この観察により、私の心に疑問が生じました。グループ、フィールド、またはリング (その他については代数構造を参照) をプログラミングで使用して、より抽象化し、コードを再利用し、数学に似たプログラミングを実現できますか?

私が知っているように、Fortressという名前の言語(コンパイラが完成したら、どの言語よりも間違いなく好むでしょう) は、ライブラリ コードでこれらの構造を定義します。しかし、これまで見てきた使用法は、すでに慣れ親しんでいる数値型に対するものだけでした。それらの他の用途はありますか？

敬具、ciun

{2,1,1,0}与えられたグループの下で同等ではないそのリストのすべての順列をリストしたいような整数のリストが与えられました。たとえば、正方形の対称性を使用すると、結果はになります{{2, 1, 1, 0}, {2, 1, 0, 1}}。

以下のアプローチ（Mathematica 8）はすべての順列を生成し、次に同等のものを取り除きます。すべての順列を生成する余裕がないため、使用できません。より効率的な方法はありますか？

更新：実際には、ボトルネックはにありDeleteCasesます。次のリスト{2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 0, 0, 0}には約100万の順列があり、計算に0.1秒かかります。どうやら対称性を取り除いた後、1292の注文があるはずですが、私のアプローチは10分で終了しません

hammarの助けを借りて、コンパイルするHaskellビットのテンプレートを作成しました

に

私は今、この方法では解決できないと思う問題に直面しています。

多項式についての注目すべき事実は、それらがいくつかの素数を法として既約である場合、それらは有理数で既約であるということですp。私はすでに、ブルートフォースが与えられた（有限）体上で多項式を因数分解しようとする方法を持っています。

この関数を複数のフィールドで実行してみたいと思います。これが私が欲しいものの一種です：

基本的に、「除算」の多数の定義に対して素因数分解アルゴリズムを実行してみたいと思います。

これはTHでも可能だと思いますが、永遠にかかるようです。算術演算をパラメータとして渡す方が簡単かどうか疑問に思っていますisIrreducibleか？

あるいは、これはNewtypeモジュールが役立つ可能性があるように思われますが、同じように難しい方法でTHを使用しないとどのように機能するかを考えることはできません...

誰かがこれを達成するための最善の方法について何か考えがありますか？

抽象代数では、グループの概念はかなり基本的です。グループを取得するには、オブジェクトのセットと、3つのプロパティ（クロージャーを数える場合は4）を持つ2項演算が必要です。有限集合が与えられたグループをランダムに生成したい場合（つまり、集合内の要素のすべての可能な組み合わせの結果を与えるテーブルをランダムに生成したい場合）、単位元をハックし、逆元をハックするのは非常に簡単です。 、しかし、連想的である操作をランダムに生成することは非常に難しいようです。

私の質問は、結合法則をランダムに生成するための（効率的な）方法があるかどうかです。ランダムに操作を生成してから、非結合関係を摂動させて、一度に1つずつ結合するようにしましたが、これは実際には収束していないようです。何か案は？

GAP を使用して、乗算表からグループの名前を特定するにはどうすればよいですか? 一連のジェネレーターからグループを定義し、一連の内部テーブルでグループを探すことができることを知っています。

しかし、どうやってグループの名前を見つけます[120, 34]か?

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

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

たとえば、Haskellでは、加算が次のような整数のモノイドであることを簡単に定義できます。

ここで、0から999の合計を計算する場合は、次のように順番に計算できます。

または並行して行うことができます

しかし、このモノイドを並列化することは、mappendが一定時間で実行されるためにのみ意味があります。そうでない場合はどうなりますか？たとえば、リストは、mappendが一定の時間（またはスペース！）で実行されないモノイドです。これがHaskellにデフォルトの並列mconcat関数がない理由だと思います。最適な実装は、モノイドの複雑さに依存します。

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

algebra/2.1.1.2/doc/htmlのドキュメントには、膨大な数の型クラスが示されています。

問題の構造に可換結合操作と単位/単位要素が必要であるが、他に何も (逆数、分配性など) がないと宣言するにはどうすればよいですか?

考えている

しかし、Data.Monoid のインスタンスは交換可能であるとは想定されていません。関数のユーザーには、型を見て、関数が機能するために交換可能性が必要であることを理解してもらいたいと思います。

群はモノイドの考え方を拡張して逆を可能にします。これにより、次のことが可能になります。

しかし、逆数がない自然数のような構造はどうでしょうか? 私は考えています：

法律で：

さらに:

だから、私の質問は次のとおりMRemoveです。