% Function LIST-LENGTH
Function LIST-LENGTH
list-length list => length
list - 通常のリストか循環リスト
length - 非負の整数か、nil
listが通常のリストなら、listの長さを返却します。
listが循環リストなら、nilを返却します。
(list-length '(a b c d)) => 4
(list-length '(a (b c) d)) => 3
(list-length '()) => 0
(list-length nil) => 0
(defun circular-list (&rest elements)
(let ((cycle (copy-list elements)))
(nconc cycle cycle)))
(list-length (circular-list 'a 'b)) => NIL
(list-length (circular-list 'a)) => NIL
(list-length (circular-list)) => 0
なし。
なし。
listが通常のリストでも循環リストでもないときは、
型type-errorのエラーが発生します。
list-lengthは次のように実装できます。
(defun list-length (x)
(do ((n 0 (+ n 2)) ;カウンター。
(fast x (cddr fast)) ;Fastポインター: 2つ進める。
(slow x (cdr slow))) ;Slowポインター: 1つ進める。
(nil)
;; もしfastポインターが終了なら、カウントを返却する。
(when (endp fast) (return n))
(when (endp (cdr fast)) (return (+ n 1)))
;; もしfastポインターがslotポインターと同じなら
;; 循環リストから抜け出せていない。
;; （深い特性の話をすると：もし循環リストにはまったのなら
;; fastポインターはやがてslotポインターと等しくなるだろう。
;; このような事実がこの実装を正当化する。）
(when (and (eq fast slow) (> n 0)) (return nil))))