Luna Flow
简体中文

immut/term 教程

本教程介绍如何把多元多项式当作有序项列表来使用：构建它们、按顺序读取各项、进行算术运算、在某点求值，以及编写遍历各项的小型算法。

快速开始

moon add Luna-Flow/luna-poly@0.2.0
import {
  "Luna-Flow/luna-poly/immut",
}
test "term quick start" {
  let p = @immut.TermPolynomial::from_array([([2U], 1), ([1U, 1], 3), ([], 4)])
  inspect(p, content="3 * xx_1 + 1 * x^2 + 4")
  inspect(p.eval([2, 5]), content="38")
}

每一项是 (exponents, coefficient)：[1, 1] 是 x0x1x_0 x_1，因此 p 是 x02+3x0x1+4x_0^2 + 3x_0x_1 + 4，且 p(2,5)=4+30+4=38p(2, 5) = 4 + 30 + 4 = 38。变量 x0x_0 打印为 x，xix_i 打印为 x_i。

日常任务

从项构建

可以以任意顺序、带重复地给出各项；构造函数会排序、合并并丢弃零：

test "building" {
  let p = @immut.TermPolynomial::from_array([
    ([1U], 2),
    ([0U, 1], 5),
    ([1U, 0, 0], 3),
    ([0U, 1], -5),
  ])
  inspect(p, content="5 * x")
  let v = @immut.ExponentVector::from_array([0U, 0, 2])
  let q = @immut.TermPolynomial::from_terms([(v, 1), (@immut.ExponentVector::one(), -1)])
  inspect(q, content="1 * x_2^2 + -1")
}

from_terms 接受现成的 ExponentVector 键；from_array 会替你构建它们。

按顺序读取各项

各项按分次序输出，首项在前：

test "reading terms" {
  let p = @immut.TermPolynomial::from_array([([], 1), ([1U], 1), ([0U, 1], 1), ([2U], 1)])
  let (lead, coeff) = p.to_terms()[0]
  inspect(lead, content="x^2")
  inspect(coeff, content="1")
  inspect(p.to_terms().map(t => t.0.to_string()).join(", "), content="x^2, x_1, x, 1")
  inspect(p.size(), content="4")
  debug_inspect(p.total_degree(), content="Some(2)")
}

总次数较高的在前；同一次数内，下标较大的变量优先，因此 x1x_1 排在 x0x_0 之前。

用多项式计算

test "arithmetic" {
  let x = @immut.TermPolynomial::from_array([([1U], 1)])
  let y = @immut.TermPolynomial::from_array([([0U, 1], 1)])
  let one : @immut.TermPolynomial[Int] = @immut.TermPolynomial::one()
  let p = (x + y + one).pow(2)
  inspect(p.size(), content="6")
  inspect(p.eval([1, 1]), content="9")
  inspect(p - p, content="0")
}

(x0+x1+1)2(x_0 + x_1 + 1)^2 有六项，在 (1,1)(1, 1) 处的值为 32=93^2 = 9。

安全地求值

eval 需要为多项式用到的每个变量提供一个值，即至少 arity() 个值：

test "evaluation" {
  let p = @immut.TermPolynomial::from_array([([0U, 0, 1], 2), ([], 1)])
  inspect(p.arity(), content="3")
  assert_true(p.eval_checked([1, 1]) is None)
  debug_inspect(p.eval_checked([0, 0, 5]), content="Some(11)")
}

当求值点来自用户输入时使用 eval_checked；eval 在数组过短时会中止。

乘以单项式

scale(γ, c) 用一次线性扫描乘以 c xγc\,x^\gamma：

test "scale" {
  let p = @immut.TermPolynomial::from_array([([1U], 1), ([], 1)])
  let shifted = p.scale(@immut.ExponentVector::from_array([0U, 2]), 4)
  inspect(shifted, content="4 * xx_1^2 + 4 * x_1^2")
}

深入了解

遍历各项

由于各项是普通的有序列表，许多算法就是一次过滤或折叠。下面是求给定次数的齐次部分：

fn[A : Eq + @immut.AddMonoid] homogeneous_part(
  p : @immut.TermPolynomial[A],
  degree : UInt,
) -> @immut.TermPolynomial[A] {
  @immut.TermPolynomial::from_terms(p.to_terms().filter(t => t.0.degree() == degree))
}

test "homogeneous part" {
  let p = @immut.TermPolynomial::from_array([([2U], 1), ([1U, 1], 3), ([1U], 7), ([], 4)])
  inspect(homogeneous_part(p, 2), content="3 * xx_1 + 1 * x^2")
  inspect(homogeneous_part(p, 5), content="0")
}

切换到映射存储

需要按指数查找时，通过项列表进行转换：

test "to sparse" {
  let t = @immut.TermPolynomial::from_array([([1U, 1], 3), ([], 4)])
  let s = @immut.SparsePolynomial::from_terms(t.to_terms())
  debug_inspect(s.get(@immut.ExponentVector::from_array([1U, 1])), content="Some(3)")
}

泛型代码

接受 MultivariateOps 以保持与存储方式无关：

fn[P, A] value_of_square(ops : @immut.MultivariateOps[P, A], p : P, at : Array[A]) -> A {
  ops.eval_indexed(ops.mul(p, p), at)
}

test "generic" {
  let terms = [([1U], 1), ([0U, 1], 1)]
  let t = @immut.TermPolynomial::from_array(terms)
  let s = @immut.SparsePolynomial::from_array(terms)
  inspect(value_of_square(@immut.TermPolynomial::ops(), t, [1, 2]), content="9")
  inspect(value_of_square(@immut.SparsePolynomial::ops(), s, [1, 2]), content="9")
}

具名变量与代换

TermPolynomial 按位置寻址变量，且没有代换功能。把它包装在 ContextPolynomial 中即可为变量命名并进行代换：

test "with names" {
  let ctx = @immut.VariableContext::from_names(["x", "y"])
  let t = @immut.TermPolynomial::from_array([([1U, 1], 2)])
  let p = @immut.ContextPolynomial::from_term_polynomial(ctx, t)
  inspect(p, content="2 * x * y")
}

常见陷阱

  • UInt 字面量。 指数数组的类型是 Array[UInt]；把第一个元素写成 1U，使字面量的类型正确。
  • 末尾的零不会增加变量。 [1, 0, 0] 是 x0x_0，其元数是 1 而不是 3。
  • 序是分次的，而不是字典序。 x1x_1 排在 x0x_0 之前，而 x02x_0^2 排在两者之前。
  • 打印的单项式没有分隔符。 xx_1 表示 x0x1x_0 x_1。
  • 大型乘积。 * 在合并前会物化全部 mnmn 个乘积；对于非常大的稀疏输入，这会消耗大量内存。

后续步骤