SICP q1.43

gistfile1.scm

; たとえば
; f(f(x))
; はq1.42のcomposeを使って
; ((compose f f) x)
; とかける
;
; ここでf(f(x))をg(x)とする
;
; f(f(f(x)))
; は
; f(g(x))
; とかけるので
; ((compose f (compose f f)) x)
; となる
;
; 同じようにf(g(x))をh(x)とする
;
; f(f(f(f(x))))
; は
; f(h(x))
; とかけるので
; ((compose f (compose f (compose f f))) x)
; となる
;
; つまりcomposeに対して「f」と「1つ前のcompose」を与えれば良さそう
;

(use slib)
(require 'trace)

(load "./q1.42.scm")

; 再帰的
(define (repeated f n)
  (if (= n 1)
    f
    (compose f (repeated f (- n 1)))))


(define (square i) (* i i))
(trace repeated)
(print ((repeated square 2) 5))   ; square(square(5)) => 625
(newline)
(print ((repeated square 3) 5))   ; square(square(square5)))) => 390625
(newline)


; またf(g(x))をh(x)とせず、新しいg(x)とすれば
;
; f(f(f(f(x))))
; は
; f(新しいg(x))
; とかけるので、何度も
; f(g(x))
; を一定の回数繰り返しやるだけ

; 反復的
(define (repeated f n)
  (define (repeated-iter g counter max-count)
    (if (>= counter max-count) 
      g
      (repeated-iter (compose f g) (+ counter 1) max-count)))
  (repeated-iter f 1 n))

(define (repeated f n)
  (define (repeated-iter g counter)
    (if (>= counter n) 
      g
      (repeated-iter (compose f g) (+ counter 1))))
  (repeated-iter f 1))

(trace repeated)
(define (square i) (* i i))
(print ((repeated square 2) 5))
(newline)
(print ((repeated square 3) 5))
(newline)

; 補修
; repeatedはq1.31のsumに似ている
; コピペをやめるためにaccumulateで書き直せ

; sumの場合、
; このときaからbまで1ずつあがっていき（nextがinc）
; それぞれにfを作用させ（termはf）
; f(a)からf(b)までの足し算（combinerは+）で、
; 終了時は何も足さないように0（null-valueが0）
; だった
;
; repeatedの場合、
; n回作用させるのは決まっているため1からnまで1ずつ上がっていき（nextがinc）
; それぞれの項が常にfになるようにし（termは(lambda (x) f)）
; それぞれの項をcomposeし（combinerはcompose）
; 終了時は何もしないようにすればよい（null-valueがidentity）

(define (accumulate combiner null-value term a next b)
    (if (> a b)
      null-value
      (combiner (term a)
         (accumulate combiner null-value term (next a) next b))))

(define (compose f g)
    (lambda (x) (f (g x))))

(define (inc n) (+ n 1))
(define (repeated f n)
  (accumulate compose identity (lambda (x) f) 1 inc n)) 


(define (square i) (* i i))
(print ((repeated square 2) 5))  ;625
(print ((repeated square 3) 5))  ;390625