自由モノイドのイテレーター(1) - 非専門的シンギュラリティー研究所

自由モノイドのイテレーター

クロージャーの調査が保留となっていたので再開したいのですが、まずは前回の続きでイテレーターについて調査していきたいと思います。

有限の場合

$M = C^*$ を $C$ で生成された自由モノイドとします。演算子を $*$ とします。 $C$ の元を文字、 $M$ の元を文字列とみなすことができます。 $s = c_1 * c_2 * \cdots * c_n$ ( $c_i \in C$ )のとき $s[i] = c_i$ とします(そのほか前回と同様配列のような記法を使います)。

$f$ をある集合 $X$ から $M$ への「形式的写像」とします。 $X = X_1 + X_2 + \cdots + X_n$ として $x \in X_i$ のとき $f(x) = g_{i1}(x) * g_{i2}(x) * \cdots * g_{im_n}(x)$ と定義されたもので、 $g_{ij}(x)$ は「式」で $f$ を含んでいても良い(含まなくても複数含んでいても良い)とします。 $f$ は前回述べたように $M$ への部分写像となります。

無限の場合

この無限の場合を考えます。

$x \in X_i$ のとき $f_\mathrm{iter}(x) = (\mapsto g'_{i1}(x)) * (\mapsto g'_{i2}(x)) * \cdots * (\mapsto g'_{im_n}(x))$ と定義します。ここで $g'_{ij}(x)$ は $g_{ij}(x)$ の $f$ を $f_\mathrm{iter}$ で置き換えたものとします。 $(\mapsto e)$ は「クロージャー」のようなものを表します。

$e$ に現れる変数(「式」の中で「形式的写像」を定義できるとし、その「引数」)を $v_1, \cdots, v_n$ とするとき、それらをまとめた $x = \langle v_1, \cdots, v_n \rangle$ に対して、 $(\mapsto e)$ は「クラスのインスタンス」のような形で $r = \langle \mathrm{data} = x, \ \mathrm{method} = (x \mapsto e) \rangle$ という組とします。 $(x \mapsto e)$ は「ラムダ式」のようなものとします。 $r$ を「評価」する $r()$ は $r() = r.\mathrm{method}(r.\mathrm{data})$ とします。このような「インスタンス」の全体を $R$ とおきます。詳細な定義は後ですることにします。

イテレーターのようなものの定義

$s \in (C + R)^*$ のとき $s^> \in (C + R)^*$ を

$s \in C * (C + R)^*$ のとき $s = c * u$ とすると $s^> = s$ $(c \in C, \ u \in (C + R)^*)$
$s \in R * (C + R)^*$ のとき $s = r * u$ とすると $s^> = r() * u$ $(c \in C, \ u \in (C + R)^*)$

と定義します。

これを $k$ 回繰り返したものを $s^{>k}$ とします。すなわち $s^{>k}$ を

$s^{>0} = s$
$k \ge 0$ のとき $s^{>(k+1)} = (s^{>k})^>$

と帰納的に定義します。

$s^\gg$ を

$s^{>j} \in C * (C + R)^*$ となる $j$ が存在するとき $s^\gg = \langle \mathrm{cur} = s^{>j} [1], \ \mathrm{next} = s^{>j} [2 \cdots] \rangle$ という組とします。
そのような $j$ が存在しないとき $s^\gg = \bot$ とします。

これを $k$ 回繰り返したものを $s^{\gg k}$ とします。ただし途中で $\bot$ となったときは $s^{\gg k} = \bot$ とします。すなわち $s^{\gg k}$ を

$s^{\gg 1} = s^\gg$
のとき
- $s^{\gg k} \ne \bot$ かつ $(s^{\gg k})^\gg \ne \bot$ のとき $s^{\gg (k+1)} = (s^{\gg k})^\gg.\mathrm{next}$
- $s^{\gg k} = \bot$ または $(s^{\gg k})^\gg = \bot$ のとき $s^{\gg (k+1)} = \bot$