0

我正在为自己的需要编写简单的多项式相关库。至于现在，我只使用 GF(2) 上的多项式基础中的多项式，因此它们简单地表示为

case class Polynomial(coeffs: BitSet)

所以我可以写一些类似的东西

Polynomial(BitSet(0,1,2))

代表

(x^2 + x + 1)

现在，我对我的乘法函数感到特别自豪：

def *(that: Polynomial): Polynomial = Polynomial {
    coeffs.foldLeft(BitSet.empty) { case (acc, i) => acc ^ that.coeffs.map(i +) }
}

但就目前而言，我所有用其他多项式模表示约简的努力都没有显示出任何类似的结果。我确实明白除法有点复杂，但我目前有非常非常肮脏的递归解决方案，我根本不喜欢它。我目前拥有的类似于以下内容（不要忘记我们在 GF(2) 中）。（UPD：简化代码使其可在类外运行）

  def foo(thisSet: BitSet, thatSet: BitSet): BitSet = {
    var ts = thisSet
    while (!ts.isEmpty && ts.max >= thatSet.max) {
      ts = ts ^ thatSet.map(_ - thatSet.max + ts.max)
    }
    ts
  }

它工作得很好（虽然到目前为止我没有写任何测试），但我想要一些整洁的东西（最多尾递归，但最好只使用折叠/映射/减少。

4

1 回答 1

0

您总是可以以递归方式编写简单的循环

以您的 foo 函数为例：

import scala.annotation.tailrec
def fooRec(thisSet : BitSet, thatSet : BitSet) : BitSet = {
    @tailrec def loop(acc : BitSet) : BitSet = {
        if (!acc.isEmpty && acc.max >= thatSet.max) loop(acc ^ thatSet.map(_ - thatSet.max + acc.max))
        else acc
    }
    loop(thisSet)
}                                         //> fooRec: (thisSet: scala.collection.BitSet, thatSet: scala.collection.BitSet)
                                          //| scala.collection.BitSet

foo(BitSet(1, 2, 0), BitSet(3, 0, 1))           //> res0: scala.collection.BitSet = BitSet(0, 1, 2)
fooRec(BitSet(1, 2, 0), BitSet(3, 0, 1))        //> res1: scala.collection.BitSet = BitSet(0, 1, 2)

您可以看到，var ts是内部递归函数的参数，loop而现在只是一个if。

在我看来，尾递归函数和 while 循环在性能和可读性上几乎相同。你可以选择最适合你的风格。

我个人认为这个版本并不比 while 版本更脏。

于 2013-11-06T09:59:04.157 回答