閱讀28 返回首頁    go 阿裏雲 go 技術社區[雲棲]

sicp習題2.33-2.39嚐試解答

這一節的內容非常有趣，通過將序列作為interface，在此基礎上進而提取出各種高階操作（map,filter,accumulate,enumerate等），由此引出模塊化設計的討論。模塊化設計帶來複雜性的降低，同時可能引入性能上的損失，比如書中對sum-odd-squares過程的兩種寫法，原來的寫法枚舉列表元素的過程散落在累積、過濾、映射的過程中，主要一次循環就夠了，而通過三個高階過程來操作反而需要3次的遍曆。

習題2.33，將map,append,length基本過程用累積操作重新定義，聯係以往的實現通過觀察和測試可以得出：
(define (map p sequence)
  (accumulate  (lambda(x y) 
                (cons (p x) y))       
                       () sequence))
(define (append seq1 seq2)
  (accumulate cons seq2 seq1))
(define (length sequence)
  (accumulate (lambda(x y)
                (+ 1 y))
                0 sequence))
難點就在於累積的操作。

習題2.34，Horner規則求多項式，難點也是累積操作的定義：
(define (horner-eval x coefficient-sequence)
  (accumulate (lambda(this-coeff higher-terms)
                (+ this-coeff (* x higher-terms)))
              0 coefficient-sequence))
隻要記住lambda中的y其實是另一個遞歸的accumulate就比較容易完成了。
測試下:
> (horner-eval 2 (list 1 3 0 5 0 1))
 79

習題2.35，利用map和accumulate重新定義count-leaves統計樹的節點數目：
(define (count-leaves t)
  (accumulate + 0 (map (lambda (x) (if (pair? x) (count-leaves x) 1)) t)))
map過程的參數op是過程
(lambda (x) (if (pair? x) (count-leaves x) 1))
當x是列表，遞歸調用count-leaves，否則返回個數1

習題2.36，列表的列表，因此map過程的第一個參數是一個過程作用於列表中的每個列表，當然是采用car將它們首項取出然後進行op操作，因此：
(define (accumulate-n op init seqs)
  (if (null? (car seqs))
      ()
      (cons (accumulate op init (map car seqs))
            (accumulate-n op init (map cdr seqs)))))

習題2.37，list作為Lisp的基本結構可以演化出各式各樣的複雜結構，比如此題就將列表作為矢量，矢量通過組合成為矩陣，3個解答就是矩陣的運算：
(define (dot-product v w)
  (accumulate + 0 (map * v w)))
(define (matrix-*-vector m v)
  (map (lambda (x) (dot-product x v)) m))
(define (transpose mat)
  (accumulate-n cons () mat))
(define (matrix-*-matrix m n)
  (let ((cols (transpose n)))
    (map (lambda (x) (matrix-*-vector cols x)) m)))
知道矩陣運算的定義得出結果並不困難。

習題2.38，計算下結果：
> (fold-right / 1 (list 1 2 3))
1 1/2
;也就是3/2

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

如果想使這兩個過程的結果相同，op需要滿足交換率和結合率的條件。

習題2.39:
;2.39
(define (reverse-list sequence)
  (fold-right (lambda(x y)(append y (list x))) () sequence))
(define (reverse-list2 sequence)
  (fold-left (lambda(x y) (cons y x)) () sequence))
文章轉自莊周夢蝶  ，原文發布時間5.17

最後更新：2017-05-17 14:02:06

  上一篇：go  redhat9安裝jdk5、ruby和Erlang備忘
  下一篇：go  對org.springframework.beans.CachedIntrospectionResults的再次解讀