**Exercise 2.34:** Evaluating a polynomial in x at a given value of x can be formulated as an accumulation. We evaluate the polynomial

using a well-known algorithm called Horner’s rule, which structures the computation as

In other words, we start with an, multiply by x, add a_{n-1}, multiply by x, and so on, until we reach a_{0}. Fill in the following template to produce a procedure that evaluates a polynomial using Horner’s rule. Assume that the coefficients of the polynomial are arranged in a sequence, from a_{0} through a_{n}.

1 2 3 4 |
(define (horner-eval x coefficient-sequence) (accumulate (lambda (this-coeff higher-terms) <??>) 0 coefficient-sequence)) |

For example, to compute at you would evaluate

1 |
(horner-eval 2 (list 1 3 0 5 0 1)) |

I included a non-abstracted version of Horner’s method for clarity.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
(define (accumulate fn init-value items) (if (null? items) init-value (fn (car items) (accumulate fn init-value (cdr items))))) (define (he x coeff-seq) (if (null? coeff-seq) 0 (+ (car coeff-seq) (* x (he x (cdr coeff-seq)))))) (define (horner-eval x coeff-seq) (accumulate (lambda (this-coeff higher-terms) (+ this-coeff (* x higher-terms))) 0 coeff-seq)) |

> (horner-eval 2 (list 1 3 0 5 0 1))

*79*

> (horner-eval 2 (list 1))

*1*

> (horner-eval 2 (list ))

*0*

> (horner-eval 2 (list 1 1))

*3*