多項式の計算

/* polynom.ts */

export {
  listEqual,
  calcProductCoef,
  calcProductCoefByList,
  normalizePolynomList,
  polynomListEqual,
  combineSimilarTerms,
  removeZeroTerms,
  sortTermsByDeg,
  normalizePolynom,
  monomEqual,
  polynomEqual,
}

/* ========== */

// 気分だけだが
type nat = number; // natは自然数の型
type someSemiring = number; // someSemiring はとある半環の型

// 多項式の積の係数を計算する
function calcProductCoef(n: nat,
  p: (i: nat) => someSemiring, q: (j: nat) => someSemiring)
  : someSemiring 
{
  let r: someSemiring = 0; // 半環のゼロ
  for (let i: nat = 0; i <= n; i++) { // 総和する
    r += p(i) * q(n - i); // 半環の足し算と掛け算
  }
  return r; // 半環の要素を返す
}

/* ========== */

// 上と同じだが、データをリストで渡せる
function calcProductCoefByList(n: nat,
  p: List<someSemiring>, q: List<someSemiring>)
  : someSemiring
{
  let r: someSemiring = 0;
  for (let i: nat = 0; i <= n; i++) {
    if (i < p.length && (n - i) < q.length) {
      r += p[i] * q[n - i];
    }
  }
  return r;
}

/* ========== */

type EqType = number;

// イコール比較可能な型を成分とするリストの等値性
function listEqual(list1: Array<EqType>, list2: Array<EqType>)
  : boolean 
{
  if (list1.length != list2.length) return false;
  for (let i = 0; i < list1.length; i++) {
    if (list1[i] != list1[i]) return false;
  }
  return true;
}

/* ========== */

// 気分だけだが
type List<X> = Array<X>;

// リスト表示した多項式の正規化
function normalizePolynomList(list: List<someSemiring>)
  :List<someSemiring>
{
  // 1を引いたり足したりしているのは、配列仕様による（鬱陶しい）。
  let k:nat = list.length - 1;
  // インデックス k を減らしながら、右から左に順に見ていく。
  while (k >= 0) {
    if (list[k] != 0) break; // 0でないなら抜ける
    k--; // 左に移動
  }
  // 0の部分は切り落として残りを返す。
  return list.slice(0, k + 1);
}

// リスト表示した多項式の等値性
function polynomListEqual(list1: List<someSemiring>, list2: List<someSemiring>)
  :boolean 
{
  // 正規化
  let normalized_1 = normalizePolynomList(list1);
  let normalized_2 = normalizePolynomList(list2);
  // listEqual はどっかで定義されているとする
  return listEqual(normalized_1, normalized_2);
}

/* ========== */

// 係数型が R の単項式の型
// coef 係数、deg 次数
type Monom<R> = { coef: R, deg: nat };
// 係数型が R の多項式の型
type Polynom<R> = List<Monom<R>>;

// 単項式のリストの係数達を全部足す
function sumUpCoefs(list: List<Monom<someSemiring>>)
  :someSemiring 
{
  let total:someSemiring = 0
  for (let monom of list) {
    total += monom.coef; // 係数を足し上げる
  }
  return total;
}

// 同類項をまとめる
function combineSimilarTerms(p:Polynom<someSemiring>)
  :Polynom<someSemiring>
{
  // 作業用のハッシュマップを準備する
  let map:Map<nat, List<Monom<someSemiring>>>;
  map = new Map<nat, List<Monom<someSemiring>>>();
  // 次数ごとに単項式をまとめたリストを作る
  for (let monom of p) {
    if (!map.has(monom.deg)) {
        map.set(monom.deg, []);
    }
    // 次数をキーにした単項式のリストに追加する
    let a = map.get(monom.deg);
    a!.push(monom);
  }
  // 同類項達の係数を足し算して単項式にする
  // それらの単項式をリストにする、それが結果
  let result:Polynom<someSemiring> = [];
  for (let [deg, monomList] of map) {
    let totalCoef:someSemiring = sumUpCoefs(monomList);
    let combinedTerm:Monom<someSemiring> = {coef:totalCoef, deg:deg};
    result.push(combinedTerm);
  }
  return result;
}

// 多項式から係数ゼロの単項式を取り除く
function removeZeroTerms(p:Polynom<someSemiring>)
  :Polynom<someSemiring>
{
  let result:Polynom<someSemiring> = [];
  for (let monom of p) {
    if (monom.coef == 0) continue;
    result.push(monom);
  }
  return result;
}

// 2つの単項式を次数によって比較する（ソート用）
function compareByDeg(m1: Monom<someSemiring>, m2: Monom<someSemiring>)
  : number 
{
  return m1.deg > m2.deg ? 1 : (m1.deg == m2.deg ? 0 : -1);
}

// 多項式＝単項式のリストを、次数によってソートする
function sortTermsByDeg(p:Polynom<someSemiring>)
  :Polynom<someSemiring>
{
  return p.slice().sort(compareByDeg);
}

// 多項式を正規化する
function normalizePolynom(p:Polynom<someSemiring>)
  :Polynom<someSemiring>
{
  // 作業用変数、使い回す
  let q:Polynom<someSemiring> = p;
  // 多項式の同類項をまとめる
  q = combineSimilarTerms(q);
  // ゼロ項を取り除く
  q = removeZeroTerms(q);
  // 次数でソートする
  q = sortTermsByDeg(q);
  // オシマイ
  return q;
}

// 単項式の等値性
function monomEqual(m:Monom<someSemiring>,
  n:Monom<someSemiring>)
  :boolean
{
  return m.coef == n.coef && m.deg == n.deg;
}

// 多項式の等値性
function polynomEqual(p:Polynom<someSemiring>,
    q:Polynom<someSemiring>)
  :boolean
{
  // 正規化
  let p1:Polynom<someSemiring> = normalizePolynom(p);
  let q1:Polynom<someSemiring> = normalizePolynom(q);
  // 比較
  if (p1.length != q1.length) return false;
  for (let i = 0; i < p1.length; i++) {
    if (!monomEqual(p1[i], q1[i])) return false;
  }
  return true;
}