問題2-38〜39

accumulate手続きは、先頭の要素を起点にして右側の要素を組み合わせていくものですが、それとは逆の方向から組み合わせるとどうなるのか。これを確かめる問題に取り組みました。
まずは、本に掲載されているそれぞれの手続きを定義します。fold-rightはaccumulateの定義名を変えただけです。

(define (fold-right op initial sequence)
  (if (null? sequence)
      initial
      (op (car sequence)
          (fold-right op initial (cdr sequence)))))

(define (fold-left op initial sequence)
  (define (iter result rest)
    (if (null? rest)
        result
        (iter (op result (car rest))
              (cdr rest))))
  (iter initial sequence))

opに四則演算記号を用いると、どのような違いが生じるかを調べます。

(define sample-list (list 1 2 3))

(fold-right + 0 sample-list)
(fold-left + 0 sample-list)
=>6
=>6

(fold-right - 0 sample-list)
(fold-left - 0 sample-list)
=>2
=>-6

(fold-right * 1 sample-list)
(fold-left * 1 sample-list)
=>6
=>6

(fold-right / 1 sample-list)
(fold-left / 1 sample-list)
=>3/2
=>1/6

和や積は同じ結果になりますが、差や除は異なる結果になります。fold-leftの方がしっくりくる値です。
では、consやlistはどうなるでしょうか。

(fold-right list '() sample-list)
(fold-left list '() sample-list)
=>(1 (2 (3 ())))
=>(((() 1) 2) 3)

(fold-right cons '() sample-list)
(fold-left cons '() sample-list)
=>(1 2 3)
=>(((() . 1) . 2) . 3)

こんどは、fold-rightの方がまともな値が返ってきました。
さらに、リストの順番を逆転させるreverseを似たような方法で定義するとどうなるかを調べてみました。

(define (reverse-right sequence)
  (fold-right (lambda (x y)
                (cons y x))
              '()
              sequence))

(define (reverse-left sequence)
  (fold-left (lambda (x y)
               (cons y x))
             '()
             sequence))

(reverse-right sample-list)
(reverse-left sample-list)
=>(((() . 3) . 2) . 1)
=>(3 2 1)

fold-leftを用いた場合は、これだけの処理で正しい答えを返す手続きを書くことができましたが、逆の方はかなり怪しい答えが返ってきました。
これらのことから何が言えるのか、ということについては後日考察してみようと思います。