【Common Lisp】
リストの基本の使い方
（list）

by
  • Common Lisp のリストは list 関数かクォート ' で作り、car・cdr・nth で要素を取り出す。
  • loop for x in でリストを走査し、collect で新しいリストを作れる。
  • mapcar は各要素に関数を適用して新しいリストを返し、reduce は畳み込みで単一の値にする。
  • リストの実体はコンスセルの連鎖で、car が先頭要素、cdr が残りのリストを指す。
  • 繰り返しには loop・mapcar+reduce・再帰の3通りがあり、フラットなリストには loop か mapcar が自然。
用途関数
生成list、list*、make-list、cons、copy-list
アクセスcar、cdr、first〜tenth、nth、nthcdr、last、butlast
長さ・確認length、null、endp、listp、consp、atom
組み立てcons、append、nconc、list*
スタック操作push、pop
並べ替え・加工sort、stable-sort、reverse、nreverse、subseq
走査・変換mapcar、mapcan、mapc、reduce
フィルタremove、remove-if、remove-if-not、remove-duplicates
検索find、find-if、member、assoc、rassoc、position、position-if
条件判定every、some、notany、notevery
集計count、count-if
集合演算union、intersection、set-difference、adjoin
置換substitute、substitute-if
型変換coerce
alistassoc、rassoc、acons、pairlis
plistgetf、setf getf、remf

関連記事

1. リストを作ってループする

1.1. リストを作る（list）

Common Lisp のリストは、list 関数に要素を渡すだけで作れます。

(list 1 2 3)
;=> (1 2 3)

(list "alice" "bob" "carol")
;=> ("alice" "bob" "carol")Code language: Lisp (lisp)

要素が実行時に確定しているなら list を使い、コードに埋め込む定数なら ' でクォートします。

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

'("alice" "bob" "carol")
;=> ("alice" "bob" "carol")Code language: Lisp (lisp)

'(...) はリーダーマクロで、読み込み時にリストオブジェクトが確定します。
変数を混ぜても評価されないので、動的に値を含めたいときは list を使います1。

(defun make-range-list (start end)
  (list start end))

(make-range-list 10 20)
;=> (10 20)Code language: Lisp (lisp)

1.2. loop for-in でリストを走査する

リストの全要素に対して処理するには、loop の for x in 節を使います。

(defun print-roster (roster)
  (loop for name in roster
        do (format t "~a~%" name)))

