Function that returns another function, for a programming task

Question

This is a task I was given for an online course. This is my solution to the problem.

Task: Write a function called general_poly, that meets the specifications below.

For example, general_poly([1, 2, 3, 4])(10) should evaluate to 1234 because

1*10^3 + 2*10^2 + 3*10^1 + 4*10^0

So in the example the function only takes one argument with general_poly([1, 2, 3, 4]) and it returns a function that you can apply to a value, in this case x = 10 with general_poly([1, 2, 3, 4])(10).

def general_poly (L):
    """ L, a list of numbers (n0, n1, n2, ... nk)
    Returns a function, which when applied to a value x, returns the value 
    n0 * x^k + n1 * x^(k-1) + ... nk * x^0 """
    #YOUR CODE HERE 

My Code:

def general_poly (L):
    """ L, a list of numbers (n0, n1, n2, ... nk)
    Returns a function, which when applied to a value x, returns the value
    n0 * x^k + n1 * x^(k-1) + ... nk * x^0 """

    def function_generator(L, x):
        k = len(L) - 1
        sum = 0
        for number in L:
            sum += number * x ** k   
            k -= 1
        return sum

    def function(x, l=L):
        return function_generator(l, x)

    return function

Answer 1

1. The name function_generator could be improved. What this function does is to evaluate the polynomial at the given value x. So a name like evaluate would be better.

2. The body of function_generator can be simplified. First, it's simpler to iterate over L in reversed order, because then you can start with k = 0 rather than k = len(L) - 1:

   def evaluate(L, x):
       k = 0
       sum = 0
       for number in reversed(L):
           sum += number * x ** k   
           k += 1
       return sum
   

   Now that k goes upwards, you can use enumerate to generate the values for k:

   def evaluate(L, x):
       sum = 0
       for k, a in enumerate(reversed(L)):
           sum += a * x ** k
       return sum
   

   And now that the body of the loop is a single expression, you can use the built-in sum function to do the addition:

   def evaluate(L, x):
       return sum(a * x ** k for k, a in enumerate(reversed(L)))
   

   Another approach to polynomial evaluation is to generate the power series in \$x\$ separately:

   def power_series(x):
       "Generate power series 1, x, x**2, ..."
       y = 1
       while True:
           yield y
           y *= x
   

   and then combine it with the coefficients using zip:

   def evaluate(L, x):
       "Evaluate the polynomial with coefficients in L at the point x."
       return sum(a * y for a, y in zip(reversed(L), power_series(x)))
   

   This is more efficient for large polynomials because each step in power_series is a multiplication by x, which is cheaper to compute than the exponentiation x ** k.

   Finally, you could take advantage of this transformation: $$a_k x^k + a_{k-1} x^{k-1} + \dots + a_1x + a_0 = (\cdots ((0 + a_k)x + a_{k-1})x + \cdots + a_1)x + a_0$$ and write:

   def evaluate(L, x):
       "Evaluate the polynomial with coefficients in L at the point x."
       r = 0
       for a in L:
           r = r * x + a
       return r
   

   (This is Horner's method.)

3. There's no need for function, because it's fine for the body of function_generator to refer to nonlocal variables like L. So you can write:

   def general_poly(L):
       "Return function evaluating the polynomial with coefficients in L."
       def evaluate(x):
           r = 0
           for a in L:
               r = r * x + a
           return r
       return evaluate
   

4. An alternative approach is to use functools.partial:

   from functools import partial
   
   def evaluate(L, x):
       "Evaluate the polynomial with coefficients in L at the point x."
       r = 0
       for a in L:
           r = r * x + a
       return r
   
   def general_poly(L):
       "Return function evaluating the polynomial with coefficients in L."
       return partial(evaluate, L)
   

   This would be useful if you sometimes wanted to call evaluate directly (instead of via general_poly).