5

霍纳规则用于简化在特定变量值处评估多项式的​​过程。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 编译器尝试了各种方法。

  1. 首先我尝试了一个嵌套的 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 的位置，这是我的问题。*

  1. 然后我尝试将我的单变量函数应用于映射。我遇到了同样的问题：

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

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

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

4

2 回答 2

4

你很亲密。让我们从形式化问题开始。给定系数 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.

于 2017-02-04T20:21:05.160 回答
2

Your second approach seems to be on the right track. If you have already defined horner, what you need to do is to apply horner to the result of mapping horner applied to inner list x over the outer list, something like:

fun evalXY coeffLists x y = horner (map (fn coeffList => horner coeffList x) coeffLists) y

You could replace the two calls to horner by the corresponding folds, but it would be much less readable.

Note that if you reverse the order of the two parameters in horner then you can shorted evalXY:

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

The point being that the way currying works, if you use this second order then horner x is already a function of coeffList so you no longer need the anonymous function fn coeffList => horner coeffList x. The moral of the story is that when defining a curried function, you should think carefully about the order of the parameters since it will make some partial applications easier to create than others.

By the way, SML is fussy. In your discussion of horner you said that you would call it like horner list 2. It would need to be horner list 2.0. Similarly, in your second attempt, using 0 rather than 0.0 is problematic.

于 2017-02-04T16:22:48.987 回答