Horner's rule for two-variable polynomial

Question

Horner's rule is used to simplify the process of evaluating a polynomial at specific variable values. https://rosettacode.org/wiki/Horner%27s_rule_for_polynomial_evaluation#Standard_ML

I've easily applied the method using SML, to a one variable polynomial, represented as an int list:

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

This works fine. We can then call it using:

- val test = horner [1.0, 2.0, 3.0] 2.0;
> val test = 17.0 : real

Where [1.0, 2.0, 3.0] is the list representing the polynomial coefficients, 2.0 is the value of the variable x, and 17.0 is the result of evaluating the polynomial.

My problem is as such: We have a two variable polynomial represented by an (int list list). The nth item in a high-level list will represent all the polynomial terms containing y^n, and the mth item in a low-level list will represent all the polynomial terms containing x^m.

For example: [[2],[3,0,0,3],[1,2]] is the polynomial

( 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) )

The function needs to return the value of the polynomial at the specified x and y.

I've tried various methods using the mlton compiler.

1. First I tried a nested foldr function:

   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
   

You can see that I'm trying to use "s" as an accumulator, like "a" was used in the single variable example. Since each element being processed by foldr needs to be "foldr'ed" itself, i call foldr again in the function describing the outer foldr. I know hat this inner foldr works fine, I proved it above. *My problem seems to be that I cant access the element of the list that the outer foldr is on to pass that list into the inner foldr. >See where I use li in the inner foldr, thats my issue. *

2. Then i tried applying my single variable function to map. I came across the same issue:

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

   *With this attempt, i know that im getting back a list of ints. I put in an int list list, in which the inner lists were processed and returned to the outer list as ints by foldr. After this i would foldr again to apply the y value to the polynomial. The function here should look like :: fn evalXY : (int list list) * int * int) -> ... -> int list *

I am new to SML, so maybe i'm missing something fundamental here. I know this is a functional programming language, so I'm trying to accumulate values instead of altering different variables,

Answer 1

You're very close. Let's begin by formalizing the problem. Given coefficients C as a nested list like you indicated, you want to evaluate

Notice that you can pull out the s from the inner sum, to get

Look closely at the inner sum. This is just a polynomial on variable x with coefficients given by . In SML, we can write the inner sum in terms of your horner function as

fun sumj Ci = horner Ci x

Let's go a step further and define

In SML, this is val D = map sumj C. We can now write the original polynomial in terms of D:

It should be clear that this is just another instance of horner, since we have a polynomial with coefficients . In SML, the value of this polynomial is

horner D y

...and we're done!

---

Here's the final code:

fun horner2 C x y =
  let
    fun sumj Ci = horner Ci x
    val D = map sumj C
  in
    horner D y
  end

Isn't that nice? All we need is multiple applications of Horner's method, and map.