霍纳对双变量多项式的规则

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列表列表)表示的两个变量多项式.高级列表中的第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.我知道帽子这个内部折叠工作正常,我证明了它.*我的问题似乎是我无法访问外部折叠器所在的列表元素以将该列表传递到内部折叠器中.>看看我在内部折叠器中使用li的位置,这就是我的问题.*

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

   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

您的第二种方法似乎走在正确的轨道上。如果您已经定义了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。这个故事的寓意是，在定义柯里化函数时，您应该仔细考虑参数的顺序，因为这将使某些部分应用程序比其他应用程序更容易创建。

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