計算機プログラムの構造と解釈 第二版 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)

できたね。