乐正

Actions speak louder than words.

Sicp-ex2-38

问题

过程accumulate也称为fold-right,因为它将序列的序列的第一个元素组合到右边所有 元素的组合结果上。也有一个fold-left,它与fold-right类似,但却按照相反的方向 去操作各个元素:

fold-left (p82-fold-left.scm) download
1
2
3
4
5
6
7
8
9
;; Happy hacking Yuez - Emacs ♥ you!

(define (fold-left op initial sequence)
  (define (iter result rest)
    (if (null? rest)
        result
        (iter (op result (car rest))
              (cdr rest))))
  (iter initial sequence))

下面表达式的值是什么?

1
2
3
4
5
6
7
(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))

如果要求用某个op时保证fold-rightfold-left对任何序列都产生同样的结果,请 给出op应该满足的性质。

解答

1
2
3
4
5
6
7
8
9
10
11
(accumulate / 1 (list 1 2 3))
;Value: 3/2

(fold-left / 1 (list 1 2 3))
;Value: 1/6

(accumulate list '() (list 1 2 3))
;Value 37: (1 (2 (3 ())))

(fold-left list '() (list 1 2 3))
;Value 38: (((() 1) 2) 3)

如果要求保证fold-rightfold-left对任何序列计算都产生同样的结果,则op应该 满足交换律和结合律。例如+

1
2
3
4
5
(accumulate + 0 (list 1 2 3))
;Value: 6

(fold-left + 0 (list 1 2 3))
;Value: 6

draft

« sicp-ex2-37 sicp-ex2-39 »

Comments