P04(*) 擷取清單的長度【重補】

Example:

sash> (my_length '(a b c d e))
sash> 
           

（1）自己造輪子

(define my_length
    (lambda (ls)
      (cond
        [(null? ls)]
        [else (+ (my_length (cdr ls)))])))
           

（2）使用

length

（3）延伸

跟Scheme中的清單定義不同，SRFI-1用一種廣義的視角定義了清單，将清單分為三種類型：

proper list

、

dotted list

、

circular list

，在Scheme中定義的清單實際上是”proper list”，那些非”proper list”的都不是清單。

我們要實作Scheme中的

list?

，可以反向思考：從清單中将

dotted list

、

circular list

排除就能得到

proper list

。

(define list?
  (lambda (x)
    (let f ([h x] [t x])
      (if (pair? h)
          (let ([h (cdr h)]) (if (pair? h) (if (eq? h t) #f (f (cdr h) (cdr t))) (if (null? h) #t #f)))
          (if (null? h) #t #f)))))
           

上述代碼判斷環的方法用了快慢兩個指針，步長分為2和1，若兩個指針相遇，則表示有環。

根據上面判斷清單的思路，可以把判斷清單的邏輯和擷取長度的邏輯合并在一起。代碼如下：

(define my_length
  (lambda (x)
    (let f ([h x] [t x] [n])
      (if (pair? h)
          (let ([h (cdr h)]) (if (pair? h) (if (eq? h t) (raise 'not-list) (f (cdr h) (cdr t) (+ n))) (if (null? h) (+ n) (raise 'not-list))))
          (if (null? h) n (raise 'not-list))))))
           

—–2015/12/23更新—–

用

reduce

實作：

(define my_length
    (lambda (ls)
      (fold-left
       (lambda (a e)
         (+ a))
       ls)))
           

使用

reduce

特别适合，暫時總結這3點：

- 需要周遊所有清單元素

- 不需要目前清單狀态資訊，比如目前位置、經過的元素數等

- 目前元素和accumulator之間的關系應有良好的定義

從這3點出發，像P01、P02、P03都不适合使用

reduce

解決，雖然可以結合函數閉包、continuation等技術實作。