Serendip

Web Studio

問題2.38

fold-right と fold-left 手続き

(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))

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

演算を行う順序に結果が左右されないような op の場合、どのような並びに対しても同じ値を生じる。

(fold-right + 0 (list 1 2 3))
gosh> 6
(fold-left + 0 (list 1 2 3))
gosh> 6
(fold-right * 1 (list 1 2 3))
gosh> 6
(fold-left * 1 (list 1 2 3))
gosh> 6

計算機プログラムの構造と解釈

posted with amazlet at 08.11.07

ジェラルド・ジェイ サスマン ジュリー サスマン ハロルド エイブルソン
ピアソンエデュケーション
売り上げランキング: 6542

Amazon.co.jp で詳細を見る