Curried function for evaluating an equation in SML

Question

The exact problem I need to work out is below.

Basically, I am given a list of real numbers, representing coefficients. The first element is the constant value, and all that follow it are the coefficients of the polynomial equation. So, eval[1.0, 5.0, 3.0] 2.0 would be constructing the equation "1 + 5x + 3x^2" and evaluating it at 2.0, resulting in 23.0. The function needs to be of type "real list -> real -> real".

Now, what I need to do is implement eval within SML using a curried function, so that it is all one line, and there are no recursive calls. I've already done the recursive way and understand that, but am having troubles wrapping my mind around the curried way. We need to use functions like map, foldr, and foldl to accomplish this, as well as anonymous functions. My thought about this was to for the function to take the list and take just the tail of it (all but head element, which is the constant), and evaluate that, using foldl. The problem I run into is I'm not sure if that is even possible, or how to accomplish this with keeping track of how far into the list I've gone (a counter), so that I could properly use their powers.

Any help at all would be greatly appreciated.

Answer 1

Considering that the fold function, the list datastructure and tail-recursion are intertwined, you can come up easily with a fold-based solution if you already have a tail-recursive solution.

The problem of evaluating a polynom can be solved using a recursive function that implements horners method:

fun eval [] _ = 0.0
  | eval (y :: ys) x = y + x*(eval ys x)

That function can be easily transformed into a tail-recursive function and after that a solution using foldr should emerge:

fun eval ys x = foldr (fn (y,a) => y + x*a) 0.0 ys

So how does foldr work here?

Given a list of coefficents [y0,y1,y2,y3] which represents the following polynom f(x)=y0+y1*x+y2*x^2+y3*x^3.

foldr does apply the anonymous function fn (y,a) => y + x*a to the list of coefficents step by step. It processes the list from right to left. It takes as its first parameter y the coefficents in the following order (first y3, then y2, then y1, finally y0).

The second parameter a does hold the temporary result of the evaluation. The parameter a is often called the accumulator. First it is initialized with 0.0. At the next step the accumulator holds the value of y3*x. Then the accumulator holds the value of y2*x+y3*x^2. After that it holds the value of y1*x+y2*x^2+y3*x^3. Finally the anonymous function is called with the coefficient y0 and it yields the result, which is the value of the evaluated polynom.