# sicp-ex-2.34

Taking the example of 1 + 3x + 5x³ + x⁵, applying Horner’s rule gives us (((((1x + 0)x + 5)x + 0)x + 3)x + 1). Translated into prefix notation yields (+ (* (+ (* (+ (* (+ (* (+ (* 1 x) 0) x) 5) x) 0) x) 3) x) 1), which reveals the recursive structure:

``` (+ (* (+ (* (+ (* (+ (* (+ (* 1 x) 0) x) 5) x) 0) x) 3) x) 1)
(+ (* ………………………………………………………………………………………………………………………………… x) 1)
(+ (* ………………………………………………………………………………………………… x) 3)
etc.
```

Which indicates that the function to be used to accumulate will be (+ (* ⟨higher-order termsx) ⟨coefficent⟩):

``` (define (horner-eval x coefficient-sequence)
(accumulate (lambda (this-coeff higher-terms)
(+ (* higher-terms x) this-coeff))
0
coefficient-sequence))

(horner-eval 2 (list 1 3 0 5 0 1))
⇒ 79
(horner-eval 2 (list 2 3 0 5 0 1)) ; Expect 1 greater than above.
⇒ 80
(horner-eval 2 (list 2 3 0 5 0 2)) ; Expect 2⁵ = 32 greater than above.
⇒ 112
```

jz

```
;; Accumulates the result of the first and the already-accumulated
;; rest.
(define (accumulate op initial sequence)
(if (null? sequence)
initial
(op (car sequence)
(accumulate op initial (cdr sequence)))))

(define nil '())  ;; stupid environment ...

(define (horner-eval x coefficient-sequence)
(accumulate (lambda (this-coeff accum-sum)
(+ this-coeff
(* x accum-sum)))
0
coefficient-sequence))

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

```

Rather Iffy

``` ;; I prefer recursion on the right because it makes it easier to grasp the recursion process.

(define (horner-eval x coefficient-sequence)
(accumulate (lambda (this-coeff higher-terms)
(+ this-coeff (* higher-terms x)))
0
coefficient-sequence))

```