SICP問題2.38

fold-right, fold-leftの定義(教科書で定義済)

(define (fold-right op initial sequence)
  (accumulate op initial 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))

次の値は何か?
(fold-right / 1 (list 1 2 3))

(fold-right / 1 (list 1 2 3))
; 1 / (2 / (3 / 1))
; => 3/2

(fold-left / 1 (list 1 2 3))

(fold-left / 1 (list 1 2 3))
; (iter 1 (1 2 3))
; (iter (/ 1 1) (2 3))
; (iter (/ 1 2) (3))
; (iter (/ (1/2) 3) ())
; => 1/6

(fold-right list () (list 1 2 3))

(fold-right list () (list 1 2 3))
; (list 1 (list 2 (list 3 (list ()))))
; => (1 (2 3 ()))

(fold-left list () (list 1 2 3))

(fold-left list () (list 1 2 3))
; (iter () (1 2 3))
; (iter (list () 1) (2 3))
; (iter (list (() 1) 2) (3))
; (iter (list (() 1) 2) 3) ())
; => (() 1) 2) 3)

fold-rihgt と fold-left がどのような並びに対しても同じ値を生じるためにopが満たすべき性質は何か?

• 演算結果がリストでなくスカラー値であること。
• 和、積のように演算結果が演算順序に関係ないもの。