immut/term API

Luna-Flow/luna-poly/immut/term 提供 TermPolynomial[A]，一种以 (ExponentVector, A) 项数组存储的不可变多元多项式。该数组是规范的：按单项式序降序排列，没有两个项共享同一指数向量，也没有零系数。

该类型由 immut 门面包重新导出为 @immut.TermPolynomial，示例中使用的就是它。变量按下标寻址：变量 $i$ 是指数向量的第 $i$ 个位置。如需具名变量，请使用 ContextPolynomial。设计说明见 immut/term 设计。

类型

`TermPolynomial`

TermPolynomial[A] 用项 $(\alpha_k, c_k)$ 表示 $\sum_k c_k x^{\alpha_k}$ ，其中 $\alpha_1 \succ \alpha_2 \succ \cdots$ 且每个 $c_k \neq 0$ 。

type TermPolynomial[A] derive(Eq, @debug.Debug)
pub impl[A] @luna-generic.Zero for TermPolynomial[A]
pub impl[A : Eq + @luna-generic.Zero + @luna-generic.One] @luna-generic.One for TermPolynomial[A]
pub impl[A : Eq + @luna-generic.AddMonoid] Add for TermPolynomial[A]
pub impl[A : Eq + @luna-generic.AddMonoid + Neg] Sub for TermPolynomial[A]
pub impl[A : Eq + @luna-generic.AddMonoid + Mul] Mul for TermPolynomial[A]
pub impl[A : Eq + @luna-generic.Zero + Neg] Neg for TermPolynomial[A]
pub impl[A : Show + @luna-generic.Zero] Show for TermPolynomial[A]
pub impl[A : Eq + @luna-generic.AddMonoid + Mul + @luna-generic.One] @arithmetic.PowNatChecked for TermPolynomial[A]
pub impl[A] @core.HasArity for TermPolynomial[A]
pub impl[A] @core.HasShape for TermPolynomial[A]
pub impl[A] @core.HasTermCount for TermPolynomial[A]
pub impl[A] @core.HasTotalDegree for TermPolynomial[A]
pub impl[A] @core.IsZero for TermPolynomial[A]
pub impl[A] @core.MultivariatePolynomial for TermPolynomial[A]

构造

`TermPolynomial::from_terms`

由一组项构建规范多项式：对它们排序，将指数向量相同的项的系数相加，并丢弃和为零的项。输入会被复制。对 $m$ 个输入项，代价为 $O(m \log m)$ 次比较。

pub fn[A : Eq + @luna-generic.AddMonoid] TermPolynomial::from_terms(Array[(@core.ExponentVector, A)]) -> Self[A]

`TermPolynomial::from_array`

与 from_terms 相同，但每个指数向量以 Array[UInt] 给出（用 ExponentVector::from_array 转换）。

pub fn[A : Eq + @luna-generic.AddMonoid] TermPolynomial::from_array(Array[(Array[UInt], A)]) -> Self[A]

`TermPolynomial::zero`, `TermPolynomial::one`

空多项式与常数 $1$ （若在 A 中 $1 = 0$ ，则为零多项式），也可写作 Zero::zero() 和 One::one()。

pub fn[A] TermPolynomial::zero() -> Self[A]
pub fn[A : Eq + @luna-generic.Zero + @luna-generic.One] TermPolynomial::one() -> Self[A]

test "construction" {
  let p = @immut.TermPolynomial::from_array([
    ([0U, 1], 3),
    ([2U], 1),
    ([1U, 0], 2),
    ([1U], -2),
    ([], 4),
  ])
  inspect(p, content="1 * x^2 + 3 * x_1 + 4")
  inspect(p.size(), content="3")
}

[1, 0] 和 [1] 是同一个单项式，因此 $2x_0 - 2x_0$ 相消。

查询

`TermPolynomial::to_terms`

返回规范项的新数组，首项在前。

pub fn[A] TermPolynomial::to_terms(Self[A]) -> Array[(@core.ExponentVector, A)]

`TermPolynomial::coefficients`

按 to_terms 的顺序返回系数。

pub fn[A] TermPolynomial::coefficients(Self[A]) -> Array[A]

`TermPolynomial::size`, `TermPolynomial::term_count`

两者都返回非零项的个数。

pub fn[A] TermPolynomial::size(Self[A]) -> Int
pub fn[A] TermPolynomial::term_count(Self[A]) -> Int

`TermPolynomial::is_zero`

没有项时返回 true。

pub fn[A] TermPolynomial::is_zero(Self[A]) -> Bool

`TermPolynomial::arity`

返回使用中的变量个数：最长的规范指数向量的长度，常数和零为 0。

pub fn[A] TermPolynomial::arity(Self[A]) -> Int

`TermPolynomial::total_degree`

返回项的最大全次数；零多项式返回 None。

pub fn[A] TermPolynomial::total_degree(Self[A]) -> UInt?

`TermPolynomial::shape`

返回 PolynomialShape::Multivariate(arity~, term_count~)。

pub fn[A] TermPolynomial::shape(Self[A]) -> @core.PolynomialShape

test "queries" {
  let p = @immut.TermPolynomial::from_array([([1U, 2], 5), ([0U, 0, 1], 1), ([], 7)])
  inspect(p.arity(), content="3")
  debug_inspect(p.total_degree(), content="Some(3)")
  debug_inspect(p.coefficients(), content="[5, 1, 7]")
  inspect(p.to_terms()[0].0, content="xx_1^2")
}

算术

`TermPolynomial::add`, `TermPolynomial::sub`, `TermPolynomial::neg`

加法、减法与取负，即运算符 +、- 和一元 -。加法拼接项并重新规范化， $O((m + n) \log(m + n))$ ；取负保持顺序， $O(m)$ 。

