mutable/dense の設計

設計目標

ミュータブルな DensePolynomial[A] を使うと、アルゴリズムはステップごとに新しい値を確保することなく、一変数多項式をその場で構築・更新できます（係数を 1 つずつ設定する、和を累積する、累積中の積に掛け込むなど）。しかも数学的な結果は immut/dense とまったく同じです。

数学的背景

表現する対象はイミュータブルなパッケージと同じで、切り詰めた係数語として格納された多項式 $f = \sum_i c_i x^i \in R[x]$ です（immut/dense の設計を参照）。ミュータブルなコンテナは、そのような値を保持する変数です。インプレース演算 $\mathtt{op\_inplace}(p, q)$ は代入 $p \leftarrow p \circ q$ であり、コンテナが新しい値の正規形の語を保持した状態で終わらなければなりません。

設計上の判断

同じ正規形を、変更のたびに復元する

不変条件。 公開呼び出しの合間には、格納された配列がゼロの係数で終わることはありません。

変更を伴う各メソッドがこれを再確立します。set_coefficient(k, c) は $k \ge n$ のとき配列をゼロで伸長し、 $c$ を書き込んでから切り詰めます。最上位に $c = 0$ を書き込んだ場合、次数は次の非ゼロ係数まで下がります。add_inplace は既存の配列に加算して切り詰めます。打ち消し合いで次数が下がりうるからです。mul_inplace と scale_inplace は新たに計算した正規形の配列を代入します。不変条件が成り立つので、degree、length、==、compare はイミュータブルな型の場合とまったく同じ意味を持ちます。

変更は明示的かつ限定的

レシーバを変更するのは set_coefficient、clear、add_inplace、mul_inplace、scale_inplace だけです。演算子 +、-、*、単項 - とその他すべてのメソッドは新しい値を返します。a + b は a をコピーし、そのコピーに b を加えます。したがって p * q と書かれたコードに隠れた副作用はなく、変更は呼び出し箇所で名前によって見てとれます。

エイリアスは安全

レシーバを引数として渡すことは許されます。p.add_inplace(p) では、ループはインデックスごとに $c_i \leftarrow c_i + c_i$ を計算します。ステップ $i$ では両オペランドがインデックス $i$ を書き込み前に読み、後のステップはそれより後のインデックスしか読まないので、結果は $2p$ になります。mul_inplace と scale_inplace は結果全体を計算してから代入するので、 $p \leftarrow p \cdot p$ は $p$ を正しく二乗します。

イミュータブルな実装への委譲

自明でないアルゴリズムを重複させることになる演算（scale、pow、karatsuba、substitute、derivative、monomial_checked）は、イミュータブルな型に変換してそれを呼び出し、変換し直します。各変換は係数をコピーし $O(n)$ かかりますが、これはアルゴリズム本体のコストに比べて小さいものです。したがって、これらの演算で 2 つの層が食い違うことはありません。短い処理である加算、筆算式の乗算、Horner 法による評価は配列上に直接実装しており、consistency テストでイミュータブル版との一致を確認しています。

変換はコピーする

from_immut はイミュータブルな係数を新しい配列にコピーし、to_immut はコピーからイミュータブルな値を構築します。to_immut で取ったスナップショットは、その後ミュータブルな多項式をどう変更しても変わらず、from_immut に渡したイミュータブルな値が後の変更の影響を受けることもありません。copy（Copyable 能力）は配列を複製するので、コピーと元のものは独立に変化します。

イミュータブルな型とのコスト比較

演算	`immut/dense`	`mutable/dense`
係数を 1 つ設定	`from_coefficients` で再構築、 $O(n)$	`set_coefficient`、 $O(n)$ （切り詰めでコピーが発生）
$p \leftarrow p + q$	新しい値、 $O(n)$	`add_inplace`、 $O(n)$ 、配列を再利用
$p \leftarrow p \cdot q$	$O(mn)$	$O(mn)$ と 1 回の代入
`pow`, `substitute`, `karatsuba`	直接	同じコストに加えて $O(n)$ の変換

set_coefficient での切り詰めは配列をコピーするので、現在の実装では各呼び出しが $O(n)$ です。イミュータブルな型に対する節約は、ステップごとに新しい多項式値を作らずに済むことと、add_inplace が既存の格納上で動作することから得られます。

正しさ / 不変条件

すべての公開呼び出しの後に 正規形 であり、== は多項式としての等しさです。
immut との一致。 変更を伴わないすべての演算について from_immut(a).op(...).to_immut() == a.op(...) が成り立ち、インプレース演算はレシーバを対応する演算子の結果に等しい状態にします。
分離。 copy、to_immut、from_immut、to_coefficients がレシーバと格納を共有することはありません。
エイリアス。 p.add_inplace(p)、p.mul_inplace(p) は $2p$ と $p^2$ を計算します。
中断。 set_coefficient、scale_inplace、scale、coefficient、monomial は、イミュータブル版と同様に負の累乗に対して中断します。

採用しなかった代替案

変更を伴う演算子。 + や * が左オペランドを更新するようにすればループ内では安価になりますが、すべての算術式が副作用を持ちうるものになってしまいます。
イミュータブルなスナップショットとの配列の共有。 コピーオンライトにすれば to_immut は $O(1)$ になりますが、MoonBit の配列が提供しない参照の追跡が必要になります。
独立したアルゴリズム群。 ミュータブルな型のために Karatsuba や合成を再実装すると、一貫性を保たなければならないコードが倍になります。

境界

set_coefficient_checked はありません。累乗の指数は自分で検証するか、イミュータブルな scale_checked / monomial_checked を使ってください。
別の計算が to_coefficients() の結果を走査している間に多項式を変更しても安全なのは、その結果がコピーだからにすぎません。
プログラムの 2 つの部分で共有されたミュータブルなコンテナは、両方に対して更新されます。それが意図したものでない場合は、各部分に専用の copy() を渡してください。
immut/dense が行わないことは、このパッケージも行いません。