反復バイナリ演算

数学では、反復二項演算は、集合S上の二項演算を繰り返し適用することによって、 Sの要素の有限列上の関数に拡張したものです。 ^{[ 1 ]}一般的な例としては、加算演算を総和演算に拡張したものや、乗算演算を積演算に拡張したものなどがあります。集合論の演算である和集合や積集合などの他の演算も、しばしば反復されますが、反復には個別の名前は付けられません。印刷物では、総和と積は特別な記号で表されますが、他の反復演算子は、通常の二項演算子の記号のより大きな変形で表されることがよくあります。したがって、上記の 4 つの演算の反復は、次のように表されます。

${\displaystyle \sum ,\ \prod ,\ \bigcup ,}$そして${\displaystyle \bigcap }$、 それぞれ。

より一般的には、二項関数の反復は一般的にスラッシュで表されます。${\displaystyle f}$シーケンス全体にわたって${\displaystyle (a_{1},a_{2}\ldots ,a_{n})}$は、${\displaystyle f/(a_{1},a_{2}\ldots ,a_{n})}$バード・メーテンス形式における還元表記法に従って。

一般に、二項演算を有限シーケンスに拡張する方法は複数あり、それは演算子が結合法則を満たすかどうか、および演算子に単位元があるかどうかによって決まります。

_{j ≥} 0 かつk _≥ jであるような、 Sの要素からなる長さk − jの有限列をa j , kで表す。ただし、j ≤ i < kに対して、要素は ( a _i )である。k = jの場合、この列は空列であることに注意する。

f  : S × S → Sに対して、 Sの要素の有限非空列に対して新しい関数F _lを定義する。 $${\displaystyle F_{l}(\mathbf {a} _{0,k})={\begin{cases}a_{0},&k=1\\f(F_{l}(\mathbf {a} _{0,k-1}),a_{k-1}),&k>1.\end{cases}}}$$

同様に定義する $${\displaystyle F_{r}(\mathbf {a} _{0,k})={\begin{cases}a_{0},&k=1\\f(a_{0},F_{r}(\mathbf {a} _{1,k})),&k>1.\end{cases}}}$$

f が一意の左恒等式eを持つ場合、 F _lの定義は、空のシーケンスに対するF _lの値をeと定義することで、空のシーケンスに対しても動作するように変更できます（長さ 1 のシーケンスに関する以前の基本ケースは不要になります）。同様に、f が一意の右恒等式を持つ場合、 F _{r も}空のシーケンスに対しても動作するように変更できます。

fが結合法則を満たす場合、F _{l は}F _rと等しくなり、単にFと書くことができます。さらに、単位元e が存在する場合、それは一意です (モノイドを参照)。

fが可換かつ結合的である場合、F は任意の非空有限多重集合に対して、その多重集合の任意の列挙に適用することで作用することができます。さらに、 f が単位元eを持つ場合、これは空の多重集合に対するFの値として定義されます。f が冪等である場合、上記の定義は有限集合にも拡張できます。

S が距離空間、あるいはより一般的にはハウスドルフ位相を備えている場合、つまり数列の極限の概念がSで定義されている場合、S内の可算数列に対する無限反復は_{、対応する有限反復の列が}収束するときに正確に定義されます。したがって、例えば、a₀ , a₁ , a₂ , a₃ , …_が実数の無限数列である場合、無限積_は  ${\textstyle \prod _{i=0}^{\infty }a_{i}}$定義されており、${\textstyle \lim \limits _{n\to \infty }\prod _{i=0}^{n}a_{i},}$その制限が存在する場合に限り、かつその場合に限る。

一般的な非結合的な二項演算はマグマによって表される。非結合的な二項演算を反復する行為は、二分木として表現できる。

反復二項演算は次のように記述されます。

${\displaystyle \mathop {\bigstar } _{k=1}^{n}a_{k}}$

記号の意味：

例：

${\displaystyle \mathop {\bigstar } _{k=1}^{4}a_{k}=\mathop {\bigstar } _{k=1}^{k=4}a_{k}=a_{1}\star a_{2}\star a_{3}\star a_{4}}$

一般形式：

${\displaystyle \mathop {\bigstar } _{k\in K}a_{k}}$

制限付き形式:

${\displaystyle \mathop {\bigstar } _{1\leq k\leq n \atop k\equiv 0{\pmod {2}}}a_{k}}$

無限バージョン：

${\displaystyle \mathop {\bigstar } _{k=1}^{\infty }a_{k}=\mathop {\bigstar } _{k=1}^{k\to \infty }a_{k}}$

させて${\displaystyle (S,\star )}$結合演算を持つ構造である${\displaystyle \star }$:

• 単一要素:

${\displaystyle \mathop {\bigstar } _{k=n}^{n}a_{k}=a_{n}}$

• 拡大：

${\displaystyle \mathop {\bigstar } _{k=1}^{n}a_{k}=a_{1}\star a_{2}\star \dots \star a_{n}}$

• 再帰：

${\displaystyle \mathop {\bigstar } _{k=1}^{n}a_{k}=\left(\mathop {\bigstar } _{k=1}^{n-1}a_{k}\right)\star a_{n}}$

• 右再帰:

${\displaystyle \mathop {\bigstar } _{k=1}^{n}a_{k}=a_{1}\star \left(\mathop {\bigstar } _{k=2}^{n}a_{k}\right)}$

• 分割:

${\displaystyle \left(\mathop {\bigstar } _{k=1}^{m}a_{k}\right)\star \left(\mathop {\bigstar } _{k=m+1}^{n}a_{k}\right)=\mathop {\bigstar } _{k=1}^{n}a_{k}}$

• 順列不変性：

${\displaystyle \mathop {\bigstar } _{k=1}^{n}a_{k}=\mathop {\bigstar } _{k=1}^{n}a_{\sigma (k)}}$

• 空の積（モノイド）：

${\displaystyle \mathop {\bigstar } _{k=1}^{0}a_{k}=e}$

• 冪等性:

もし${\displaystyle a\star a=a}$、 それから${\displaystyle \mathop {\bigstar } _{k=1}^{n}a=a}$

• 定数配列:

${\displaystyle \mathop {\bigstar } _{k=1}^{n}a=a\star \cdots \star a}$

もし${\displaystyle (S,\star ,e)}$がモノイドである場合、次のようになります。

• 空積＝単位元
• 空和 = 0 (算術モノイドの場合)

関数型プログラミングでは、反復二項演算は、 foldやreduceなどの高階関数に対応します。

• 単項演算
• 単項関数
• 二項演算
• 二値関数
• 三値演算

• 一括処理
• 並列プレフィックス操作2013年6月3日にWayback Machineにアーカイブされました
• Nuprl の反復バイナリ演算(2016 年 3 月 3 日、 Wayback Machineにアーカイブ)