Hatena::Groupcsnagoya-sicp

クラなんとかの日記 このページをアンテナに追加 RSSフィード

 | 

2009-06-11準備会

2.38

| 2.38 - クラなんとかの日記 を含むブックマーク はてなブックマーク - 2.38 - クラなんとかの日記 2.38 - クラなんとかの日記 のブックマークコメント

accumulate は,先頭の要素に右側の要素を組み合わせるので,fold-right と呼ばれている.

fold-left のことを考えてみようという問題.

fold-right と fold-left の結果が等しくなるのは,op の結果が引数の順序で不変である場合.(+ や * など)

#!/usr/bin/env gosh
;; -*- coding: utf-8; -*-
; 

;; 準備
(define (accumulate op initial sequence)
  (if (null? sequence)
      initial
      (op (car sequence)
          (accumulate op initial (cdr sequence)))))

(define fold-right accumulate)

; 問題文より
(define (fold-left op initial  sequence)
  (define (iter result rest)
    (if (null? rest)
        result
        (iter (op result (car rest))
              (cdr rest))))
  (iter initial sequence))

;; 答え

;; 確認
(define x (list 1 2 3))

(display x) (newline) ; (1 2 3)
(display (fold-right / 1 x)) (newline) ; 3/2 {= 1 / (2 / (3 / 1))}
(display (fold-left / 1 x)) (newline) ; 1/6 {= (1 / 2) / 3}
(display (fold-right list (list) x)) (newline) ; (1 (2 (3 ())))
(display (fold-left list (list) x)) (newline) ; (((() 1) 2) 3)
 |