霍纳规则的双变量多项式

霍纳规则用于简化在特定变量值下评估多项式的过程。 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（x^0）（y^2）+ 2（x^3）（y^1）+0（x^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。我知道这个内部折叠器工作正常，我在上面证明了它。 *我的问题似乎是，我无法访问列表中的元素，外部折叠器将该列表传递到内部折叠器。 >看看我在哪里使用锂在内部折叠器，这是我的问题。 *

然后我试着应用我的单变量函数来映射。我碰到了同样的问题：
```
fun evalXY (z::zs) x y = 
     map 
     (foldr (fn(a, b) => a + b*x) 0 ???) 
     z:zs 
```
*有了这次尝试，我知道，即时得到回INTS的列表。我把一个int列表列表中，其中内部列表被处理并作为int整数返回到外部列表。在此之后，我再次折叠以将y值应用于多项式。这里的功能应该像:: FN evalXY：（INT名单列表）* INT * INT） - > - > INT列表*

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

来源

2017-02-04 M Miller

2014年的[SNA中的Horner算法？]（http://stackoverflow.com/questions/25099601/horners-algorithm-in-sml）的重复。我建议您使用Googling StackOverflow的课程应该有一个幻灯片在寻找前几年给予课程参与者的答案时。 ;-) –

如果你没有意识到，这个问题处理给定多项式中的两个变量（即f = 3xy）。很相似，但很难实现，如果你是新的语言 –

我没有看到，对不起。 –

你的第二种方法似乎是在正确的轨道上。如果您已经定义horner，你需要做的是在外部列表应用horner于映射horner applied to inner list x的结果是这样的：

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

您可以通过相应的褶皱更换两次调用horner，但它会更不易读。

请注意，如果您反转两个参数的顺序horner那么你就可以缩短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)

在于方式讨好的作品的时候，如果你使用这个二阶然后horner x已经是一个功能coeffList因此您不再需要匿名功能fn coeffList => horner coeffList x。故事的寓意是，当定义一个curried函数时，应该仔细考虑参数的顺序，因为它会使一些部分应用程序比其他应用程序更容易创建。

顺便说一句，SML很挑剔。在你对horner的讨论中，你说过你会称之为horner list 2。它将需要是horner list 2.0。同样，在第二次尝试中，使用0而不是0.0是有问题的。

来源

2017-02-04 16:22:48

这非常有帮助。谢谢！ –

你非常接近。我们首先将问题正式化。鉴于系数C为嵌套表像你指出，你要评估

$\sum_i \sum_j C_{i,j} \cdot y^i x^j$

注意，您可以从内部和拔出 $y^i$ S，得到

$\sum_i y^i \left(\sum_j C_{i,j} \cdot x^j \right)$

看内心深处。这只是变量x上的一个多项式，系数由 $C_i$ 给出。在SML，我们可以写在你的horner功能方面的内部和作为

fun sumj Ci = horner Ci x

让我们更进一步，并定义

$D_i = \sum_j C_{i,j} \cdot x^j$

在SML，这是val D = map sumj C。现在，我们可以写在d方面原多项式：

$\sum_i \sum_j C_{i,j} \cdot x^j y^i = \sum_i y^i \left(\sum_j C_{i,j} \cdot x^j\right) = \sum_i D_i \cdot y^i$

应该明确的是，这是horner只是一个例子，因为我们有一个系数 $D_i$ 多项式。在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-04 20:21:05

二维霍纳方法的基本逻辑的很好的解释。 –

霍纳规则的双变量多项式

回答

相关问题