リストの要素数を取得する


Tags: リスト, R6RS

リストの長さは length 手続きで調べることができる。

(import (rnrs))

(length '(1 2 3 4)) ; => 4

ただし、リストの構造を調べるような場合には length を使うよりも car, cdr, null? を使って構造を調べた方が効率がよい。例えばリストが if フォームとして適正な形をしているか調べる手続きを考える。

(import (rnrs))

(define (if? xs)
  (and (<= 3 (length xs) 4)
       (eq? (car xs) 'if)))

この場合、 length で長さを調べると、引数で与えられたリストの長さが大きい場合、余計な時間がかかってしまう。

(import (rnrs))

(define (if? xs)
  (and (pair? xs)
       (eq? (car xs) 'if)
       (not (null? (cdr xs)))
       (not (null? (cddr xs)))
       (or (null? (cdddr xs))
           (null? (cddddr xs)))))

とすれば引数のリストの長さにかかわらず定数時間で計算が終了する。

同じ理由で、リストが空かどうか調べるには length を使うよりも null? を使う方がよい。

(import (rnrs) (only (srfi :1) make-list))

;; fast version
(null? (make-list 5000000 0)) ; => #f
;; slow version
(zero? (length (make-list 5000000 0))) ; #f