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

Your second approach seems to be on the right track. If you have already defined horner, what you need to do is to apply horner to the result of mapping horner applied to inner list x over the outer list, something like:

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

You could replace the two calls to horner by the corresponding folds, but it would be much less readable.

Note that if you reverse the order of the two parameters in horner then you can shorted 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)

The point being that the way currying works, if you use this second order then horner x is already a function of coeffList so you no longer need the anonymous function fn coeffList => horner coeffList x. The moral of the story is that when defining a curried function, you should think carefully about the order of the parameters since it will make some partial applications easier to create than others.

By the way, SML is fussy. In your discussion of horner you said that you would call it like horner list 2. It would need to be horner list 2.0. Similarly, in your second attempt, using 0 rather than 0.0 is problematic.

Answer 2

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.