(print-roster '("alice" "bob" "carol"))
; alice
; bob
; carolCode language: Lisp (lisp)

do は副作用だけ実行して nil を返します。
結果をリストにまとめたいときは collect を使います。

(defun name-lengths (words)
  (loop for word in words
        collect (length word)))

(name-lengths '("cat" "elephant" "dog"))
;=> (3 8 3)Code language: Lisp (lisp)

1.3. loop で条件を絞る（when）

when を組み合わせると、条件に合う要素だけ処理できます。

(defun long-words (words min-len)
  (loop for word in words
        when (>= (length word) min-len)
          collect word))

(long-words '("cat" "elephant" "dog" "butterfly") 4)
;=> ("elephant" "butterfly")Code language: Lisp (lisp)

2. リストの要素にアクセスする

ここまで、リストをリスト全体として扱いました。
もちろん、リスト内の要素を扱うこともできます。

2.1. car と cdr で先頭と残りを取り出す

リストの先頭要素は car、残りのリストは cdr で取り出します。

(defun first-word (words)
  (car words))

(first-word '("alice" "bob" "carol"))
;=> "alice"Code language: Lisp (lisp)
(defun rest-words (words)
  (cdr words))

(rest-words '("alice" "bob" "carol"))
;=> ("bob" "carol")Code language: Lisp (lisp)

car と cdr という名前は歴史的なもので、IBM 704 のレジスタ名に由来します2。
現代のコードでは first と rest という別名も使えます。
どちらを使っても動作は同じです3。

(first '("alice" "bob" "carol"))  ;=> "alice"
(rest  '("alice" "bob" "carol"))  ;=> ("bob" "carol")Code language: Lisp (lisp)

cdr を重ねると先頭から順に剥がせます。
cadr は (car (cdr ...)) の短縮形で、2番目の要素を返します4。

(defun second-word (words)
  (cadr words))

(second-word '("alice" "bob" "carol"))
;=> "bob"Code language: Lisp (lisp)

同様に caddr が3番目、cadddr が4番目です。
5番目以降は nth を使う方が読みやすくなります。

2.2. nth で n 番目の要素を取り出す

nth は 0 始まりのインデックスで要素を返します。

(defun get-player (roster n)
  (nth n roster))

(get-player '("alice" "bob" "carol" "dave") 2)
;=> "carol"Code language: Lisp (lisp)

範囲外のインデックスを渡すとエラーではなく nil が返ります。
ベクタの aref と違い、リストを先頭からたどるため O(N) になります5。

2.3. length で長さを得る

(defun count-players (roster)
  (length roster))

(count-players '("alice" "bob" "carol"))
;=> 3Code language: Lisp (lisp)

2.4. loop でインデックスと要素を同時に扱う

for i from 1 と for x in を並べると、インデックスと要素を同時に取り出せます6。

(defun print-indexed (items)
  (loop for i from 1
        for item in items
        do (format t "~a: ~a~%" i item)))

(print-indexed '("alice" "bob" "carol"))
; 1: alice
; 2: bob
; 3: carolCode language: Lisp (lisp)

3. 高階関数によるリスト操作

3.1. mapcar で各要素を変換する

mapcar はリストの各要素に関数を適用し、結果を新しいリストにして返します。
元のリストは変更しません。

(defun normalize-scores (scores)
  (mapcar (lambda (s) (* s 1.0)) scores))

(normalize-scores '(80 90 70 85 95))
;=> (80.0 90.0 70.0 85.0 95.0)Code language: Lisp (lisp)

loop の collect と対応していて、同じ処理をこう書き換えられます。

; mapcar 版
(mapcar (lambda (s) (* s 1.0)) '(80 90 70))

; loop 版
(loop for s in '(80 90 70)
      collect (* s 1.0))Code language: Lisp (lisp)

複数のリストを同時に処理することもできます。
リストの長さが異なる場合は、短い方に合わせて終了します7。

(defun add-lists (a b)
  (mapcar #'+ a b))

(add-lists '(1 2 3) '(10 20 30))
;=> (11 22 33)Code language: Lisp (lisp)

3.2. reduce で畳み込む

reduce はリストの要素を二項演算で順に畳み込み、単一の値を返します。

(defun total-score (scores)
  (reduce #'+ scores))

(defun highest-score (scores)
  (reduce #'max scores))

(total-score '(80 90 70 85 95))
;=> 420

(highest-score '(80 90 70 85 95))
;=> 95Code language: Lisp (lisp)

lambdaを使うと、第一引数が累積値、第二引数が現在の要素です。

(defun even-total (scores)
  (reduce (lambda (acc x)
            (if (evenp x)
                (+ acc x)
                acc))
          scores
          :initial-value 0))

(even-total '(80 91 70 85 95))
;=> 150Code language: Lisp (lisp)

:initial-value を渡すと、リストが空のときの初期値を指定できます8。

(defun safe-total (scores)
  (reduce #'+ scores :initial-value 0))

(safe-total '())
;=> 0Code language: Lisp (lisp)

:from-end t を渡すと末尾から畳み込みます。
+ や max のような可換な演算では結果は変わりませんが、- のように結合順序が影響する場合は違いが出ます。

(reduce #'- '(10 3 2 1))
;=> 4    ; ((10 - 3) - 2) - 1

(reduce #'- '(10 3 2 1) :from-end t)
;=> 6    ; 10 - (3 - (2 - 1))Code language: Lisp (lisp)

4. 再帰によるリスト操作

4.1. コンスセルの構造

リストの実体は、コンスセルと呼ばれるペアの連鎖です9。
コンスセルは car（先頭）と cdr（残り）の2つのポインタを持ちます。

(1 2 3 4) の内部構造

[1 | ●]──→[2 | ●]──→[3 | ●]──→[4 | nil]
 car  cdr    car  cdr    car  cdr    car  cdrCode language: CSS (css)

car は先頭の値を指し、cdr は次のコンスセルを指します。
末尾のコンスセルの cdr は nil になっています。

この構造から、リストの性質が決まります。
先頭への追加や削除は O(1) ですが、n番目の要素に到達するには先頭からたどるため O(N) になります。

; cons で先頭に要素を追加する
(cons 0 '(1 2 3))
;=> (0 1 2 3)

; car/cdr でコンスセルを確認する
(car (cons 10 '(20 30)))
;=> 10

(cdr (cons 10 '(20 30)))
;=> (20 30)Code language: Lisp (lisp)

cons は新しいコンスセルを1つ作ります。
既存のリストは変更せず、先頭に要素を追加した新しいリストを返します。

4.2. null・endp でリストを確認する

リストが空かどうかは null で確認します。

nil と空リスト '() は Common Lisp では同じオブジェクトなので、null は nil かどうかを調べる関数でもあります10。

(defun summarize (items)
  (if (null items)
      "リストが空です"
      (format nil "~a 件あります" (length items))))

(summarize '())
;=> "リストが空です"

(summarize '("alice" "bob"))
;=> "2 件あります"Code language: Lisp (lisp)

endp もリストの末尾判定に使えます。
null と結果は同じですが、リスト以外を渡すとエラーになるため、「リストの末尾チェックである」という意図を明示したいときに選びます11。

(null '())  ;=> T
(endp '())  ;=> T
(null nil)  ;=> T
(endp nil)  ;=> TCode language: Lisp (lisp)

4.3. アトムかリストか atom・listp・consp

carやlengthを使う前提として、引数がリストかどうかを確認するときもあります。

atom はリスト（コンスセル）でないオブジェクトかどうかを確認します。
consp の逆で、数値・シンボル・文字列・nil はすべて atom が t を返します。

(atom 42)       ;=> T
(atom :keyword) ;=> T
(atom nil)      ;=> T   ; nil はアトムでもある
(atom '(1 2))   ;=> NILCode language: Lisp (lisp)

再帰的にリストを処理する関数で「先頭がアトムかリストか」を分岐するときに atom が使われます。

listp を使います。

ただし、nil もリストとみなされるため (listp nil) は t を返します12。

(defun safe-first (x)
  (if (listp x)
      (car x)
      x))

(safe-first '(1 2 3))  ;=> 1
(safe-first 42)        ;=> 42
(safe-first '())       ;=> NILCode language: Lisp (lisp)

consp は空でないリスト、つまり cons オブジェクトかどうかを確認します。
listp と異なり nil には nil を返すため、「空でないリストかどうか」を調べるときに使います。

(listp '())   ;=> T
(consp '())   ;=> NIL

(listp '(1 2))  ;=> T
(consp '(1 2))  ;=> TCode language: Lisp (lisp)

4.4. 再帰による繰り返し

このようなリストの基本操作を使うと、再帰によって繰り返し処理を書くことができます。

たとえば、リストの各要素を二乗した新しいリストを返す関数は、

(defparameter *nums* '(1 2 3 4 5))

(defun squares-rec (nums)
  (if (null nums)
      '()
      (cons (* (car nums) (car nums))
            (squares-rec (cdr nums)))))

(squares-rec *nums*)     ;=> (1 4 9 16 25)Code language: Lisp (lisp)

同じ処理は、loop・mapcarでも書けます。

; loop 版
(defun squares-loop (nums)
  (loop for n in nums
        collect (* n n)))

; mapcar 版
(defun squares-mapcar (nums)
  (mapcar (lambda (n) (* n n)) nums))

(squares-loop *nums*)    ;=> (1 4 9 16 25)
(squares-mapcar *nums*)  ;=> (1 4 9 16 25)Code language: Lisp (lisp)

4.5. 再帰的なデータ構造と再帰関数

Lispの基本は、再帰だと思いますが、フラットなリストに対しては、loop か mapcar でも自然で読みやすいかもしれません。

再帰がもっとも力を発揮するのは、データ構造自体が再帰的な場合です。
たとえば、ネストしたリストを並列にするときは、再帰による解決が自然です。

(defun flatten (lst)
  (cond
    ((null lst) '())
    ((listp (car lst))
     (append (flatten (car lst)) (flatten (cdr lst))))
    (t
     (cons (car lst) (flatten (cdr lst))))))

(flatten '(1 (2 3) (4 (5 6))))
;=> (1 2 3 4 5 6)Code language: Lisp (lisp)

ただし、このコードは、append を再帰的に呼ぶため非効率です。

Common Lisp では末尾再帰の最適化が言語仕様として保証されていません13。
深いリストに再帰を使うとスタックが溢れる可能性があるため、スタックの深さが気になる場面では loop を選ぶほうが安全です。

5. 生成とアクセス

5.1. make-list で同じ値のリストを作る

make-list は指定した長さのリストを作り、全要素を :initial-element で指定した値で埋めます。

(defun make-score-list (n)
  (make-list n :initial-element 0))

(make-score-list 5)
;=> (0 0 0 0 0)Code language: Lisp (lisp)

:initial-element を省略すると全要素が nil になります14。

(make-list 3)
;=> (NIL NIL NIL)Code language: Lisp (lisp)

5.2. list* で末尾にリストをつなげる

list* は list に似ていますが、最後の引数をそのままリストの末尾につなげます。
先頭に要素を足しながら既存のリストを保持したいときに使います。

(defun prepend-header (header items)
  (list* header items))

(prepend-header :scores '(80 90 70))
;=> (:SCORES 80 90 70)Code language: Lisp (lisp)

(list* a b c lst) は (cons a (cons b (cons c lst))) と同じ結果になります15。
list との違いはこう確認できます。

(list  1 2 '(3 4))   ;=> (1 2 (3 4))
(list* 1 2 '(3 4))   ;=> (1 2 3 4)Code language: Lisp (lisp)

5.3. last と butlast で末尾を扱う

last はリストの末尾のコンスセルを返します。
要素そのものではなくコンスセルなので、car で取り出す必要があります16。

(defun last-player (roster)
  (car (last roster)))

(last-player '("alice" "bob" "carol"))
;=> "carol"Code language: Lisp (lisp)

省略可能な第2引数で、末尾から何個分のコンスセルを返すか指定できます。

(last '(1 2 3 4 5) 2)
;=> (4 5)Code language: Lisp (lisp)

butlast は末尾の n 要素を除いたリストを返します。
デフォルトは1つ除きます。

(defun drop-last (items)
  (butlast items))

(drop-last '("alice" "bob" "carol"))
;=> ("alice" "bob")

(butlast '(1 2 3 4 5) 2)
;=> (1 2 3)Code language: Lisp (lisp)

5.4. nthcdr で n 番目以降のリストを得る

nthcdr は cdr を n 回適用した結果を返します。
n 番目以降のリストを取り出すのに使います。

(defun drop-first-n (items n)
  (nthcdr n items))

(drop-first-n '(1 2 3 4 5) 2)
;=> (3 4 5)Code language: Lisp (lisp)

(nth n lst) は (car (nthcdr n lst)) と同じです。
nthcdr はリストの後半を丸ごと渡したいときに nth より自然に使えます17。

5.5. copy-list でリストをコピーする

copy-list はリストのトップレベルの構造だけをコピーして新しいリストを返します。
sort や nreverse のような破壊的操作を元のリストに影響を与えずに使いたいときに使います。

(defun safe-sort (items)
  (sort (copy-list items) #'<))

(defparameter *scores* '(80 95 70 85 90))
(safe-sort *scores*)
;=> (70 80 85 90 95)

*scores*
;=> (80 95 70 85 90)   ; 元のリストは変わらないCode language: Lisp (lisp)

copy-list は浅いコピーです。トップレベルのコンスセルは新しく作られますが、各要素が指すオブジェクトは元のリストと共有されます18。

; 要素がリストの場合、浅いコピーの影響が出る例
(defparameter *nested* (list (list 1 2) (list 3 4)))
(defparameter *copied* (copy-list *nested*))

(push 99 (car *copied*))   ; コピーの先頭要素（リスト）を変更

*copied*   ;=> ((99 1 2) (3 4))
*nested*   ;=> ((99 1 2) (3 4))   ; 元も変わってしまうCode language: Lisp (lisp)

要素が数値・シンボル・文字列など不変のオブジェクトだけで構成されているリストでは、この共有は問題になりません。
要素そのものも独立したコピーが必要な場合は、再帰的にコピーする関数を自前で書く必要があります。

subseq も同様に浅いコピーを返します。
切り出した範囲の新しいリストが作られますが、各要素は元と同じオブジェクトを指します。

6. 組み立てと加工

6.1. append でリストを連結する

append は複数のリストを連結して新しいリストを返します。
元のリストは変更しません。

(defun merge-rosters (home away)
  (append home away))

(merge-rosters '("alice" "bob") '("carol" "dave"))
;=> ("alice" "bob" "carol" "dave")Code language: Lisp (lisp)

3つ以上も連結できます。

(append '(1 2) '(3 4) '(5 6))
;=> (1 2 3 4 5 6)Code language: Lisp (lisp)

引数が1つのときはそのリストをそのまま返します。
引数が0のときは nil を返します。

ただし、append は最後の引数以外のリストを走査してコピーするため、長いリストを何度も append するとコストが積み重なります19。
先頭への cons を積み重ねてから最後に reverse する方が効率的です。

; 非効率（append を繰り返す）
(defun build-bad (n)
  (loop for i from 1 to n
        for acc = '() then (append acc (list i))
        finally (return acc)))

; 効率的（cons で先頭に積んでから nreverse）
(defun build-good (n)
  (let ((acc '()))
    (loop for i from 1 to n
          do (push i acc))
    (nreverse acc)))Code language: Lisp (lisp)

6.2. nconc で破壊的に連結する

nconc は append の破壊的版で、最後の引数以外のリストの末尾を直接書き換えて連結します。
新しいコンスセルを作らない分メモリ効率がよい場合がありますが、元のリストが変更されます。

(defparameter *a* (list 1 2 3))
(defparameter *b* (list 4 5 6))

(nconc *a* *b*)
;=> (1 2 3 4 5 6)

*a*
;=> (1 2 3 4 5 6)   ; *a* 自体が変わっているCode language: Lisp (lisp)

'(1 2 3) のようなリテラルリストに nconc を使うと動作が未定義になります20。
list や copy-list で作ったリストに対して使います。

6.3. push と pop でスタック操作をする

push はリストの先頭に要素を追加し、pop は先頭要素を取り出します。
どちらも変数を直接変更する破壊的な操作です。

(defparameter *stack* '())

(push 1 *stack*)   ;=> (1)
(push 2 *stack*)   ;=> (2 1)
(push 3 *stack*)   ;=> (3 2 1)

(pop *stack*)      ;=> 3
*stack*            ;=> (2 1)Code language: Lisp (lisp)

push は (setf var (cons item var)) の短縮形です21。
後入れ先出しのスタックとして使うのが典型的な用途です。

(defun reverse-with-stack (items)
  (let ((stack '()))
    (loop for item in items
          do (push item stack))
    stack))

(reverse-with-stack '(1 2 3 4 5))
;=> (5 4 3 2 1)Code language: Lisp (lisp)

6.4. reverse と nreverse で逆順にする

reverse は元のリストを変更せず、逆順の新しいリストを返します。

(defun reversed-ranking (scores)
  (reverse scores))

(reversed-ranking '(95 85 80 70))
;=> (70 80 85 95)Code language: Lisp (lisp)

nreverse は破壊的版で、元のリストを書き換えて逆順にします。
新しいリストを作らないためメモリ効率がよく、元のリストを以後使わない場面で選びます22。

(defun reverse-in-place! (items)
  (nreverse items))

(let ((buf (list 1 2 3 4 5)))
  (reverse-in-place! buf))
;=> (5 4 3 2 1)Code language: Lisp (lisp)

返り値を必ず受け取って使います。nreverse を呼び出した後に元の変数を参照すると、内容が変わっているか未定義の状態になっている可能性があります。

; 安全な使い方
(defun build-reversed (items)
  (let ((result (copy-list items)))
    (setf result (nreverse result))
    result))Code language: Lisp (lisp)

6.5. sort と stable-sort で並べ替える

sort はリストをソートしますが、元のリストを破壊的に変更します。
元のリストを保持したいときは copy-list してから渡します23。

(defun top-scores (scores)
  (sort (copy-list scores) #'>))

(top-scores '(80 95 70 85 90))
;=> (95 90 85 80 70)Code language: Lisp (lisp)

stable-sort は同値要素の元の順序を保ちます。
sort は同値要素の順序を保証しません24。

(defparameter *players*
  '(("alice" 85) ("bob" 90) ("carol" 85) ("dave" 90)))

(stable-sort (copy-list *players*)
             #'> :key #'cadr)
;=> (("bob" 90) ("dave" 90) ("alice" 85) ("carol" 85))Code language: Lisp (lisp)

:key に関数を渡すと、その関数の戻り値で比較します。

6.6. subseq でスライスする

subseq は開始インデックスから終了インデックスの手前までを切り出して新しいリストを返します。

(defun top-three (ranking)
  (subseq ranking 0 3))

(top-three '("alice" "bob" "carol" "dave" "eve"))
;=> ("alice" "bob" "carol")Code language: Lisp (lisp)

終了インデックスを省略すると末尾まで取り出します。

(subseq '(1 2 3 4 5) 2)
;=> (3 4 5)Code language: Lisp (lisp)

7. 検索・判定・フィルタ

7.1. find と find-if で要素を探す

find は最初に一致した要素を返し、見つからなければ nil を返します。

(defun find-score (scores target)
  (find target scores))

(find-score '(80 90 70 85 95) 70)
;=> 70

(find-score '(80 90 70 85 95) 60)
;=> NILCode language: Lisp (lisp)

find-if は条件関数を受け取り、最初に条件を満たした要素を返します。

(defun find-passing (scores passing-mark)
  (find-if (lambda (s) (>= s passing-mark)) scores))

(find-passing '(80 90 70 85 95) 90)
;=> 90Code language: Lisp (lisp)

:key で比較前に各要素に適用する関数を指定できます25。

(defparameter *players*
  '(("alice" 85) ("bob" 90) ("carol" 70)))

(find "bob" *players* :key #'car :test #'equal)
;=> ("bob" 90)Code language: Lisp (lisp)

7.2. member でリストを検索する

member は一致した要素以降のリストを返し、見つからなければ nil を返します。
find が要素そのものを返すのに対し、member は残りのリストを返す点が違います26。

(defun member-p (items target)
  (if (member target items) t nil))

(member-p '(80 90 70 85 95) 70)
;=> TCode language: Lisp (lisp)

member はデフォルトで eql で比較します。
文字列のように eql では比較できないものは :test を指定します27。

(member "bob" '("alice" "bob" "carol") :test #'equal)
;=> ("bob" "carol")Code language: Lisp (lisp)

7.3. remove・remove-if でフィルタする

remove は指定した値と一致する要素を除いた新しいリストを返します。

(defun remove-score (scores target)
  (remove target scores))

(remove-score '(80 90 70 90 95) 90)
;=> (80 70 95)Code language: Lisp (lisp)

remove-if は条件を満たす要素を除きます。
remove-if-not は条件を満たさない要素を除きます。どちらも元のリストは変更しません。

(defun failing-scores (scores passing-mark)
  (remove-if (lambda (s) (>= s passing-mark)) scores))

(defun passing-scores (scores passing-mark)
  (remove-if-not (lambda (s) (>= s passing-mark)) scores))

(failing-scores '(80 90 70 85 95) 85)
;=> (80 70)

(passing-scores '(80 90 70 85 95) 85)
;=> (85 95)Code language: Lisp (lisp)

:count で除く件数を制限できます。

(remove 90 '(80 90 70 90 95) :count 1)
;=> (80 70 90 95)Code language: Lisp (lisp)

7.4. every・some・notany・notevery で条件を判定する

every は全要素が条件を満たすとき t を返します。
some は少なくとも1つが条件を満たすとき、その要素を返します。
いずれも条件が確定した時点で走査を打ち切ります28。

(defun all-passing-p (scores passing-mark)
  (every (lambda (s) (>= s passing-mark)) scores))

(all-passing-p '(80 90 70 85 95) 60)  ;=> T
(all-passing-p '(80 90 70 85 95) 75)  ;=> NILCode language: Lisp (lisp)
(defun any-perfect-p (scores)
  (some (lambda (s) (= s 100)) scores))

(any-perfect-p '(80 100 70 85 95))  ;=> 100
(any-perfect-p '(80 90 70 85 95))   ;=> NILCode language: Lisp (lisp)

notany は1つも条件を満たさないとき t を返し、notevery は少なくとも1つが条件を満たさないとき t を返します。
Ruby の none?・any? に対応します29。

(notany  #'zerop '(1 2 3))   ;=> T    ; 0が1つもない
(notevery #'oddp '(1 2 3))   ;=> T    ; 奇数でないものがあるCode language: Lisp (lisp)

7.5. count と count-if で数える

count は一致する要素の個数を返します。
count-if は条件を満たす要素の個数を返します。

(defun count-passing (scores passing-mark)
  (count-if (lambda (s) (>= s passing-mark)) scores))

(count-passing '(80 90 70 85 95) 85)
;=> 2Code language: Lisp (lisp)
(count 90 '(80 90 70 90 95))
;=> 2Code language: Lisp (lisp)

7.6. position と position-if でインデックスを得る

要素そのものではなくインデックスが欲しいときは position を使います。
見つからない場合は nil を返します。

(defun index-of (items target)
  (position target items))

(index-of '(80 90 70 85 95) 85)
;=> 3Code language: Lisp (lisp)

position-if は条件関数を受け取ります。

(defun first-failing-index (scores passing-mark)
  (position-if (lambda (s) (< s passing-mark)) scores))

(first-failing-index '(80 90 70 85 95) 75)
;=> 2Code language: Lisp (lisp)

8. 変換・構造・実践

8.1. mapcan で変換しながら連結する

mapcar が各要素の変換結果をリストにまとめるのに対し、mapcan は各結果のリストを連結します。
1対多の変換、つまり1つの要素から複数の要素を生成したいときに使います。

(defun expand-range (pair)
  (loop for i from (car pair) to (cadr pair)
        collect i))

(mapcan #'expand-range '((1 3) (6 8)))
;=> (1 2 3 6 7 8)Code language: Lisp (lisp)

mapcar で同じことをすると結果がネストします。

(mapcar #'expand-range '((1 3) (6 8)))
;=> ((1 2 3) (6 7 8))Code language: Lisp (lisp)

mapcan は内部的に nconc を使うため、変換関数が返すリストを破壊的に連結します。
リテラルリストを返さないように注意が必要です30。

8.2. mapc で副作用だけ実行する

mapc は mapcar と同じく各要素に関数を適用しますが、結果のリストを作らず元のリストをそのまま返します。
変換結果が不要で副作用だけ実行したいときに選びます31。

(defun log-scores (scores)
  (mapc (lambda (s)
          (format t "score: ~a~%" s))
        scores))

(log-scores '(80 90 70))
; score: 80
; score: 90
; score: 70
;=> (80 90 70)Code language: Lisp (lisp)

loop for x in ... do と対応していて、こちらはより関数型のスタイルです。

8.3. coerce でリストを変換する

coerce はシーケンスの型を変換します。
リストをベクタや文字列に変換したいときに使います32。

(defun list->vector (lst)
  (coerce lst 'vector))

(list->vector '(1 2 3 4 5))
;=> #(1 2 3 4 5)Code language: Lisp (lisp)
(defun chars->string (chars)
  (coerce chars 'string))

(chars->string '(#\h #\e #\l #\l #\o))
;=> "hello"Code language: Lisp (lisp)

ベクタやシーケンスをリストに戻すこともできます。

(coerce #(1 2 3) 'list)
;=> (1 2 3)

(coerce "hello" 'list)
;=> (#\h #\e #\l #\l #\o)Code language: Lisp (lisp)

8.4. alist で辞書的なデータを扱う

alist はキーと値のペアをコンスセルにしたリストです。
(key . value) という形のコンスセルを並べます。

(defparameter *config*
  '((:host . "localhost")
    (:port . 8080)
    (:debug . t)))Code language: Lisp (lisp)

assoc でキーに対応するコンスセルを返します。
値だけ欲しいときは cdr で取り出します。

(defun get-config (config key)
  (cdr (assoc key config)))

(get-config *config* :port)
;=> 8080

(get-config *config* :missing)
;=> NILCode language: Lisp (lisp)

assoc はデフォルトで eql で比較します。
文字列キーには :test #'equal が必要です33。

(defparameter *env*
  '(("HOST" . "localhost") ("PORT" . "8080")))

(assoc "HOST" *env* :test #'equal)
;=> ("HOST" . "localhost")Code language: Lisp (lisp)

rassoc はキーではなく値で検索します。

(rassoc 8080 *config*)
;=> (:PORT . 8080)Code language: Lisp (lisp)

acons はキーと値のペアをalistの先頭に追加した新しいalistを返します。
(cons (cons key value) alist) の短縮形です。

(defun add-entry (alist key value)
  (acons key value alist))

(add-entry *config* :timeout 30)
;=> ((:TIMEOUT . 30) (:HOST . "localhost") (:PORT . 8080) (:DEBUG . T))Code language: Lisp (lisp)

pairlis はキーのリストと値のリストからalistを作ります。
2つのリストを対応付けるときに使います。

(pairlis '(:name :score :level) '("alice" 85 3))
;=> ((:LEVEL . 3) (:SCORE . 85) (:NAME . "alice"))   ; 順序は実装依存Code language: Lisp (lisp)

8.5. plist でプロパティリストを扱う

plist はキーと値を交互に並べたフラットなリストです。
alist より書き方が簡単で、Lispのシンボルプロパティやキーワード引数でよく使われます34。

(defparameter *player*
  '(:name "alice" :score 85 :level 3))Code language: Lisp (lisp)

getf でキーに対応する値を返します。

(defun player-score (player)
  (getf player :score))

(player-score *player*)
;=> 85Code language: Lisp (lisp)

値が見つからないときのデフォルト値を第3引数で指定できます。

(getf *player* :rank 999)
;=> 999Code language: Lisp (lisp)

setf getf で値を更新します。破壊的な操作です。

(setf (getf *player* :score) 90)
*player*
;=> (:NAME "alice" :SCORE 90 :LEVEL 3)Code language: Lisp (lisp)

alist との使い分けの目安はこうなります。
キーワード引数の受け渡しや小さな設定データには plist が手軽です。
検索・更新・削除が多く、キーが動的に決まる場合は alist か、ハッシュテーブルを選びます35。

remf は plist からキーとそれに対応する値を取り除きます。破壊的な操作で、変数を直接書き換えます。

(defparameter *player* '(:name "alice" :score 85 :level 3))

(remf *player* :level)
*player*
;=> (:NAME "alice" :SCORE 85)Code language: Lisp (lisp)

8.6. 集合演算

Common Lisp はリストを集合として扱う関数を標準で持っています。

union は2つのリストの和集合を返します。重複は除かれます36。

(union '(1 2 3) '(2 3 4 5))
;=> (1 2 3 4 5)   ; 順序は実装依存Code language: Lisp (lisp)

intersection は積集合、set-difference は差集合を返します。

(intersection '(1 2 3 4) '(2 4 6))
;=> (2 4)

(set-difference '(1 2 3 4) '(2 4 6))
;=> (1 3)Code language: Lisp (lisp)

これらはデフォルトで eql で比較します。
文字列など equal が必要なときは :test #'equal を渡します。

(intersection '("alice" "bob" "carol")
              '("bob" "dave")
              :test #'equal)
;=> ("bob")Code language: Lisp (lisp)

remove-duplicates は重複要素を除いたリストを返します37。

(remove-duplicates '(1 2 1 3 2 4))
;=> (1 3 2 4)   ; デフォルトは後ろの重複を残す

(remove-duplicates '(1 2 1 3 2 4) :from-end t)
;=> (1 2 3 4)   ; 先頭側を残すCode language: Lisp (lisp)

adjoin は要素がまだリストに含まれていなければ先頭に追加し、含まれていればリストをそのまま返します。
集合にまだない要素だけを追加したいときに使います。

(defun add-unique (items new-item)
  (adjoin new-item items))

(add-unique '(1 2 3) 4)  ;=> (4 1 2 3)
(add-unique '(1 2 3) 2)  ;=> (1 2 3)   ; すでに含まれているので変化なしCode language: Lisp (lisp)

文字列には :test #'equal が必要です。

(adjoin "bob" '("alice" "carol") :test #'equal)
;=> ("bob" "alice" "carol")

(adjoin "alice" '("alice" "carol") :test #'equal)
;=> ("alice" "carol")Code language: Lisp (lisp)

8.7. substitute と substitute-if で置換する

substitute は値を指定して一致する要素を別の値に置き換えた新しいリストを返します。
元のリストは変更しません。

(defun replace-score (scores old new)
  (substitute new old scores))

(replace-score '(80 90 70 90 95) 90 100)
;=> (80 100 70 100 95)Code language: Lisp (lisp)

substitute-if は条件を満たす要素を置き換えます。

(defun cap-scores (scores limit)
  (substitute-if limit (lambda (s) (> s limit)) scores))

(cap-scores '(80 110 70 85 120) 100)
;=> (80 100 70 85 100)Code language: Lisp (lisp)

:count で置換する件数を制限できます。
破壊的に書き換えたいときは nsubstitute・nsubstitute-if を使います。

(substitute 100 90 '(80 90 70 90 95) :count 1)
;=> (80 100 70 90 95)   ; 最初の1件だけ置換Code language: Lisp (lisp)

9. 実践パターン

9.1. 標準入力からリストを読み込む

read は標準入力から1トークン読みます。
要素数が実行前に決まらない場合も collect で動的に積み上げられます。

(defun read-int-list (n)
  (loop repeat n
        collect (read)))

; 入力: 1 2 3 4 5
; (read-int-list 5)
;=> (1 2 3 4 5)Code language: Lisp (lisp)

9.2. 頻度カウント（事前にサイズが決まらない集計）

要素の出現回数を alist で集計します。
キーの種類が実行前に決まらないため、ベクタより alist が自然な選択です38。

(defun count-freq (items)
  (loop for item in items
        for cell = (assoc item acc :test #'equal)
        with acc = '()
        if cell
          do (incf (cdr cell))
        else
          do (push (cons item 1) acc)
        finally (return acc)))

(count-freq '("a" "b" "a" "c" "b" "a"))
;=> (("c" . 1) ("b" . 2) ("a" . 3))Code language: Lisp (lisp)

9.3. グループ化（条件で振り分ける）

1つのリストを条件で2つに振り分けます。
中間リストを動的に構築するため、ベクタのように事前にサイズを確保する必要がありません39。

(defun partition-by (pred items)
  (loop for item in items
        if (funcall pred item)
          collect item into yes
        else
          collect item into no
        finally (return (list yes no))))

(partition-by #'evenp '(1 2 3 4 5 6 7 8))
;=> ((2 4 6 8) (1 3 5 7))Code language: Lisp (lisp)

9.4. 隣接ペアで走査する

loop の on 節はリストの残り部分（cdr 相当）を順に取り出します40。
(car ...) と (cadr ...) を組み合わせると隣接する2要素をペアで処理できます。
差分計算や単調増加の検証など、前後の要素を比較したい場面で使います。

(defun differences (nums)
  (loop for (a b) on nums
        while b
        collect (- b a)))

(differences '(1 3 6 10 15))
;=> (2 3 4 5)Code language: Lisp (lisp)
(defun sorted-p (items)
  (loop for (a b) on items
        while b
        always (<= a b)))

(sorted-p '(1 3 5 7 9))  ;=> T
(sorted-p '(1 3 2 7 9))  ;=> NILCode language: Lisp (lisp)

9.5. zip と unzip

2つのリストを組み合わせて対のリストを作る zip と、その逆の unzip です。
mapcar に複数のリストを渡す形で zip が書けます41。

(defun zip (keys values)
  (mapcar #'cons keys values))

(zip '(:name :score :level)
     '("alice" 85 3))
;=> ((:NAME . "alice") (:SCORE . 85) (:LEVEL . 3))Code language: Lisp (lisp)

unzip は alist をキーと値に分解します。

(defun unzip (pairs)
  (list (mapcar #'car pairs)
        (mapcar #'cdr pairs)))

(unzip '((:name . "alice") (:score . 85) (:level . 3)))
;=> ((:NAME :SCORE :LEVEL) ("alice" 85 3))Code language: Lisp (lisp)

9.6. 重複を除いて並べ替える

(defun unique-sorted (items)
  (sort (remove-duplicates (copy-list items)) #'<))

(unique-sorted '(3 1 4 1 5 9 2 6 5 3))
;=> (1 2 3 4 5 6 9)Code language: Lisp (lisp)
  1. '(1 2 3) のようなリテラルリストはコンパイラが同じオブジェクトを再利用する可能性があり、変更は未定義動作になります。変更する可能性があるリストは必ず list か copy-list で作ります。 – CLHS: 2.4.1 Quote
  2. car は “Contents of the Address part of Register”、cdr は “Contents of the Decrement part of Register” の略です。IBM 704 の 36 ビットワードのアドレス部とデクリメント部にリストのポインタを格納したことに由来します。実装者の Steve Russell は後に「first と rest の方がよい名前だったと気づいたが、変更するには遅すぎた」と述べています。 – CAR and CDR – Wikipedia
  3. first〜tenth まで順番にアクセスする別名が標準で定義されています。alistのようにコンスセルをペアとして使う場面では car/cdr の方が意図を正確に伝えるという考え方もあります。 – CLHS: Function FIRST, SECOND…
  4. Common Lisp では caar、cadr、cdar、cddr から始まり、最大4段まで cXXXXr の形の組み合わせが標準で定義されています。5段以上が必要な場合は nth か nthcdr を使う方が読みやすくなります。 – CLHS: Function CAAR, CADR…
  5. (nth n list) は内部的に (car (nthcdr n list)) と同等です。n 番目の要素に到達するまで cdr を n 回たどるためコストは O(N) になります。頻繁にインデックスアクセスするなら coerce でベクタに変換する方が効率的です。 – CLHS: Function NTH
  6. 複数の for 節を並べると、いずれかのリストが尽きた時点でループ全体が終了します。for i from 1 には終端がないので、for item in items のリストが尽きた時点で停止します。 – CLHS: Section 6.1.2.1 Iteration Control
  7. 複数リストを受け取る場合、最も短いリストが尽きた時点で処理を打ち切り、余分な要素は無視されます。これは mapcar の仕様で定められています。 – CLHS: Function MAPCAR
  8. :initial-value を指定しない場合、リストが空だとエラーになります。また要素が1つの場合は関数を呼ばずにその要素をそのまま返します。安全のため、合計や積のような演算では常に :initial-value を指定する習慣が推奨されます。 – CLHS: Function REDUCE
  9. cons という名前は “construct” に由来し、メモリ上に2つのポインタを持つ構造体を作る操作です。car と cdr の2つのポインタで構成され、任意のオブジェクトを指せます。 – cons – Wikipedia
  10. Common Lisp では nil、'()、false がすべて同一のオブジェクトです。(null x) は (not x) と同じ結果を返しますが、リストの空チェックであるという意図を示すために null を使うのが慣例です。 – CLHS: Function NULL
  11. CLHSは「endp の目的は proper list の末尾を判定することである」と定義しています。実際のコードでは null の方が頻繁に使われますが、再帰関数の終了条件を書くときに endp を選ぶとリストを前提とした処理だと読み手に伝わります。 – CLHS: Function ENDP
  12. listp は nil または cons オブジェクトであれば t を返します。consp は cons オブジェクトだけに t を返すため、空でないリストかどうかを確認したい場合は consp を使います。 – CLHS: Function LISTP
  13. Scheme は仕様として末尾呼び出しの最適化を要求しますが、Common Lisp はそれを要求しません。SBCL は特定条件下でTCO（Tail Call Optimization）を行いますが、デフォルト設定やデバッグモードでは無効になる場合があります。移植性のあるコードでは loop を使う方が安全です。 – Tail Call Optimisation in Common Lisp Implementations
  14. make-list の :initial-element を省略した場合の初期値は仕様上保証されていません。多くの実装では nil になりますが、移植性のあるコードでは明示的に指定する方が安全です。 – CLHS: Function MAKE-LIST
  15. list* は引数が1つのとき、その引数をそのまま返します。最後の引数がリストでなくても動作し、その場合はドットペアを含む improper list が生成されます。 – CLHS: Function LIST, LIST*
  16. last がコンスセルを返す設計になっているのは、末尾に要素を nconc で破壊的に連結する操作の基点として使われるからです。(car (last lst)) で末尾要素を得る書き方が慣用句です。 – CLHS: Function LAST
  17. nthcdr に n としてリストの長さ以上の値を渡すと nil を返します。エラーにならない点は nth と同じです。 – CLHS: Function NTHCDR
  18. copy-list は cdr 方向にコピーしますが car 方向にはコピーしません。CLHSでは「トップレベルのリスト構造のみをコピーする」と定義されています。 – CLHS: Function COPY-LIST
  19. append の計算量は最後の引数以外のリストの全要素数に比例します。ループ内で (append acc (list x)) を繰り返すパターンは O(N²) になります。先頭に cons を積んでから最後に nreverse するパターンが効率的です。 – Lisp Style and Efficiency
  20. nconc は末尾コンスセルの cdr を書き換えて連結します。リテラルリストはコンパイラが共有オブジェクトとして扱う場合があり、変更すると他の場所にある同じリテラルにも影響する可能性があります。list や copy-list で作ったリストだけに使います。 – Practical Common Lisp: They Called It Lisp for a Reason
  21. push はマクロとして実装されており、第2引数には変数だけでなく setf が使えるジェネラライズド変数を渡せます。たとえば (push x (car lst)) のように使えます。 – CLHS: Macro PUSH
  22. nreverse は元のリストの cdr を書き換えますが、返り値が元の変数を指しているとは限りません。(setf lst (nreverse lst)) のように返り値を変数に代入し直す必要があります。 – CLHS: Function NREVERSE
  23. sort の破壊的な動作は仕様で定められています。「どのコンスセルを変更するかは実装依存」とされており、返り値を使わずに元の変数を参照し続けると、未定義の結果になります。常に返り値を使います。 – CLHS: Function SORT, STABLE-SORT
  24. stable-sort は同値要素間の相対順序を保持することが仕様で保証されています。一方 sort は高速化のために順序を変える可能性があります。ソートキー以外の情報も重要な場合は stable-sort を選びます。 – CLHS: Function SORT, STABLE-SORT
  25. :key に指定した関数は要素を変換するためだけに使われ、返り値が比較対象になります。要素そのものは変更されません。:test のデフォルトは eql で、文字列など eql で比較できないオブジェクトには :test #'equal を渡します。 – CLHS: Function FIND, FIND-IF
  26. member が残りのリストを返す設計になっているのは、「見つかった位置以降の要素も処理したい」ケースに対応するためです。単に「含まれているか」を調べるだけなら (if (member x lst) t nil) のように t に変換します。 – CLHS: Function MEMBER
  27. eql は数値・文字・シンボルの同一性を比較します。文字列は eql では内容比較ができず、equal が必要です。オブジェクトの構造的な等価性を比較するには equalp を使います。 – CLHS: Function EQL
  28. every は条件が偽になった時点で即座に nil を返し、残りの要素を処理しません。some は条件が真になった時点で即座にその値を返します。この短絡評価により、長いリストでも無駄な処理を避けられます。 – CLHS: Function EVERY, SOME, NOTANY, NOTEVERY
  29. notany は (not (some ...)) と等価で、notevery は (not (every ...)) と等価です。ただし独立した関数として定義されているため、短絡評価を行います。 – CLHS: Function EVERY, SOME, NOTANY, NOTEVERY
  30. CLHSは mapcan を「mapcar と同様だが結果を nconc で連結する」と定義しています。そのため変換関数が '(1 2) のようなリテラルを返すと、nconc がそのリテラルを破壊的に変更し未定義動作になります。変換関数の中では必ず list で新しいリストを作って返します。 – CLHS: Function MAPCAN
  31. mapc が元のリストを返す設計なのは、dolist や loop と同じく「副作用のためだけに使うときは入力を返す」という慣例に沿っています。返り値を使わないことが多いですが、パイプライン的な処理で入力リストを次の関数に渡したいときに便利です。 – CLHS: Function MAPC
  32. coerce はリスト、ベクタ、文字列など Common Lisp の「シーケンス」型の間で変換できます。ただし変換先の型と要素型が一致しない場合はエラーになります。文字列への変換には各要素が character 型である必要があります。 – CLHS: Function COERCE
  33. alist に同じキーが複数存在する場合、assoc は先頭から走査して最初に見つかったコンスセルを返します。この性質を利用して、リストの先頭に新しいペアを cons するだけで「上書き」を表現できます。古いエントリは残りますが参照されなくなります。 – CLHS: Function ASSOC
  34. plist はシンボルのプロパティとして言語レベルで組み込まれており、(get symbol indicator) でシンボルの plist からプロパティを取得できます。関数のキーワード引数の内部表現にも plist が使われています。 – CLHS: Function GETF
  35. alist、plist、ハッシュテーブルの使い分けの目安は要素数と操作の種類によります。要素数が少なく（目安として10〜20件以下）、線形走査のコストが問題にならない場合は alist か plist が簡潔です。頻繁な検索・更新が必要でデータが大きい場合はハッシュテーブルを選びます。 – Common Lisp Cookbook: Data Structures
  36. union、intersection、set-difference はいずれも結果の順序が仕様で定められていません。順序が重要な場合は sort で並べ直す必要があります。また :test のデフォルトは eql なので、文字列には :test #'equal を渡します。 – CLHS: Function UNION
  37. remove-duplicates はデフォルトで後ろの重複を残し、前の重複を除きます。:from-end t を渡すと前の重複を残します。どちらの順序になるかは意図を明示するために常に指定する習慣をつけると安全です。 – CLHS: Function REMOVE-DUPLICATES
  38. キーの種類が事前にわかっていてサイズが固定できる場合はベクタでのカウントが O(1) で高速です。キーが動的に決まる場合や文字列など非整数のキーを使う場合は alist か、大規模データにはハッシュテーブルが適します。
  39. loop の into 節を使うと複数の蓄積変数を並列に作れます。collect item into yes と collect item into no はそれぞれ独立したリストに要素を集め、finally で取り出せます。 – CLHS: Section 6.1.3 Value Accumulation Clauses
  40. for x on lst は x に lst、(cdr lst)、(cddr lst) … と残りのリストを順に束縛します。for x in lst が要素を取り出すのに対し、on はコンスセルのリストを取り出す点が違います。 – CLHS: Section 6.1.2.1 Iteration Control
  41. (mapcar #'cons keys values) が zip になるのは、cons が2引数を取り、mapcar が複数リストの対応要素を並行して渡すからです。Python の zip() 関数と同じ動作を、mapcar と cons の組み合わせで実現しています。 – CLHS: Function MAPCAR