Luna Flow
日本語

immut チュートリアル

このチュートリアルは、多項式を値として使うための入口です。すべてのイミュータブル表現を利用できる 1 つのインポートを示し、適切な表現の選び方を説明し、表現の間で多項式を移す方法を紹介します。詳細は各表現のチュートリアルにあります。

クイックスタート

moon add Luna-Flow/luna-poly@0.2.0
import {
  "Luna-Flow/luna-poly/immut",
}
test "immut quick start" {
  let p = @immut.DensePolynomial::from_coefficients([1, 2, 3])
  let q = p.pow(2)
  inspect(q, content="1 + 4x^1 + 10x^2 + 12x^3 + 9x^4")
  inspect(q.eval(2), content="289")
  inspect(p, content="1 + 2x^1 + 3x^2")
}

p.pow(2) は新しい多項式を返します。この層のすべての演算の後と同様に、p 自体は変わりません。

日常的なタスク

表現を選ぶ

状況使う型チュートリアル
変数が 1 つで、係数の大半が非ゼロDensePolynomialimmut/dense
変数が複数で、項を順に処理するTermPolynomialimmut/term
変数が複数で、係数を検索するSparsePolynomialimmut/sparse
名前付き変数で、名前による評価や代入を行うContextPolynomialimmut/context

4 つすべてが演算子 +、-、*、単項 - とメソッド pow を共有しています。

同じ多項式を 3 つの表現で

test "three representations" {
  let dense = @immut.DensePolynomial::from_coefficients([1, 2, 1])
  let term = @immut.TermPolynomial::from_array([([2U], 1), ([1U], 2), ([], 1)])
  let sparse = @immut.SparsePolynomial::from_terms(term.to_terms())
  inspect(dense.eval(3), content="16")
  inspect(term.eval([3]), content="16")
  inspect(sparse.eval([3]), content="16")
}

x2+2x+1x^2 + 2x + 1 の x=3x = 3 における値は、どの表現でも 1616 です。

表現の間を移動する

多変数の表現は項のリストを介して変換します。コンテキスト多項式はコンテキストを束縛または解放します。

test "conversions" {
  let ctx = @immut.VariableContext::from_names(["x", "y"])
  let term = @immut.TermPolynomial::from_array([([1U, 1], 2), ([], 1)])
  let sparse = @immut.SparsePolynomial::from_terms(term.to_terms())
  let named = @immut.ContextPolynomial::from_sparse_polynomial(ctx, sparse)
  inspect(named, content="1 + 2 * x * y")
  let back = named.to_term_polynomial()
  assert_true(back == term)
}

値のセマンティクスに頼る

古いバージョンは自由に取っておけます。たとえば前後の比較に使えます。

test "history" {
  let history = [@immut.DensePolynomial::from_coefficients([0, 1])]
  for _ in 0..<3 {
    let last = history[history.length() - 1]
    history.push(last * last + @immut.DensePolynomial::constant(1))
  }
  inspect(history.map(p => p.length()).map(n => n.to_string()).join(" "), content="2 3 5 9")
  inspect(history[1], content="1 + 1x^2")
}

さらに進む

ジェネリックコードを一度だけ書く

ファサードは能力トレイトと luna-generic の代数トレイトを再エクスポートしているので、どちらの種類の制約もこのインポートだけで書けます。

fn[P : @immut.MultivariatePolynomial] degree_or_minus_one(p : P) -> Int {
  match @immut.HasTotalDegree::total_degree(p) {
    Some(d) => d.reinterpret_as_int()
    None => -1
  }
}

fn[A : @immut.Ring + Eq] square_minus_one(p : @immut.DensePolynomial[A]) -> @immut.DensePolynomial[A] {
  p * p - @immut.DensePolynomial::one()
}

test "generic" {
  inspect(degree_or_minus_one(@immut.TermPolynomial::from_array([([1U, 2], 1)])), content="3")
  inspect(degree_or_minus_one(@immut.SparsePolynomial::from_array([([1U], 0)])), content="-1")
  inspect(square_minus_one(@immut.DensePolynomial::from_coefficients([1, 1])), content="2x^1 + 1x^2")
}

値をミュータブル層に渡す

ホットループでインプレースの更新が必要なときは、境界で変換し、また変換して戻します。

test "to mutable and back" {
  let p = @immut.DensePolynomial::from_coefficients([1, 1])
  let buffer = @mutable.DensePolynomial::from_immut(p)
  for _ in 0..<3 {
    buffer.mul_inplace(@mutable.DensePolynomial::from_immut(p))
  }
  inspect(buffer.to_immut(), content="1 + 4x^1 + 6x^2 + 4x^3 + 1x^4")
  inspect(p, content="1 + 1x^1")
}

よくある落とし穴

  • 型が異なれば、同じ多項式でも別物。 DensePolynomial と TermPolynomial は互いに加算できません。まず変換してください。
  • 代入のコンストラクタ。 @immut.Polynomial(p) は存在しません。代入リストの中では Polynomial(p) と書くか、@immut.ContextSubstitutionValue::Polynomial(p) と書いてください。
  • 2 つの core パッケージ。 Luna-Flow/type_theory/core もインポートする場合は別名を付けてください（たとえば @tt_core）。ファサード自体は luna-poly/core を必要としません。
  • 再構築のコスト。 イミュータブルな更新は結果を再構築します。長い逐次的な構築にはミュータブル層を使ってください。

次のステップ