霍納規則的雙變量多項式

霍納規則用於簡化在特定變量值下評估多項式的過程。 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

二維霍納方法的基本邏輯的很好的解釋。 –

霍納規則的雙變量多項式

回答

相關問題