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等技术实现。