SICP学习笔记 2.2.3 序列作为一种约定的接口

    练习2.33

;; map过程即为使用过程p作用x, 然后再合并作用y后的结果
(define (map p sequence)
  (accumulate (lambda (x y) (cons (p x) y)) '() sequence))

;; append过程为合并两个列表, 则初始值为空表, 要传入的列表为枚举两个参数列表的元素组成的列表
(define (append seq1 seq2)
  (accumulate cons '() (enumerate-tree (list seq1 seq2))))
  
;; length过程即为在y参数不为空时将长度递增
(define (length sequence)
  (accumulate (lambda (x y) (+ 1 y))  0 sequence))

 

    练习2.34

(define (horner-eval x coefficient-sequence)
  (accumulate (lambda (this-coeff higher-terms) (+ this-coeff (* x higher-terms)))
	            0 coefficient-sequence))

 

    练习2.35

(define (count-leaves tree)
  (accumulate + 0 (map (lambda (x) 1) (enumerate-tree tree))))

 

    练习2.36

;; 这里关键是从序列的序列中依次取第一个、第二个、第N个元素
;; 则应首先枚举序列中的每个序列, 检测非空, 分别取首元素
;; 即(map car (filter pair? seqs))
(define (accumulate-n op init seqs)
  (if (null? (car seqs))
      '()
      (cons (accumulate op init (map car (filter pair? seqs)))
	          (accumulate-n op init (map cdr (filter pair? seqs))))))	 

 

    练习2.37

;; 首先定义扩充的map,可以接收多个序列参数        
(define (new-map proc item1 item2)
  (define items (list item1 item2))
  (accumulate-n proc 1 items))
(define (dot-product v w)
  (accumulate + 0 (new-map * v w))) 

;; 矩阵与向量的乘法即为矩阵中的每一行与向量做dot-product  
(define (matrix-*-vector m v)
  (map (lambda (w) (dot-product v w)) m))  
  
;; 矩阵转置即为分别取矩阵相同行的相同列组成新的行
(define (transpose mat)
  (accumulate-n cons '() mat))
;; 矩阵乘法即为第一个矩阵的转置与第二个矩阵中的每一行做matrix-*-vector
(define (matrix-*-matrix m n)
  (let ((cols (transpose n)))
    (map (lambda (w) (matrix-*-vector cols w)) m)))

 

    练习2.38

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

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

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

1 ]=> (fold-right list '() (list 1 2 3))
;Value : (1 (2 (3 ())))

1 ]=> (fold-left list '() (list 1 2 3))
;Value : (((() 1) 2) 3)

;; 因为这两种方式的不同之处在于对结果的累加方式，因为如果对于op，如果满足交换律则两种方式处理的结果相同
1 ]=> (fold-right + 0 (list 1 2 3 4))
;Value: 10
1 ]=> (fold-left + 0 (list 1 2 3 4))
;Value: 10

1 ]=> (fold-right * 1 (list 1 2 3 4))
;Value: 24
1 ]=> (fold-left * 1 (list 1 2 3 4))
;Value: 24

 

    练习2.39

(define (reverse sequence)
  (fold-right (lambda (x y) (append y (list x))) '() sequence))

(define (reverse sequence)
  (fold-left (lambda (x y) (append (list y) x)) '() sequence))

 

    练习2.40

(define (unique-pairs n)
  (flatmap (lambda (i) (map (lambda (j) (list i j))
			                      (enumerate-interval 1 (- i 1))))
	         (enumerate-interval 1 n)))
(define (prime-sum-pairs n)
  (map make-pair-sum (filter prime-sum? (unique-pairs n))))

 

    练习2.41

;; 构建三元组即为在二元组的基础上进行组合
;; 如n为6的三元组即为6与5的二元组的组合
;; 即 (cons i (unique-pairs (- i 1))
(define (unique-pairs-new n)
  (flatmap (lambda (i) (map (lambda (j) (cons i j))
			                      (unique-pairs (- i 1))))
	         (enumerate-interval 1 n)))

1 ]=> (unique-pairs-new 6)
;Value : ((3 2 1) 
          (4 2 1) (4 3 1) (4 3 2) 
          (5 2 1) (5 3 1) (5 3 2) 
          (5 4 1) (5 4 2) (5 4 3) 
          (6 2 1) 
          (6 3 1) (6 3 2) 
          (6 4 1) (6 4 2) (6 4 3)
          (6 5 1) (6 5 2) (6 5 3) (6 5 4))	         
;; 过滤三元组的过程
(define (s-sum-pairs n)
  (filter s-sum? (unique-pairs-new n)))
(define S 8)
(define (s-sum? pair)
  (= S (accumulate + 0 pair)))
  
1 ]=> (s-sum-pairs 6)
;Value : ((4 3 1) (5 2 1))

 

    练习2.42

;; 首先定义棋盘
;; 构造棋盘的一列
(define (matrix-seqs seqs i n)
  (if (< i n)
      (matrix-seqs (cons 0 seqs) (+ i 1) n)
      seqs))
;; 在已有的棋盘上追加n列
(define (matrix-iter matrix i n)
  (if (< i n)
      (matrix-iter (cons (matrix-seqs '() 0 n) matrix) (+ i 1) n)
      matrix))
;; 构造n阶棋盘
(define (matrix-n n)
  (matrix-iter '() 0 n))
1 ]=> (matrix-n 4)
;Value : ((0 0 0 0) (0 0 0 0) (0 0 0 0) (0 0 0 0))	

;; 然后构造在已有格局的基础上追加一列的过程
;; 以4阶棋盘为例
;; 0 0 0 0
;; 1 0 0 0
;; 0 0 0 0
;; 0 1 0 0
;; 此时有n=4, k=3
;; 则新的格局应为(已经安全的前k-1列 + 需要循环检测每行安全性的第k列 + 暂时为空值的后(n-k)列

;; 构造为空值的后(n-k)列
(define (cdr-rest n k)
  (if (= k n)
	  '()
	  (cons (matrix-seqs '() 0 n) (cdr-rest n (+ k 1)))))

;; 构造需要检测的第k列, 其中第row行的值设为1
(define (make-rest n row)
  (define x (- (+ n 1) row))
  (define (rest-iter seqs i)
    (if (> i n)
	      seqs
	      (if (= i x)
	          (rest-iter (cons 1 seqs) (+ i 1))
	          (rest-iter (cons 0 seqs) (+ i 1)))))
  (rest-iter '() 1))
  
;; 将三者组合在一起构造出新的格局
(define (adjoin-position n row k rest)
  (define cdr-postion (cons (make-rest n row) (cdr-rest n k)))
  (define x (- k 1))
  (define (iter i result)
    (if (> i 0)
	      (iter (- i 1) (cons (list-ref rest (- i 1)) result))
	      result))
  (iter x cdr-postion))   
  
1 ]=> rest
;Value : ((0 1 0 0) (0 0 0 1) (1 0 0 0) (0 0 0 0)) 

1 ]=> (adjoin-position 4 1 4 rest)
;Value : ((0 1 0 0) (0 0 0 1) (1 0 0 0) (1 0 0 0))

1 ]=> (adjoin-position 4 4 4 rest)
;Value : ((0 1 0 0) (0 0 0 1) (1 0 0 0) (0 0 0 1))
     
;; 最后完成安全性的检测

;; 在一列中查找皇后所在的行数
(define (find i seqs)
  (if (= (list-ref seqs (- i 1)) 1)
	    i
	    (find (+ i 1) seqs)))
	    
;; 根据新格局中新添加的皇后的位置与已有的皇后位置进行冲突检测
(define (safe? n k positions)
  (define seqs-k (list-ref positions (- k 1)))
  (define row-k (find 1 seqs-k))
  
  (define (iter i)
    (define seqs-i (list-ref positions (- i 1)))
    (define row-i (find 1 seqs-i))
    (if (= i k)
	      #t
	      (if (= row-i row-k) ;; 相同行
	          #f
	          (if (or (= (+ i row-i) (+ k row-k))
		                (= (- i row-i) (- k row-k)))  ;; 对角线
		            #f
		            (iter (+ i 1))))))
  (iter 1))
  
;; 因此可以使用如下过程进行求解
(define (queens board-size)
  (define empty-board (matrix-n board-size))
  (define (queen-cols k)
    (if (= k 0)
	      (list empty-board)
	      (filter
	        (lambda (positions) (safe? board-size k positions))
	        (flatmap
	          (lambda (rest-of-queens)
	            (map (lambda (new-row)
		                 (adjoin-position board-size new-row k rest-of-queens))
		               (enumerate-interval 1 board-size)))
	          (queen-cols (- k 1))))))
  (queen-cols board-size))
  
1 ]=> (queens 4)
;Value : (((0 1 0 0) (0 0 0 1) (1 0 0 0) (0 0 1 0)) ((0 0 1 0) (1 0 0 0) (0 0 0 1) (0 1 0 0)))

;; 这里序列中的序列代表的是棋盘中的一列, 转换后即为
0 0 1 0    0 1 0 0
1 0 0 0    0 0 0 1
0 0 0 1    1 0 0 0
0 1 0 0    0 0 1 0

 

    练习2.43

;; 交换前
;; 求解(queen n)时会递归调用(queen-cols n)
;; 直到k=0,得到n阶空棋盘
;; 然后在第一列的第i行添加皇后作为新的格局, 共n种格局, 保留通过安全检测的格局
;; 然后依次处理第i列, 共n列
;; 所以这里共调用queen-cols过程n次

;; 交换后
;; 求解(queen n)时会递归调用(queen-cols n)
;; 而(queen-cols n)过程将递归调用嵌套在了嵌套映射中
;; 因此queen-cols将会被调用n^n次

;; 所以Louis的方法将会是原来的N^(N-1)倍