問題解答

問2.38
(fold-right / 1 (list 1 2 3)) は以下のような処理になる。

(op 1
    (fold-right op 1 (2 3)))
(op 1
    (op 2
        (fold-right op 1 (3))))
(op 1
    (op 2
        (op 3
            (fold-right op 1 ())))
(op 1
    (op 2
        (op 3
            1)))
(op 1
    (op 2
        3))
(op 1
    2/3)
3/2

(fold-left / 1 (list 1 2 3)) は以下。

(iter 1 (1 2 3))
(iter (op 1 1) (2 3)) → (iter 1 (2 3))
(iter (op 1 2) (3)) → (iter 1/2 (3))
(iter (op 1/2 3) ()) → (iter 1/6 ())
1/6

op はオペランドが入れ替わっても同じ結果を返すものであれば fold-right と fold-left で同じ値を得ることができる。

問2.39

(define (reverse sequence)
  (fold-right (lambda (x y) (append y (list x))) () sequence))

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

cons, list 周りと append などのオペレーション周りの理解が怪しい感じがしたので復習。