Правило Хорнера для двузначного полинома

Question

Правило Хорнера используется для упрощения процесса вычисления полинома по определенным значениям переменных. 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 является значение переменной х, и 17.0 является результатом вычисления полинома.

Моя проблема такова: У нас есть два переменных полинома, представленных (список списка объектов). N-й элемент в списке высокого уровня будет представлять все полиномиальные члены, содержащие y^n, а m-й элемент в низкоуровневом списке будет представлять все полиномиальные члены, содержащие x^m.

Например: [[2],[3,0,0,3],[1,2]] есть многочлен

(2 (х = 0) (у = 0)) +
(3 (х = 0) (у^1) + 0 (х^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» в качестве аккумулятора, как «а» был использован в пример с одной переменной. Так как каждый элемент, обрабатываемый foldr, должен быть «сломан» сам, я снова вызываю foldr в функции, описывающей внешний foldr. Я знаю, что этот внутренний склад работает отлично, я доказал это выше. * Моя проблема, похоже, в том, что я не могу получить доступ к элементу списка, в котором находится внешний foldr, чтобы передать этот список во внутренний склад. > Посмотрите, где я использую li во внутренней папке, вот моя проблема. *

2. Затем я попытался применить мою единственную переменную функцию для отображения. Я наткнулся на тот же вопрос:

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

   * С этой попытки, я знаю, что им получить обратно список Интс. Я поместил список списка int, в котором внутренние списки были обработаны и возвращены во внешний список как int с помощью foldr. После этого я снова сброшу, чтобы применить значение y к многочлену. функция здесь должна выглядеть :: Fn evalXY: (интермедиат список список) * INT * целое) -> ... -> список Int *

Я новичок в SML, поэтому, возможно, я» m отсутствует что-то фундаментальное здесь.Я знаю, что это функциональный язык программирования, поэтому я пытаюсь накапливать значения вместо изменения разных переменных,

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. Мораль этой истории заключается в том, что при определении функции curries вы должны тщательно охарактеризовать порядок параметров, поскольку это облегчит создание некоторых частичных приложений, чем другие.

Кстати, SML суетливый. В своем обсуждении horner вы сказали, что назовете это как horner list 2. Это должно быть horner list 2.0. Аналогичным образом, во второй попытке использование 0, а не 0.0, проблематично.

Answer 2

Вы очень близко. Начнем с формализации проблемы. С учетом коэффициентов C в виде вложенного списка, как вы указали, вы хотите оценить

Обратите внимание, что вы можете вытащить с от внутренней суммы, чтобы получить

Look близко к внутренней сумме. Это всего лишь многочлен от переменной 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.