リストの作成

リストを作成する

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

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

(make-list 5)
=> (nil nil nil nil nil)

(make-list 5 :initial-element 7)
=> (7 7 7 7 7)

要素が一つのリストを作成する

(cons 'a nil)
=> (a)

1 から n までの要素を順に持つリストを作る

(defun seq (n)
  (labels((seq-reverse (n)
            (if (= n 0) nil
              (cons n (seq-reverse (- n 1))))))
    (reverse (seq-reverse n))))

(seq 10)
=> (1 2 3 4 5 6 7 8 9 10)

リストを調べる

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

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

リストの要素がただひとつかどうかを調べる

(defun singlep (l)
  (and (consp l) (null (cdr l))))

(singlep '(1 2))
=> nil

(singlep '(1))
=> t

length を使うのは非効率．最初の要素だけを見ればよい．

ある要素がリストに含まれているかを調べる

(find 1 '(1 2 3 4 5))
=> 1

位置を調べたい場合は position を使うこと．

(position 4 '(5 4 3 2 1))
=> 1

文字列の場合は、デフォルトの比較関数 eq が使えないので注意。

(find "apple" '("grape" "orange" "apple"))
nil

(find "apple" '("grape" "orange" "apple") :test 'equal)
=> "apple"

要素にある処理を加えた上で検索する

各要素(リストになっている)の先頭の要素を取り出して、条件と比較する例。

(member 'c '((a b) (c d) (e f)) :key #'car)
=> ((c d) (e f))

リスト内に重複データがあるかどうかチェックする

(defun check-duplicate (lst)
  (if (eql lst nil)
      nil
    (let ((var (car lst))
	  (l (cdr lst)))
      (if (find var l)
	  t
	(check-duplicate l)))))

(check-duplicate '(1 2 3 4 5))
=> nil

(check-duplicate '(1 1 2 3))
=> t

リストの長さを比較する

(defun longerp (la lb)
  (cond ((null la) nil)
	((null lb) t)
	(t (longerp (cdr la) (cdr lb)))))

(longerp '(1 2 3) '(1 2 3 4 5))
=> nil

(longerp '(1 2 3 4 5 6) '(1 2 3 4 5))
=> t

(longerp '(1 2 3) '(1 2 3))
=> nil

リスト中に含まれる x の個数を数える

(count 'x '(x y z x y z))
=> 2

リスト中に含まれる x の位置を求める

(position 5 '(1 2 3 4 5 6))
=> 4

リスト中の最大値、最小値を求める

(apply #'max '(1 2 3 4 5))
=> 5

(apply #'min '(1 2 3 4 5))
=> 1

リストの要素の合計値を求める

(apply #'+ '(1 2 3 4 5))
=> 15

要素 x, y が隣接しているかチェックする(順序は問わない)

(defun adjacent (x y lst)
  (cond ((null lst) nil)
	((and (eql x (car lst)) (eql y (cadr lst)) t))
	((and (eql y (car lst)) (eql x (cadr lst)) t))
	(t (adjacent x y (cdr lst)))))

(adjacent 'x 'y '(x y z z y))
=> t

(adjacent 'x 'y '(x p y z z y))
=> nil

要素 x が y より前にあるかチェックする

(defun before (x y lst)
  (let ((p1 (position x lst))
	(p2 (position y lst)))
    (cond ((null p1) nil)
	  ((null p2) nil)
	  ((< p1 p2) t)
	  (t nil))))

(before 'x 'y '(a b c x y z))
=> t

(before 'x 'y '(a b c x - z))
=> nil

(before 'x 'y '(a b c y x z))
=> nil

ある条件にリストの一部あるいは全体が該当するかどうかを調べる

(notany #'evenp '(1 3 5))
=> t

(notany #'evenp '(1 2 3 4 5))
=> nil

(notevery #'evenp '(1 2 3 4 5))
=> t

(notevery #'evenp '(2 4))
=> nil

(some #'evenp '(1 2 3 4 5))
=> t

(some #'evenp '(1 3 5))
=> nil

リストの変更

リストに要素を追加する

(cons 4 '(1 2 3))
=> (4 1 2 3)

リストを任意の値で埋める

(fill '(a b c d e) 'x)
=> (x x x x x)

リストを空にする

意味はないと思うが…。

(setq x '(1 2 3))
=> (1 2 3)

(setq x nil)
=> nil

リストの値の置き換え(特定の位置の値を置き換える)

(setq lst '(1 2 3 4 5))
=> (1 2 3 4 5)

(setf (first lst) 5)
=> 5

lst
=> (5 2 3 4 5)

(setf (nth 4 lst) 9)
=> 9

lst
=> (5 2 3 4 9)

リストの値の置き換え(特定の値を，別の値に置き換える)

(subst 1 2 '(0 1 2 (1 2 (1 2)) 3 4 5))
=> (0 1 1 (1 1 (1 1)) 3 4 5)

(substitute 1 2 '(0 1 2 (1 2 (1 2)) 3 4 5))
=> (0 1 1 (1 2 (1 2)) 3 4 5)

subst と substitute の違いは、前者がリスト構造を再帰的にたどること。

リストの値の置き換え(ある条件を満たす要素を，別の値に置き換える)

subst, substitute には -if, -if-not もある。

(substitute-if 0 #'(lambda (x) (and (integerp x) (evenp x))) '(0 1 2 (1 2 (1 2)) 3 4 5))
=> (0 1 0 (1 2 (1 2)) 3 0 5)

(subst-if 0 #'(lambda (x) (and (integerp x) (evenp x))) '(0 1 2 (1 2 (1 2)) 3 4 5))
=> (0 1 0 (1 0 (1 0)) 3 0 5)

テスト条件には、リストの末端要素だけでなく部分リストも与えられるので、型チェックを忘れないこと。

リストの n, m 番目の要素を入れ替える

(defun swap (n m ls)
  (let ((new-ls (copy-list ls)))
    (setf (nth n new-ls) (nth m ls))
    (setf (nth m new-ls) (nth n ls))
    new-ls))

(swap 1 5 '(0 1 2 3 4 5))
=> (0 5 2 3 4 1)

リストから特定の値を取り除く

(remove nil '(nil 1 2 3 nil nil))
=> (1 2 3)

リストのn番目の要素を取り除く

(defun take (n lst)
  (if (= n 0) nil
    (cons (car lst) (take (1- n) (cdr lst)))))

(defun remove-nth (n lst)
  (append (take (1- n) lst) (nthcdr n lst)))

(remove-nth 5 '(1 2 3 4 5 6 7 8))
=> (1 2 3 4 6 7 8)

リストの最後の要素を取り除く

(butlast '(1 2 3 4 5))
=> (1 2 3 4)

リストから重複データを取り除く

(remove-duplicates '(1 1 2 2 1 1 3 3))
=> (2 1 3)

ソート済みリストに要素を挿入する

(defun sorted-list-insert (val lst f)
  (cond ((null lst) (cons val nil))
	((funcall f val (car lst)) (cons val lst))
	(t (cons (car lst) (sorted-list-insert val (cdr lst) f)))))
=> sorted-list-insert

(sorted-list-insert 5 '(1 2 3 7 8 9) #'<)
=> (1 2 3 5 7 8 9)

(sorted-list-insert 4 '(1 2) #'<)
=> (1 2 4)

(sorted-list-insert 'j '(a b c x y z) #'string<)
=> (a b c j x y z)

リストをn個ずつのリストに分解する

(defun take (n lst)
  (if (= n 0) nil
    (cons (car lst) (take (1- n) (cdr lst)))))

(defun group (n lst)
  (if (null lst) nil
    (cons (take n lst) (group n (nthcdr n lst)))))

(group 3 '(1 2 3 4 5 6 7 8 9))
=> ((1 2 3) (4 5 6) (7 8 9))

(group 3 '(1 2 3 4 5 6 7 8 9 10))
=> ((1 2 3) (4 5 6) (7 8 9) (10 nil nil))

リストをn個に分割する(先頭要素から順に分配する)

(defun take (n lst)
  (if (= n 0) nil
    (cons (car lst) (take (1- n) (cdr lst)))))

(defun list-cons (lst cars)
  (mapcar #'(lambda (l c) (cons c l))
	  lst
	  cars))

(defun divide (n lst)
  (labels ((divide-sub (m l result)
	     (if (null l) result
	       (divide-sub m
			   (nthcdr m l)
			   (list-cons result (take m l))))))
    (mapcar #'reverse (divide-sub n lst (make-sequence 'list n)))))

(divide 2 '(a 1 b 2 c 3 d 4 e 5))
=> ((a b c d e) (1 2 3 4 5))

car部分を置き換える

(setq l '(a b c d e))
=> (a b c d e)

(rplaca l 'x)
=> (x b c d e)

(rplaca (cddr l) 'y)
=> (y d e)

l
=> (x b y d e)

cdr部分を置き換える

(setq l '(a b c d e))
=> (a b c d e)

(rplacd l '(x y z))
=> (a x y z)

l
=> (a x y z)

リストの一部を取り出す

リストから n 番目の値を取り出す

1～10番目までは関数が用意されている．

(setq lst '(1 2 3 4 5 6 7 8 9 10))

(first lst)
=> 1

(second lst)
=> 2

(tenth lst)
=> 10

それ以降については，nth を使う．最初の要素は「0番目」なので注意．

(nth 5 lst)
=> 6

リストの最後を(リストとして)取り出す

(last '(1 2 3 4 5))
=> (5)

リストの先頭または末尾から要素を取りだす

(car '(1 2 3 4 5))
=> 1

(car (last '(1 2 3 4 5)))
=> 5

リストからランダムな要素を取り出す

(defun random-element (ls)
  (nth (random (length ls)) ls))

(random-element '(1 2 3 4 5 6 7 8 9 10))
=> 3

より一般的な考え方に基づく別解。

長さがわからない列において、今まで出てきた要素がそれぞれ等確率で残るようにする手順は、「n番目の要素に出会った際、確率1/nで新しい要素と置き換える」である。

最初の要素: 1/1 の確率で残る。
2番目の要素: 1/2 の確率で入れ替え→最初の要素が残る確率は 1 - 1/2 = 1/2 となる。
3番目の要素: 1/3 の確率で入れ替え→1, 2番目の要素が残る(=入れ替えられない)確率は2/3。それぞれは1/2の確率で残るので、全体としては (2/3)*(1/2) = 1/3 ずつの確率で残る
n番目の要素: n/1 の確率で入れ替え→1..(n-1)番目の要素が残る(=入れ替えられない)確率は(n-1)/n。それぞれは1/(n-1)の確率で残るので、全体としては {(n-1)/n}*{1/(n-1)} = 1/n ずつの確率で残る。

(defun random-element (ls)
  (let ((i 2)
	(result (car ls)))
    (dolist (e (cdr ls) result)
      (if (= 0 (random i)) (setq result e))
      (incf i))))

(random-element '(1 2 3 4 5 6 7 8 9 10))
=> 2

ただし、xyzzy lisp 上で時間測定したところ、nth を使った実装のほうが15倍早かった。

リストの先頭から n 個の要素を部分リストとして取り出す

(defun take (n lst)
  (if (= n 0) nil
    (cons (car lst) (take (1- n) (cdr lst)))))

(take 3 '(1 2 3 4 5))
=>(1 2 3)

リストの先頭から n 個の要素を取り除く

(nthcdr 3 '(1 2 3 4 5))
=>(4 5)

ある要素で始まる部分リストを取り出す

(member 3 '(1 2 3 4 5))
=> (3 4 5)

(member 3 '(1 2 3 4 5 1 2 3 4 5))
=> (3 4 5 1 2 3 4 5)

部分リストを取りだす

(subseq '(1 2 3 4 5 6 7) 3 5)
=> (4 5)

(subseq '(1 2 3 4 5 6 7) 3)
=> (4 5 6 7)

リストから条件に合う値だけを取り出す

素直に書くなら再帰。

(defun filter (val test lst)
  (if (null lst) nil
    (if (funcall test (car lst) val)
	(cons (car lst) (filter val test (cdr lst)))
      (filter val test (cdr lst)))))

(filter 5 #'> '(2 4 6 8 10))
=> (6 8 10)

reduce を使う別解。こちらのほうが一般解で美しい。

(defun filter (func lst)
  (reduce (lambda (x y)
	    (if (funcall func x)
		(cons x y)
	      y))
	  lst
	  :initial-value nil
	  :from-end t))

(filter #'(lambda (x) (> x 5)) '(2 4 6 8 10))
=> (6 8 10)

リスト同士の操作

複数のリストを結合する

(append '(1 2 3) '(4 5 6))
=> (1 2 3 4 5 6)

(concatenate 'list '(1 2 3) '(4 5 6))
=> (1 2 3 4 5 6)

複数のリストを結合する（リストをコピーしない）

(setq x '(1 2 3))
=> (1 2 3)

(setq y '(4 5 6))
=> (4 5 6)

(nconc x y)
=> (1 2 3 4 5 6)

x
=> (1 2 3 4 5 6)

y
=> (4 5 6)

リストの要素ごとの和・差を取る

(setq a1 '(1 2 3 4 5)
      a2 '(1 2 3 4 5))

(mapcar #'+ a1 a2)
=> (2 4 6 8 10)

(mapcar #'- a1 a2)
=> (0 0 0 0 0)

リストを集合とみなして和・積・差・排他的論理和を取る

(union '(1 2 3) '(2 3 4))
=> (1 2 3 4)

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

(set-difference '(1 2 3 4 5) '(2 3 4 9))
=> (5 1)

(set-exclusive-or '(1 2 3 4 5) '(2 3 4 9))
=> (5 1 9)

2つの列を比較し、一致しない部分を調べる

mismatch は異なる要素が最初に現れる位置を返す。

(mismatch '(a b c d e) '(a c d e f))
=> 1

(mismatch '(a b c d e) '(a b c d e))
=> nil

リストの並び替え

並びを逆順にする

(reverse '(1 2 3 4 5))
=> (5 4 3 2 1)

ソートする

(sort '(3 4 5 6 9 1) #'<)
=> (1 3 4 5 6 9)

(sort '("apple" "grape" "orange" "banana") #'string<)
=> ("apple" "banana" "grape" "orange")

リストをランダムに並べ替える

(defun take (n lst)
  (if (= n 0) nil
    (cons (car lst) (take (1- n) (cdr lst)))))

(defun remove-nth (n lst)
  (append (take (1- n) lst) (nthcdr n lst)))

(defun shuffle (lst)
  (if (null lst)
      nil
    (let* ((n (1+ (random (length lst))))
	   (v (nth (1- n) lst))
	   (l (remove-nth n lst)))
      (cons v (shuffle l)))))

(shuffle '(1 2 3 4 5 6 7 8 9 10))
=> (5 8 3 10 1 7 9 2 4 6)

連想リスト

連想リストを新規作成する

(setq alist '((a . b) (c . d) (e . f) (g . h)))
=> ((a . b) (c . d) (e . f) (g . h))

(pairlis '(a c e g) '(b d f h))
=> ((g . h) (e . f) (c . d) (a . b))

連想リストを検索する

(setq alist '((a . b) (c . d) (e . f) (g . h)))
=> ((a . b) (c . d) (e . f) (g . h))

(assoc 'a alist)
=> (a . b)
(assoc 'b alist)
=> nil

(rassoc 'd alist)
=> (c . d)

(rassoc 'c alist)
=> nil

文字列をキーにする場合は注意すること．:test を指定しないと期待通りの動きをしない．

(setq alist '(("a" . ".-.")
              ("b" . "---")
              ("c" . "...")))
=> (("a" . ".-.") ("b" . "---") ("c" . "..."))

(assoc "a" alist :test #'equal)
=> ("a" . ".-.")

連想リストにデータを追加する

(setq alist '((a . b)))
=> ((a . b))

(acons 'c 'd alist)
=> ((c . d) (a . b))

連想リストをソートする

cdr 部で降順，cdr 部が同じ場合は car 部で降順にソートする例．

(setq alist '(("abc" . 10) ("xcd" . 20) ("cde" . 30) ("dea" . 30) ("eab" . 20)))
=> (("abc" . 10) ("xcd" . 20) ("cde" . 30) ("dea" . 30) ("eab" . 20))

(defun compare-alist (e1 e2 cmp-car cmp-cdr)
  (let ((car1 (car e1))
        (car2 (car e2))
        (cdr1 (cdr e1))
        (cdr2 (cdr e2)))
    (if (equalp cdr1 cdr2)
        (funcall cmp-car car1 car2)
      (funcall cmp-cdr cdr1 cdr2))))

(defun sort-alist (alist cmp-car cmp-cdr)
  (sort alist (lambda (e1 e2)
                (compare-alist e1 e2 cmp-car cmp-cdr))))

(sort-alist alist #'string> #'>)
=> (("dea" . 30) ("cde" . 30) ("xcd" . 20) ("eab" . 20) ("abc" . 10))

属性リスト

属性リストは、キーと値のペアを保存するためのデータ構造。

(key-1 value-1 key-2 value-2 ... key-n value-n)

属性を追加する

(setf (get 'taro 'height) 170)
=> 170

(setf (get 'taro 'weight) 60)
=> 60

(setf (get 'taro 'sex) 'male)
=> male

属性リストを得る

(symbol-plist 'taro)
=> (sex male weight 60 height 170)

キーから値を得る

(get 'taro 'height)
=> 170

属性を削除する

(remprop 'taro 'height)
=> t

(get 'taro 'height)
=> nil

(symbol-plist 'taro)
=> (sex male weight 60)

リストの外部出力

リスト要素をカンマ区切りで出力する

(defun join (str delimiter vlist)
  (let ((v (car vlist)))
    (cond
     ((equal v nil) str)
     ((equal str "") (join (format nil "~D" v) delimiter (cdr vlist)))
     (t (join (concat str delimiter (format nil "~D" v)) delimiter (cdr vlist))))))

(join "" "," '(1 2 3 4 5))
=> "1,2,3,4,5"

リストをコピーする

copy-list, copy-tree がある。両者の違いは、 *copy-list はトップレベルのセルだけをコピーする *copy-tree はすべてのセルをコピーする

(copy-list '(1 2 3 4 5))
=> (1 2 3 4 5)

(copy-list '((1 2) (3 4) (5 6))
=> ((1 2) (3 4) (5 6))

(copy-tree '(1 2 3 4 5))
=> (1 2 3 4 5)

(copy-tree '((1 2) (3 4) (5 6))
=> ((1 2) (3 4) (5 6))

数字を要素とするリストを、数値に変換する

(defun numerize (lst)
  (labels
      ((numerize-recur (lst)
	 (if (null lst) 0
	   (+ (car lst) (* 10 (numerize-recur (cdr lst)))))))
    (numerize-recur (reverse lst))))
numerize

(numerize '(1 2 3))
=> 123