SICP 問題 2.38（fold-rightとfold-left）

【問題】

accumulate 手続きは、並びの先頭の要素を右方の全ての要素を組み合わせた結果に組み合わせるので、 fold-right としても知られている。逆向きに仕事をしながら要素を組み合わせる他は fold-right と類似な fold-left もある。

(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-left / 1 (list 1 2 3))

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

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

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

【解答】

とりあえず評価してみようか。

gosh> (fold-right / 1 (list 1 2 3))

3/2

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

1/6

gosh> (fold-right list '() (list 1 2 3))

(1 (2 (3 ())))

gosh> (fold-left list '() (list 1 2 3))

(((() 1) 2) 3)

gosh> 

op が「どのような並びに対しても同じ値を生じる」には「結合則」である必要がある。
例をあげると加算とか乗算とかだぁね。