計算機プログラムの構造と解釈 第二版 P68 問題2.34

この問題も穴埋めだ。

そしてこの問題もaccumulateとにらめっこすることになる。
ポイントは、accumulateは一回展開してから戻ってくる(自分にしか分からない表現)。
再帰プロセスをとる。

あとは記載されているHornerの方法を頭に入れた方がいい。
なにを言ってるかって言うと、具体的に言うと

1 + 3x + 5x^3 + 5x^5

てのはこんな以下のような感じで表現できる

1 + x(3 + x(0 + x(3 + x(0 + 5x))))

これがHornerの方法

あとはぬわーっと考えれば多分解けるはずだ。
実装

#!/usr/local/bin/gosh
;; -*- coding: utf-8 -*-

(use ggc.debug.trace)
(use math.mt-random)

(define nil '())


(define (accumulate op initial sequence)
  (if (null? sequence)
    initial
    (op (car sequence)
        (accumulate op initial (cdr sequence)))))


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


;; main
(define (main args)

  (display "(horner-eval 2 (list 1 3 0 5 0 1)): ")
  (display (horner-eval 2 (list 1 3 0 5 0 1)))
  (newline)

  0)  

実行

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

できた。