functional-programming - 二元多项式的霍纳法则

Question

Horner 规则用于简化在特定变量值处评估多项式的​​过程。 https://rosettacode.org/wiki/Horner%27s_rule_for_polynomial_evaluation#Standard_ML

我已经很容易地将使用 SML 的方法应用于单变量多项式，表示为一个 int 列表:

fun horner coeffList x = foldr (fn (a, b) => a + b * x) (0.0) coeffList

这工作正常。然后我们可以使用以下方法调用它:

- val test = horner [1.0, 2.0, 3.0] 2.0;
> val test = 17.0 : real

哪里 [1.0, 2.0, 3.0]是表示多项式系数的列表， 2.0是变量 x 的值， 17.0是对多项式求值的结果。

我的问题是这样的:我们有一个由 (int list list) 表示的两个变量多项式。高级列表中的第 n 项将表示所有包含 y^n 的多项式项，而低级列表中的第 m 项将表示所有包含 x^m 的多项式项。

例如: [[2],[3,0,0,3],[1,2]]是多项式

( 2(x^0)(y^0) ) +
( 3(x^0)(y^1) + 0(x^1)(y^1) + 0(x^2)(y^1) + 3(x^3)(y^1) ) +
( 1(x^0)(y^2) + 2(x^1)(y^2) )

该函数需要返回指定 x 和 y 处的多项式值。

我已经尝试过使用 mlton 编译器的各种方法。

首先我尝试了一个嵌套的 foldr 函数:

fun evalXY (z::zs) x y = 
        foldr 
        (fn (s, li:list) => 
            s + ((foldr (fn(a, b) => a + b*x) 0 li)*y)
        )
        0 
        z:zs

您可以看到我正在尝试使用“s”作为累加器，就像在单变量示例中使用“a”一样。由于 foldr 处理的每个元素都需要自己“折叠”，因此我在描述外部 foldr 的函数中再次调用 foldr。我知道这个内部文件夹工作正常，我在上面证明了这一点。 *我的问题似乎是我无法访问外部文件夹所在的列表元素以将该列表传递到内部文件夹中。 >看看我在内部文件夹中使用 li 的地方，那是我的问题。 *

然后我尝试应用我的单变量函数来映射。我遇到了同样的问题:

fun evalXY (z::zs) x y = 
        map 
        (foldr (fn(a, b) => a + b*x) 0 ???)
        z:zs

*通过这次尝试，我知道我得到了一个整数列表。我放入了一个 int 列表列表，其中处理内部列表并通过 foldr 作为 int 返回到外部列表。在此之后，我将再次折叠以将 y 值应用于多项式。
这里的函数应该看起来像::fn evalXY : (int list list) * int * int) -> ... -> int list *

我是 SML 的新手，所以也许我在这里遗漏了一些基本的东西。我知道这是一种函数式编程语言，所以我试图累积值而不是改变不同的变量，

Answer 1

你很亲近。让我们从形式化问题开始。给定系数 C 作为您指出的嵌套列表，您想要评估



请注意，您可以拔出 s 从内部和，得到



仔细查看内部总和。这只是变量 x 上的多项式，系数由 给出.在 SML 中，我们可以根据您的 horner 来写内和作为

fun sumj Ci = horner Ci x

让我们更进一步定义



在 SML 中，这是 val D = map sumj C .我们现在可以用 D 写出原始多项式:



应该清楚，这只是 horner 的另一个实例。 ，因为我们有一个系数为 的多项式.在 SML 中，这个多项式的值是

horner D y

......我们完成了!

这是最终的代码:

fun horner2 C x y =
  let
    fun sumj Ci = horner Ci x
    val D = map sumj C
  in
    horner D y
  end

这不是很好吗？我们所需要的只是霍纳方法的多次应用，以及 map .