計算機科学におけるモノイド
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2019/09/09 09:54 UTC 版)
「モノイド」の記事における「計算機科学におけるモノイド」の解説
「高階関数」も参照 計算機科学において、多くの抽象データ型はモノイド構造を持つ。よくあるパターンとして、モノイド構造を持つデータ型の元の列を考えよう。この列に対して「重畳」(fold) あるいは「堆積」(accumulate) の操作を施すことで、列が含む元の総和のような値が取り出される。例えば、多くの反復アルゴリズムは各反復段階である種の「累計」を更新していく必要があるが、モノイド演算の重畳を使うとこの累計をすっきりと表記できる。別の例として、モノイド演算の結合性は、多コアや多CPUを効果的に利用するために、prefix sumあるいは同様のアルゴリズムによって、計算を並列化できることを保証する。 単位元 ε と演算 • を持つモノイド M に対して、その列の型 M* から M への重畳関数 fold は次のように定義される。 fold : M ∗ → M {\displaystyle \operatorname {fold} \colon M^{*}\to M} fold l = { ε if l = nil m ∙ fold l ′ if l = cons m l ′ {\displaystyle \operatorname {fold} \,l={\begin{cases}\varepsilon &{\text{if }}l=\operatorname {nil} \\m\bullet \operatorname {fold} \,l'&{\text{if }}l=\operatorname {cons} \,m\,l'\end{cases}}} 更に、任意のデータ型でもその元の直列化演算(serialization)が与えられれば同様に「重畳」することができる。例えば、二分木においては木の走査が直列化にあたるが、結果は走査が行きがけか帰りがけかによって異なる。 単純な構造化プログラミング言語自身は文やブロックの連接を演算としてモノイドをなす。
※この「計算機科学におけるモノイド」の解説は、「モノイド」の解説の一部です。
「計算機科学におけるモノイド」を含む「モノイド」の記事については、「モノイド」の概要を参照ください。
- 計算機科学におけるモノイドのページへのリンク
