Conversion from imperative to functional programming [Python to Standard ML]

Question

I have a function specification that states it that should evaluate a polynomial function of one variable. The coefficient of the function is given as a list. It also accepts the value of the variable as a real.

For example: eval(2, [4, 3, 2, 1]) = 26 (1*x^3 + 2*x^2 + 3*x^1 + 4*x^0, where x = 2)

Here's the function in python, but I'm not sure how to convert it to SML. I'm having trouble finding a way to pass it the iteration value without changing the parameters of the function. It needs to remain a real * real list -> real function.

def eval(r, L):
    sum = 0
    for i in range(0, len(L)):
        sum = sum + L[i] * (r ** i)
    return sum

Try not to name your function eval. There is already a built-in eval (docs.python.org/library/functions.html#eval) function doing completely different things. — kennytm
– kennytm, Commented Feb 22, 2010 at 18:30
The name is in the specification. The python code is just for reference. At least, eval should be the name in sml. — efritz
– efritz, Commented Feb 22, 2010 at 18:31
Oh, and it's better to evaluate a polynomial using Horner's scheme (en.wikipedia.org/wiki/Horner_scheme). — kennytm
– kennytm, Commented Feb 22, 2010 at 18:32

sepp2k · Accepted Answer · 2010-02-22 18:54:28Z

4

The usual way to express sums in functional languages is a fold. You can get rid of the need for an index (and a function to raise an int to the power of another int) by multiplying the sum with r in each iteration:

fun eval radix lst = let
  fun f (element, sum) = sum * radix + element
in
  foldr f 0 lst
end

Now the function can be used like this:

- eval 10 [1,2,3];
val it = 321 : int

answered Feb 22, 2010 at 18:54

sepp2k

372k56 gold badges687 silver badges687 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

efritz Over a year ago

This works, but the assignment specifically calls for a pattern-matching solution, so I'm guessing that it should run through the algorithm by hand, not using fold / foldl or foldr.

ephemient · Accepted Answer · 2010-02-22 19:22:30Z

1

You can use explicit recursion to walk through the list of coefficients, exponentiate the radix, and sum up the total.

fun eval r =
    let fun step (power, sum) (coeff :: rest) =
                step (power * r, sum + coeff * power) rest
          | step (_, sum) nil = sum
    in step (1, 0)
    end

Structurally, this is exactly like a fold, and it becomes clearer if we replace it with one.

fun eval r lst =
    let fun step (coeff, (power, sum)) = (power * r, sum + coeff * power)
        val (_, sum) = foldl step (1, 0) lst
    in sum
    end

You can reverse the order of operations to use Horner's scheme, as mentioned in KennyTM's comment: that would result in sepp2k's answer, which requires half as many multiplications, but uses more stack space.

answered Feb 22, 2010 at 19:22

ephemient

206k39 gold badges292 silver badges402 bronze badges

1 Comment

efritz Over a year ago

This works, but the assignment specifically calls for a pattern-matching solution, so I'm guessing that it should run through the algorithm by hand, not using fold / foldl or foldr.

Collectives™ on Stack Overflow

Conversion from imperative to functional programming [Python to Standard ML]

2 Answers 2

1 Comment

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related