Common Lisp Programming

列関数

Common Lisp はリスト (list)、文字列 (string)、ベクタ (vector) を、「列 (sequence)」として統一して扱うことができます。

列型データを操作する関数を「列関数」と呼びます。列関数には有用な関数が多数用意されています。

●単純な列関数

まずは単純な列関数を説明します。下表を見てください。

列はベクタと同様に 0 から数えます。elt で指定する index の範囲は、列の長さを len とすると 0 から len - 1 までとなります。subseq の start と end はコピーする範囲を指定します。end を省略すると列の最後尾が範囲となります。start 位置の要素はコピー範囲に含まれますが、end 位置の要素は範囲外になることに注意してください。次の図を見てください。

1 番目の要素 B は範囲内ですが 5 番目の要素 F は範囲外なので、コピーされたリストに F は含まれません。

関数 make-sequence は type で指定した列型データを作成します。キーワード :initial-element を指定すると、列はその値で初期化されます。

それでは簡単な例を示しましょう。

* (elt '(11 12 13 14 15) 0)

11
* (elt #(11 12 13 14 15) 4)

15
* (subseq '(11 12 13 14 15) 1 4)

(12 13 14)
* (subseq #(11 12 13 14 15) 1 4)

#(12 13 14)
* (copy-seq '(11 12 13 14 15))

(11 12 13 14 15)
* (copy-seq #(11 12 13 14 15))

#(11 12 13 14 15)
* (length '(11 12 13 14 15))

5
* (length #(11 12 13 14 15))

5
* (reverse '(11 12 13 14 15))

(15 14 13 12 11)
* (reverse #(11 12 13 14 15))

#(15 14 13 12 11)
* (make-sequence 'list 10 :initial-element 1)

(1 1 1 1 1 1 1 1 1 1)
* (make-sequence 'vector 10 :initial-element 1)

#(1 1 1 1 1 1 1 1 1 1)

●文字

文字列から取り出した要素は「文字 (character)」として扱われます。Common Lisp には文字型データが用意されていて、#\ に続けて文字自身を書いて表します。文字のエンコードが UTF-8 であれば、SBCL は日本語を 1 文字として扱うことができます。簡単な例を示しましょう。

* (elt "abcdeあいうえお" 0)

#\a
* (elt "abcdeあいうえお" 5)

#\HIRAGANA_LETTER_A
* (elt "abcdeあいうえお" 6)

#\HIRAGANA_LETTER_I
* (length "abcdeあいうえお")

10
* (reverse "abcdeあいうえお")

"おえういあedcba"
* (make-sequence 'string 10 :initial-element #\a)

"aaaaaaaaaa"
* (make-sequence 'string 10 :initial-element #\HIRAGANA_LETTER_A)

"ああああああああああ"
* (make-sequence 'string 10 :initial-element #\HIRAGANA_LETTER_KA)

"かかかかかかかかかか"

文字列から文字を取り出すには、elt のほかに関数 char を使うことができます。

char string index

* (char "abcdeあいうえお" 0)

#\a
* (char "abcdeあいうえお" 9)

#\HIRAGANA_LETTER_O

char の引数 string は文字列でなければいけません。

●列の探索

次に、列を探索する関数を説明します。下表を見てください。

名前の最後に -if, -if-not がつく関数は述語 predicate を受け取る高階関数です。それから、単純な列関数以外では、下表に示すキーワードを使用することができます。

もっともよく使われるキーワードは :start と :end です。これは subseq の start, end と同様に部分列を指定します。

簡単な例を示しましょう。

* (find-if #'oddp '(10 11 12 13 14 15 16 17 18 19) :start 2)

13
* (position-if #'oddp '(10 11 12 13 14 15 16 17 18 19) :start 4)

5
* (count-if #'oddp '(10 11 12 13 14 15 16 17 18 19) :start 3 :end 7)

2

find-if の例では、2 番目から奇数を探すので 11 ではなく 13 を返します。position-if では、4 番目から奇数を探すので 15 の位置 5 を返します。count-if では部分列 (13 14 15 16) の奇数をカウントするので 2 を返します。

:test, :test-not は等値を判定する述語を指定します。これらのキーワードは、-if, -if-not がついている列関数で使うことはできません。-if, -if-not 以外の関数では、デフォルトで述語 eql を使います。たとえば、文字列を格納しているリストからデータを探す場合、eql では探すことができません。次の例を見てください。

* (find "def" '("abc" "def" "ghi"))

NIL
* (find "def" '("abc" "def" "ghi") :test #'equal)

"def"

この場合、:test に equal を指定することで文字列を検索することができます。:test-not は :test の逆で、指定した述語が偽となる要素を探します。

列に格納されたデータがリストの場合、その中の要素をキーにして探索できると便利です。この場合はキーワード :key を使います。次の例を見てください。

* (find 'b '((a . 1) (b . 2) (c . 3)))

NIL
* (find 'b '((a . 1) (b . 2) (c . 3)) :key #'car)

(B . 2)

:key を指定しないと B と要素 (リスト) を eql で比較することになるので、データを見つけることができません。:key に car を指定することで、要素に car を適用した結果と B を比較することができるので、(B . 2) を見つけることができます。:from-end に t を指定すると、列の最後尾から検索を開始します。:count は列を修正する関数で説明します。

●列の修正

次は列を修正する関数を説明します。下表を見てください。

remove と substitute は引数を変更しませんが、fill は引数 sequence を破壊的に修正します。このほかに、引数を破壊的に修正する関数 delete と nsubstitute があります。簡単な例を示しましょう。

* (remove-if #'oddp '(10 11 12 13 14 15 16 17 18 19))

(10 12 14 16 18)
* (remove-if #'oddp '(10 11 12 13 14 15 16 17 18 19) :start 2 :end 8)

(10 11 12 14 16 18 19)
* (substitute-if 99 #'oddp '(10 11 12 13 14 15 16 17 18 19))

(10 99 12 99 14 99 16 99 18 99)
* (substitute-if 99 #'oddp '(10 11 12 13 14 15 16 17 18 19) :start 3 :end 7)

(10 11 12 99 14 99 16 17 18 19)
* (setq a '(10 11 12 13 14 15 16 17 18 19))

(10 11 12 13 14 15 16 17 18 19)
* (fill a 99 :start 3 :end 7)

(10 11 12 99 99 99 99 17 18 19)
* a

(10 11 12 99 99 99 99 17 18 19)

キーワード :count は、処理する要素の個数を制限します。たとえば、remove であれば item と等しい要素を列からすべて削除しますが、:count で個数が指定されていると、それ以上の削除は行いません。次の例を見てください。

* (remove 'a '(a b c a b c a b c))

(B C B C B C)
* (remove 'a '(a b c a b c a b c) :count 2)

(B C B C A B C)
* (remove 'a '(a b c a b c a b c) :count 2 :from-end t)

(A B C B C B C)

このように、:count に 2 を指定すれば、a は 2 つしか削除されません。:from-end を設定すれば、後ろから 2 つ a を削除します。また、:test-not を指定することで、item と等しくないデータを削除する、つまり、item と等しいデータを取り出すこともできます。

* (remove 'b '((a . 1) (b . 2) (c . 3) (b . 4)) :test-not #'eql :key #'car)

((B . 2) (B . 4))

remove-duplicates は sequence の要素を順番に比較し、一致する要素が 2 つあれば sequence の前にある要素を削除します。等しい要素が複数個ある場合、結果として一番最後の要素だけが 1 つ残ります。:form-end が真の場合、sequence の後ろにある要素が削除されるので、一番前の要素だけが 1 つ残ります。このほかに、引数を破壊的に修正する delete-duplicates があります。簡単な使用例を示します。

* (remove-duplicates '(a b c b d d d e))

(A C B D E)
* (remove-duplicates '(a b c b d d d e) :from-end t)

(A B C D E)
* (remove-duplicates '("abc" "def" "abc" "ghi") :test #'equal)

("def" "abc" "ghi")
* (remove-duplicates '("abc" "def" "abc" "ghi") :test #'equal :from-end t)

("abc" "def" "ghi")

●マッピング

マップ関数 mapcar はリストにしか適用できませんが、Common Lisp には列型データに適用できるマップ関数が用意されています。

関数 map は引数の列の要素に関数 func を適用し、その結果を要素とする列型データを返します。返り値のデータ型は result-type で指定します。関数 map-into は、map と同様に引数の列の要素に関数 func を適用しますが、その結果を列 result-seq に代入します。result-seq の内容は書き換えられることに注意してください。

それから、map-into の result-seq には文字列を指定できません。リストかベクタだけなので注意してください。簡単な例を示します。

* (map 'list #'+ '(1 2 3) '(10 20 30 40))

(11 22 33)
* (map 'vector #'* '(10 20 30) '(1 2 3))

#(10 40 90)
* (setq a #(10 20 30 40))

#(10 20 30 40)
* (map-into a #'+ '(1 2 3) '(4 5 6))

#(5 7 9 40)
* a

#(5 7 9 40)

●列の連結

複数の列を連結するには関数 concatenate を使います。

concatenate は複数の列を連結し、結果を result-type で指定したデータ型で返します。concatenate の場合、ふつう list, string, vector のどれかを指定します。簡単な使用例を示しましょう。

* (concatenate 'list '(a b c) '(d e f g))

(A B C D E F G)
* (concatenate 'vector '(a b c) '(d e f g))

#(A B C D E F G)
* (concatenate 'string '(#\a #\b #\c) '(#\d #\e #\f #\g))

"abcdefg"

リストやベクタを文字列に変換する場合、列の要素は文字でなければいけません。

●畳み込み

関数 reduce は列の畳み込みます。

reduce function sequence

reduce は sequence の各要素に対して関数 function (F) を次のように適用します。

(A1 A2 A3 ... An-1 An) = reduce F => (F (F ... (F (F A1 A2) A3) ...) An-1) An)

:from-end t の場合
(A1 A2 A3 ... An-1 An) = reduce F => (F A1 (F A2 (F A3 ... (F An-1 An) ...)))

簡単な例を示しましょう。

* (reduce #'+ '(1 2 3 4 5 6))

21
* (reduce #'list '(1 2 3 4 5 6))

(((((1 2) 3) 4) 5) 6)
* (reduce #'list '(1 2 3 4 5 6) :from-end t)

(1 (2 (3 (4 (5 6)))))

キーワード :initial-value が指定された場合、reduce は関数 F を次のように適用します。

:initial-vallue G の場合
(G A1 A2 A3 ... An-1 An) = reduce F => (F (F ... (F (F G A1) A2) ...) An-1) An)
(reduce #'list '(1 2 3 4 5 6) :initial-value 0) => ((((((0 1) 2) 3) 4) 5) 6)

:initial-vallue G :from-end t の場合
(A1 A2 A3 ... An-1 An G) = reduce F => (F A1 (F A2 (F A3 ... (F An G) ...)))
(reduce #'list '(1 2 3 4 5 6) :from-end t :initial-value 7) => (1 (2 (3 (4 (5 (6 7))))))

:initial-value がなくて列の要素が 1 つしかない場合、reduce はその要素を返します。列が空で :initial-value が指定されている場合、reduce は :initial-value の値を返します。もしも、列が空で :initial-value も指定されていない場合、reduce は関数 function を引数無しで呼び出してその結果を返します。簡単な例を示します。

* (reduce #'+ '(1))

1
* (reduce #'+ nil :initial-value 2)

2
* (reduce #'+ nil)

0

reduce と 2 引数の関数を組み合わせることで、いろいろな関数を実現することができます。たとえば、length と append は次のようになります。

* (reduce #'(lambda (x y) (+ x 1)) '(a b c d e) :initial-value 0)

5
* (reduce #'cons '(a b c d e) :initial-value '(1 2 3 4 5) :from-end t)

(A B C D E 1 2 3 4 5)

●ソートとマージ

ソート (sort) はデータを昇順または降順に整列させる操作です。マージ (merge) は整列済みの 2 つのデータ列を 1 つの整列済みのデータ列にまとめる操作です。Common Lisp には関数 sort と merge が用意されています。

関数 sort は引数の sequence を破壊的にソートし、関数 merge はソート済みの 2 つの列 seq1 と seq2 をマージします。簡単な使用例を示しましょう。

* (setq a #(9 1 8 2 7 3 4 6 5))

#(9 1 8 2 7 3 4 6 5)
* (sort a #'<)

#(1 2 3 4 5 6 7 8 9)
* a

#(1 2 3 4 5 6 7 8 9)
* (setq a #((9 a) (1 b) (8 c) (2 d) (7 e) (3 f) (4 g) (6 h) (5 i)))

#((9 A) (1 B) (8 C) (2 D) (7 E) (3 F) (4 G) (6 H) (5 I))
* (sort a #'< :key #'car)

#((1 B) (2 D) (3 F) (4 G) (5 I) (6 H) (7 E) (8 C) (9 A))
* (merge 'list '(1 3 5 7 9) '(2 4 6 8) #'<)

(1 2 3 4 5 6 7 8 9)

キーワード :key を設定することで、複雑なデータでもソートやマージを簡単に行うことができます。

リスト操作関数

リスト操作の基本 では、リストの分解や合成など簡単なリスト操作を説明しました。また、リストの操作には 列関数 を使うことができます。このほかにも Common Lisp にはリストを扱う便利な関数が用意されています。

●リストの探索

リストの探索は find や position などの列関数で行うことができますが、このほかに member というリスト専用の関数が用意されています。

伝統的な Lisp では、リストの中にデータが含まれているか調べる述語として member を使います。伝統のある Lisp 関数なのですが、Common Lisp では -if や -if-not も用意されています。

member は list の中に item が含まれているか調べます。もし見つからなければ NIL を返します。見つけた場合は、item 以降のリストの残りを返します。返り値は member-if, -if-not も同じです。ここが find や position と異なるところです。member はリストのトップレベルの中から item を探すことに気をつけてください。

それでは、簡単な使用例を示します。

(member 'd '(b c d e f))   => (D E F)
(member 'a '(b c d e f))   => NIL
(member 'c '((a b) (c d))) => NIL
(member-if #'oddp '(0 2 4 6 1 3 5 7)) => (1 3 5 7)

member, -if, -if-not はキーワード :key を指定することができます。それから、member は :test と :test-not も指定することができます。デフォルトは列関数と同じく eql です。ただし、列関数と違って :start と :end は指定できません。ご注意ください。簡単な例を示しましょう。

(member 'c '((a b) (c d) (e f)) :key #'car)   => ((C D) (E F))
(member 1.0 '(0 2 4 6 1 3 5 7) :test #'equal) => (1 3 5 7)

●リストの置換

リストの要素を置き換えるには、列関数の substitute を使うと便利ですが、リストのトップレベルの要素にしか適用できません。したがって、((a b) (c d)) のようなリストの要素を置換することはできません。このように、入れ子になっているリスト構造を「木 (tree)」といいますが、Lisp には木の要素を置換する関数 subst が用意されています。

subst も伝統的な関数ですが、Common Lisp には -if, -if-not も用意されています。subst は、リスト tree の old に等しい (eql) 部分を、new に置き換えた新しいリストを返します。subst はリストの構造を再帰的にたどり、すべての要素を検査します。元のリストは破壊されません。簡単な例を示しましょう。

(subst 1 'a '(a b c (a b c (a b c . a)))) => (1 B C (1 B C (1 B C . 1)))

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

subst-if, -if-not を使う場合、述語にはリストも渡されるので、最後の例は #'evenp だけでは動作しません。つまり、1 や 2 だけではなく、(1 2) や ((1 2) (3 4)) も検査されるのです。ご注意ください。

subst, -if, -if-not はキーワード :key を指定することができます。それから、subst は :test と :test-not も指定することができます。また、tree のリスト構造を破壊的に修正する関数 nsubst もあります。

●連想リスト

もうひとつ Lisp らしいリスト構造を紹介しましょう。「連想リスト (association list : a-list)」はドット対を要素とするリストです。ドット対の CAR 部がキーで、CDR 部がデータに対応します。次の図を見てください。

上図の場合、A, C, E, G がキーで、B, D, F, H がデータとなります。キーやデータはシンボル以外の S 式でもかまいません。そして、連想リストからデータを検索する関数が assoc です。

assoc も Lisp の伝統的な関数ですが、Common Lisp では -if, -if-not も用意されています。assoc は連想リスト a-list から item と等しい (eql) キーを探します。見つからない場合は NIL を返します。簡単な使用例を示しましょう。

(setq z '((a . b) (c . d) (e . f) (g . h))) => ((A . B) (C . D) (E . F) (G . H))
(assoc 'e z) => (E . F)
(assoc 'h z) => NIL

assoc は、見つけたキーのデータを返すのではなく、ドット対を返すことに注意してください。それから、assoc, -if, -if-not はキーワード :key を指定することができ、assoc は :test と :test-not も指定することができます。

assoc の動作は、列関数 find の :key に car を指定した場合とほとんど同じです。ただひとつの違いは NIL の扱い方です。次の例を見てください。

(find nil '((a . b) nil (c . d) (nil . e)) :key #'car) => NIL

(assoc nil '((a . b) nil (c . d) (nil . e))) => (NIL . E)

find の場合、リストの要素に無条件で car を適用します。探索するキーが NIL の場合、リストの要素に NIL が含まれていると、(car nil) の結果が NIL になるので、find はデータを見つけたと判断します。これに対し、assoc は連想リスト中に NIL が含まれているとそれを無視するので、キーが NIL のデータを見つけることができます。

assoc はキーを探索しますが、データ (ドット対の CDR 部) を探索する関数が rassoc です。

rassoc は連想リスト a-list から item と等しい (eql) データを探します。見つからない場合は NIL を返します。簡単な使用例を示しましょう。

(setq z '((a . b) (c . d) (e . f) (g . h))) => ((A . B) (C . D) (E . F) (G . H))

(rassoc 'e z) => NIL
(rassoc 'h z) => (G . H)

assoc と同様にドット対を返すことに注意してください。また、rassoc, -if, -if-not はキーワード :key を指定することができ、rassoc は :test と :test-not も指定することができます。

連想リストにデータを追加する場合、cons でも簡単にできますが関数 acons を使うと便利です。

acons key data a-list

acons は (cons (cons key data) a-list) と同じです。また、連想リストの新規に作成する場合や、まとめてデータを追加する場合は関数 pairlis を使うと便利です。

pairlis key-list data-list &optional a-list

(pairlis '(a b c d) '(1 2 3 4)) => ((D . 4) (C . 3) (B . 2) (A . 1))

もうひとつ便利な関数を紹介しましょう。関数 sublis は、連想リストのキーに等しい tree の部分を、キーに対応するデータに置き換えます。sublis は subst を複数回実行した場合と同じ効果が得られます。tree は破壊されません。

sublis a-list tree

(sublis '((a . 1) (b . 2)) '(a b c (a b c . a) d . b))
=> (1 2 C (1 2 C . 1) D . 2)

sublis にはキーワード :key, :test, :test-not を指定することができます。

●その他の関数

関数 endp はリストの終端を検査する述語です。コンスセルに対しては偽、NIL に対しては真を返します。それ以外のデータはエラーになります。

(endp nil)    => T
(endp '(1 2)) => NIL

関数 nth はリストの n 番目の要素を返します。列関数と同様に先頭の要素が 0 番目になります。n がリストの長さより大きい場合は NIL を返します。

nth n list 

(nth 0 '(a b c d)) => A
(nth 3 '(a b c d)) => D
(nth 4 '(a b c d)) => NIL

関数 nthcdr はリストに対して n 回だけ cdr を実行します。n がリストの長さより大きい場合は NIL を返します。

nthcdr n list

(nthcdr 0 '(a b c d)) => (A B C D)
(nthcdr 2 '(a b c d)) => (C D)
(nthcdr 5 '(a b c d)) => NIL

関数 last はリストの最後から n 個のコンスセルを返します。空リストの場合は NIL を返します。

last list &optional (n 1)

(last '(a b c d))     => (D)
(last '(a b c d . e)) => (D . E)
(last '(a b c d) 2)   => (C D)

関数 butlast は n 個のコンスセルをリストの最後尾から取り除きます。

butlast list &optional (n 1)

(butlast '(a b c d))       => (A B C)
(butlast '(a b c d) 2)     => (A B)
(butlast '(a b c d . e) 2) => (A B)
(butlast nil)              => NIL

関数 make-list は、要素が size 個のリストを作成します。キーワード :initial-element が指定されると、その値に初期化されます。デフォルト値は NIL です。

make-list size &key :initial-element

(make-list 5) => (NIL NIL NIL NIL NIL)
(make-list 5 :initial-element 0) => (0 0 0 0 0)

関数 copy-list はリストのトップレベルをコピーして返します。関数 copy-tree はリストの木構造をコピーして返します。

copy-list list
copy-tree object

(copy-list '((a b) (c d))) => ((A B) (C D))
(copy-tree '((a b) (c d))) => ((A B) (C D))

(copy-list 1) => エラー
(copy-tree 1) => 1

copy-tree は引数がリストでなければ、引数をそのまま返します。copy-list は引数がリストでなければエラーになります。

次に、copy-list と copy-tree の違いを簡単に説明します。次の図を見てください。

上図はリスト ((1 2) (3 4)) の構造を表したものです。コンスセルは全部で 6 つありますね。copy-list はトップレベルのセル A と B だけをコピーします。残りのセルはコピーしません。つまり、新しいセル A' と B' を生成して、A の CAR と CDR を A' にコピーし、B の CAR と CDR を B' にコピーします。

これに対し、copy-tree はすべてのコンスセルをコピーします。トップレベルのセル A と B だけではなく、C, D, E, F のセルもコピーするのです。これが copy-list と copy-tree の違いです。