計算機プログラムの構造と解釈 第二版 P70 問題2.38
この問題は2つやる事がある。
1. 本に書いてある関数を実装して試してみる。
2. fold-leftと、fold-rightが、どのような並びに対しても、同じ値を生じるためにopが満たすべき性質は何か、考える。
「1」の方は実際に試してみれば分かるのだが、
fold-rigth、まぁいままでやってきたアキュムレータの実装なんだけど
こいつは、リストの右側から順番に評価していきますよって手続き。
fold-leftはその逆で、リストの左側から順に評価していく。
反復的な方法にするとこういう感じになる。
んでまぁ、とはいっても、単にやってみただけだと勉強にならないので、
予測をたてて、展開をしてみる。
たとえば、この問題の
(fold-right / (list 1 2 3))
は展開すると以下のようになると思う。
(/ 1 (/ 2 (/ 3 1)))
fold-leftは
(fold-left / (list 1 2 3))
展開すると以下のようになると思う。
(/ (/ 1 2) 3)
んで「2」の方だけど、
ま、普通に考えて、順番を考慮しなくても良い場合ってことだろう。
基本的に、opは引数を2つとる手続きで、その二つの順番が
変わっても変わらないような手続きならオッケーなんだと思う。
さて実装
#!/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 fold-right accumulate) (define (fold-left op initial sequence) (define (iter result rest) (if (null? rest) result (iter (op result (car rest)) (cdr rest)))) (iter initial sequence)) ;; main (define (main args) (display "(fold-right / 1 (list 1 2 3)) :") (display (fold-right / 1 (list 1 2 3))) (newline) (display "(/ 1 (/ 2 (/ 3 1))) :") (display (/ 1 (/ 2 (/ 3 1)))) (newline) (newline) (display "(fold-left / 1 (list 1 2 3)): ") (display (fold-left / 1 (list 1 2 3))) (newline) (display "(/ (/ 1 2) 3): ") (display (/ (/ 1 2) 3)) (newline) (newline) (display "(fold-right list nil (list 1 2 3)) :") (display (fold-right list nil (list 1 2 3))) (newline) (display "(fold-left list nil (list 1 2 3)) :") (display (fold-left list nil (list 1 2 3))) (newline) 0)
実行
(fold-right / 1 (list 1 2 3)) :3/2 (/ 1 (/ 2 (/ 3 1))) :3/2 (fold-left / 1 (list 1 2 3)): 1/6 (/ (/ 1 2) 3): 1/6 (fold-right list nil (list 1 2 3)) :(1 (2 (3 ()))) (fold-left list nil (list 1 2 3)) :(((() 1) 2) 3)
できたね。