28

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

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

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

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

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

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

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

4

4 に答える 4

6

商モノイドは、モノイド（準モノイド？）を形成する別の方法です。モノイドMと、乗算と互換性のある同値関係が与えられると、別のモノイドが得られます。例えば：

  • 結合を持つ有限多重集合：A *が自由モノイド（連結のリスト）である場合、〜は「の順列」関係であり、A * /〜は自由可換モノイドです。

  • 和集合のある有限集合：要素の数を無視するように〜が変更された場合（つまり「aa」〜「a」）、A * /〜は自由な可換べき等モノイドです。

  • 構文モノイド：正規言語は、「言語による識別不能性」の関係によってA*の商である構文モノイドを生成します。これがこのアイデアのフィンガーツリー実装です。たとえば、言語{a 3n：n natural}には、構文モノイドとしてZ3があります。

商モノイドは、全射である準同型M-> M /〜を自動的に伴います。

「デュアル」構造はサブモノイドです。それらは、単射である準同型A->Mを備えています。

モノイドのさらに別の構造はテンソル積です。

モノイドは、O（log n）で二乗し、高速並列プレフィックス合計計算によって指数化を可能にします。また、それらはWriterモナドで使用されます。

于 2010-03-20T23:01:40.817 に答える
5

Haskell 標準ライブラリは、その型クラスに実際の数学用語を使用しているため、賞賛と攻撃を交互に受けます。(私の意見では、これは良いことです。なぜなら、それがなければ、モノイドが何であるかさえわからないからです!)。いずれにせよ、さらにいくつかの例については、http://www.haskell.org/ghc/docs/latest/html/libraries/base/Data-Monoid.htmlを参照してください。

  • 任意のモノイドの双対はモノイドです: a+b が与えられた場合、a++b = b+a で新しい演算 ++ を定義します。
  • ブール値の結合と分離
  • Maybe モナド (別名 Ocaml では「オプション」) の最初と最後。あれは、
    まず (Just a) b = Just a
最初 なし b = b
    同様に最後の

後者は、モナドとアローに関連するモノイドのファミリー全体の氷山の一角にすぎませんが、これらについて頭を悩ませることはできません (単純なモナド自己準同形を除いて)。しかし、グーグルで検索するmonads monoidsとかなり出てきます。

于 2010-03-20T20:04:12.090 に答える
1

可換モノイドの非常に便利な例は、論理言語と制約言語の統合です。可能な統一アルゴリズムの正確な定義については、「コンピュータ プログラミングの概念、技法、およびモデル」のセクション 2.8.2.2 を参照してください。

あなたの言語で頑張ってください！モノイドを使用して並列計算からのサブ結果をマージして、並列言語で同様のことを行っています。

于 2012-05-28T14:32:15.660 に答える
0

任意の長さのローマ数字値の計算。 https://gist.github.com/4542999

于 2013-01-16T17:07:38.567 に答える