pub fn[A : Eq + @luna-generic.AddMonoid] TermPolynomial::add(Self[A], Self[A]) -> Self[A]
pub fn[A : Eq + @luna-generic.AddMonoid + Neg] TermPolynomial::sub(Self[A], Self[A]) -> Self[A]
pub fn[A : Eq + @luna-generic.Zero + Neg] TermPolynomial::neg(Self[A]) -> Self[A]

`TermPolynomial::mul`

将一个操作数的每一项与另一个操作数的每一项相乘并重新规范化，即运算符 *。对 $m$ 项和 $n$ 项，代价为 $O(mn \log(mn))$ 。

pub fn[A : Eq + @luna-generic.AddMonoid + Mul] TermPolynomial::mul(Self[A], Self[A]) -> Self[A]

`TermPolynomial::scale`

对指数向量 $\gamma$ 和系数 $c$ 返回 $c\,x^\gamma \cdot p$ 。乘积为零的项被丢弃。结果无需重新排序即保持有序，因此代价为 $O(m)$ 次项运算。

pub fn[A : Eq + @luna-generic.Zero + Mul] TermPolynomial::scale(Self[A], @core.ExponentVector, A) -> Self[A]

`TermPolynomial::pow`

通过二进制幂算法返回 $p^e$ ；pow(0) 为 one()。也可通过 @arithmetic.PowNatChecked 使用。

pub fn[A : Eq + @luna-generic.AddMonoid + Mul + @luna-generic.One] TermPolynomial::pow(Self[A], UInt) -> Self[A]

test "arithmetic" {
  let x = @immut.TermPolynomial::from_array([([1U], 1)])
  let y = @immut.TermPolynomial::from_array([([0U, 1], 1)])
  inspect((x + y).pow(2), content="1 * x_1^2 + 2 * xx_1 + 1 * x^2")
  inspect((x + y) * (x - y), content="-1 * x_1^2 + 1 * x^2")
  let xy = @immut.ExponentVector::from_array([1U, 1])
  inspect((x + y).scale(xy, 3), content="3 * xx_1^2 + 3 * x^2x_1")
}

求值

`TermPolynomial::eval`

在点 values 处求值，其中 values[i] 是变量 $i$ 的值。每一项按 $c \prod_i a_i^{\alpha_i}$ 用二分幂求值。当 values 短于 arity() 时中止（abort）；多余的值被忽略。

pub fn[A : @luna-generic.AddMonoid + Mul + @luna-generic.One] TermPolynomial::eval(Self[A], Array[A]) -> A

`TermPolynomial::eval_checked`

与 eval 相同，但当 values.length() < arity() 时返回 None。

pub fn[A : @luna-generic.AddMonoid + Mul + @luna-generic.One] TermPolynomial::eval_checked(Self[A], Array[A]) -> A?

test "evaluation" {
  let p = @immut.TermPolynomial::from_array([([2U], 1), ([1U, 1], 3), ([], 4)])
  inspect(p.eval([2, 5]), content="38")
  assert_true(p.eval_checked([2]) is None)
  inspect(p.eval([2, 5, 100]), content="38")
}

比较与打印

`TermPolynomial::equal`

规范项数组的结构相等，即多项式相等。它就是 ==。没有 Compare 实例。

pub fn[A : Eq] TermPolynomial::equal(Self[A], Self[A]) -> Bool

`TermPolynomial::to_string`

按存储顺序以 c * monomial 的形式渲染各项（常数项仅为 c），以 + 连接；零打印为系数零。单项式使用 ExponentVector 的记法。

pub fn[A : Show + @luna-generic.Zero] TermPolynomial::to_string(Self[A]) -> String

泛型访问

`TermPolynomial::ops`

返回该类型的 MultivariateOps 记录；eval_indexed 即 eval。

pub fn[A : Eq + @luna-generic.AddMonoid + Mul + @luna-generic.One] TermPolynomial::ops() -> @core.MultivariateOps[Self[A], A]

test "ops" {
  let ops = @immut.TermPolynomial::ops()
  let p = ops.from_terms([(@immut.ExponentVector::from_array([1U]), 2)])
  inspect(ops.eval_indexed(ops.pow(p, 3), [1]), content="8")
}

转换为稀疏存储

没有直接的转换方法；需经由项列表，这会重新进行规范化：

test "conversion" {
  let t = @immut.TermPolynomial::from_array([([1U], 2), ([], 1)])
  let s = @immut.SparsePolynomial::from_terms(t.to_terms())
  let back = @immut.TermPolynomial::from_terms(s.to_terms())
  assert_true(back == t)
}

已弃用

为源码兼容而保留的隐藏方法形式：

已弃用	替代方案
`p.not_equal(q)`	`p != q`
`p.output(logger)`	`to_string` 或字符串插值
`p.to_repr()`	`Repr(p)` 或 `debug_inspect`
`p.pow_nat_checked(e, ctx)`	`@arithmetic.PowNatChecked::pow_nat_checked(p, e, ctx)` 或 `p.pow(e)`

immut/term API

类型

TermPolynomial

构造

TermPolynomial::from_terms

TermPolynomial::from_array

TermPolynomial::zero, TermPolynomial::one

查询

TermPolynomial::to_terms

TermPolynomial::coefficients

TermPolynomial::size, TermPolynomial::term_count

TermPolynomial::is_zero

TermPolynomial::arity

TermPolynomial::total_degree

TermPolynomial::shape

算术

TermPolynomial::add, TermPolynomial::sub, TermPolynomial::neg

TermPolynomial::mul

TermPolynomial::scale

TermPolynomial::pow

求值

TermPolynomial::eval

TermPolynomial::eval_checked