Luna Flow
简体中文

immut 教程

本教程是把多项式作为值来使用的入门。它展示一次导入即可获得所有不可变表示，帮助你选择合适的表示，并在表示之间转换多项式。每种表示都有自己的教程介绍细节。

快速开始

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 本身不变，这一层中每个操作之后都是如此。

日常任务

选择一种表示

你有使用教程
单变量，大多数系数非零DensePolynomialimmut/dense
多变量，按顺序处理项TermPolynomialimmut/term
多变量，查找系数SparsePolynomialimmut/sparse
具名变量，按名字求值或代换ContextPolynomialimmut/context

四者都共享运算符 +、-、*、一元 - 以及方法 pow。

同一多项式，三种表示

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")
}

深入了解

泛型代码只写一次

门面包重新导出了能力 trait 和 luna-generic 代数 trait，因此两类约束都只需要这一个导入：

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)。
  • 两个 core 包。 如果你还导入了 Luna-Flow/type_theory/core，请为其起别名（例如 @tt_core）；门面包本身不需要 luna-poly/core。
  • 重建代价。 不可变更新会重建其结果；对于长时间的增量构建，请使用可变层。

后续步骤