第17章「シーケンス」

概要

ANSI Common Lispの第17章「シーケンス」を説明します。

シーケンスの基礎

シーケンスとは、リストまたはベクトルのことです。シーケンスは独立したデータ構造ではなく、リストとベクトルを共通して扱えるようにするための集合(型)です。文字列もベクトルなので、シーケンスでもあります。

シーケンスに対して定められたいくつかのオペレータはリスト版またはベクトル版の似たようなオペレータが存在する場合があります。例えば、シーケンスのアクセッサであるeltは、リストならnth、ベクトルならaref、シンプルベクトルならsvrefのように、同じ機能のものが複数定められています。このような場合、型が事前に決まっているならより特定的なアクセッサを利用した方が高速に処理することができます。どのようなオペレータを使用するかは臨機応変に判断してください。

シーケンスに関する基礎的なオペレータは以下の通りです。
Function: make-sequence
シーケンスを生成します。第1引数に返り値の型を、第2引数に要素数を指定します。返り値は型で指定したリストまたはベクトルとなります。:initial-elementキーワード引数を指定すると、その要素で埋めることができます。
Accessor: elt
シーケンスに対するアクセッサです。第1引数にシーケンスを、第2引数に要素番号を指定します。setfマクロで使用すると、要素を変更することができます。
Accessor: subseq
シーケンスの一部に対するアクセッサです。第1引数にシーケンスを、第2引数に部分参照する開始位置を指定します。第3引数はオプショナルで、部分参照の終了位置を指定します。setfマクロで使用すると、シーケンスの一部を変更することができます。
Function: length
シーケンスの要素数を取得します。シーケンスがフィルポインタ付のベクトルの場合、フィルポインタの番号(アクティブな状態のベクトルの要素数)を取得します。
Function: concatenate
シーケンスを連結します。第1引数に返り値の型を指定し、第2引数以降は可変長で、連結したいシーケンスを列挙します。
make-sequence関数はあまり使われないかもしれません。特に、ベクトルの場合の型の指定は処理系依存として定められており、意図した型にならない場合があるので気をつけてください。
(defparameter *seq* (make-sequence '(vector fixnum 3) 3))
; => *SEQ*
(type-of *seq*)
; => (SIMPLE-VECTOR 3)

GNU CLISPではこのように要素の型がtに変換されるため、'simple-vectorになりましたが、SBCLとCCLでは'fixnumという要素の型の指定がそのまま有効だったため、型は'(simple-array fixnum (3))という型になりました。
;; 参照
(elt '(1 2 3) 1)
; => 2

;; 部分参照
(subseq "abcdef" 2 4)
; => "cd"

;; 参照を用いた変更
(let ((seq "abcdef")) 
  (setf (subseq seq 2 4) "34") 
  seq)
; => "ab34ef"

;; 長さ(要素数)
(length '((1 2) (3 4)(5 6)))
; => 3

;; 連結
(concatenate 'simple-vector '(1 2) #(3 4) '(5 6))
; => #(1 2 3 4 5 6)

シーケンスに関するオペレータ

前節で述べたlengthconcatenateもオペレータ(関数)ですが、少し複雑でありながら、汎用性の高いオペレータをまとめて紹介します。
Function: reverse, nreverse
シーケンスを逆順にします。reverseは元のリストをコピーし、nreverseは元のリストをそのまま破壊的に修正して逆順に変えます。
Function: find, find-if
シーケンスの中から特定の要素を探します。第1引数が探したい要素、第2引数がシーケンスです。:from-endキーワード引数をtで指定すると後ろから検索します。:testキーワード引数を使うと要素の検索に用いる述語関数を指定できます。find-ifの場合は探す要素の代わりに述語関数を指定し、判定結果がtの場合の要素を探索します。返り値は要素です。
Function: position, position-if
シーケンスの中から特定の要素を検索し、その位置を返します。findと同じ引数を使うことができます。
Function: count, count-if
シーケンスの中から特定の要素を検索し、その個数を返します。findpositionと同様です。
Function: remove, remove-if, delete, delete-if
シーケンスの中から特定の要素を検索し、その要素を削除したシーケンスを返します。removeはシーケンスをコピーしますが、deleteはシーケンスをコピーせずに破壊的に修正します。
Function: remove-if-not, delete-if-not
シーケンスの中から要素を順番に述語関数で判定し、tとなる要素のみを残したシーケンスを返します。if-not系は全般に非推奨となっていますが、これだけはif系と共に比較的よく使われていると思うので、あえて紹介します。
Function: substitute, substitute-if, nsubstitute, nsubstitute-if
シーケンスの中から第2引数の要素を検索し、第1引数の要素に置換して、新しいシーケンスを返します。対象となるシーケンスは第3引数に指定します。
Function: sort
シーケンスの要素を指定された述語関数に従って並べ替えます。第1引数にシーケンスを、第2引数に述語関数を指定します。
Function: merge
2つのシーケンスの要素を述語関数で比較しながら連結したシーケンスを返します。元のシーケンスは破壊的に修正される可能性があります。第1引数に返り値の型を、第2引数と第3引数にマージしたいシーケンスを、第4引数にソートに用いる述語関数を指定します。連結してからソートするのではなく、各要素同士を比較しながら逐次連結を行います。
Function: map
シーケンスの各要素に対して特定の関数を適用し、その返り値をシーケンスにして返します。第1引数に返り値の型を、第2引数に適用したい関数を指定します。第3引数以降は可変長になっており、幾つでもシーケンスを指定できますが、シーケンスの数と適用したい関数の引数の数は一致していなければなりません。
Function: reduce
シーケンスの要素を1つずつ取り出し、指定された関数に適用しますが、その返り値と次の要素を新しい引数として、再び指定された関数に適用していきます。引数の要素を一つずつ消費するため、「縮約」関数と呼ばれます。第1引数に適用したい関数を、第2引数にシーケンスを指定します。特に指定しなければ左から順に要素を消費しますが、:from-endキーワード引数をtで指定すると後ろから消費します。また、特に指定しなければ最初の関数適用ではシーケンスから2つの要素が消費されますが、:initial-valueキーワード引数で最初に消費したいオブジェクトを指定すれば、そのオブジェクトが最初に使われます。
以下がサンプルです。
;; 逆順
(reverse '(1 2 3))
; => (3 2 1)
(reverse "abc")
; => "cba"

;; 検索
(find "abc" '("ABC" "ABc" "AbC" "aBC" "abc") :test #'string=)
; => "abc"
(find-if #'upper-case-p "abcDef")
; => #\D
(find-if #'evenp '(1 3 9 7 6 5 2))
; => 6

;; 位置
(position-if #'evenp '(1 3 9 7 6 5 2))
; => 4

;; 個数
(count-if #'evenp '(1 3 9 7 6 5 2))
; => 2

;; 削除
(remove-if #'evenp '(1 3 9 7 6 5 2))
; => (1 3 9 7 5)

;; フィルタ
(remove-if-not #'evenp '(1 3 9 7 6 5 2))
; => (6 2)

;; 置換
(substitute-if 0 #'evenp '(1 3 9 7 6 5 2))
; => (1 3 9 7 0 5 0)

;; ソート
(sort '(1 3 9 7 6 5 2) #'<)
; => (1 2 3 5 6 7 9)
(sort '(1 3 9 7 6 5 2) #'>)
; => (9 7 6 5 3 2 1)

;; マージ
; (1) 1と6を比較して、1
; (2) 3と6を比較して、3
; (3) 9と6を比較して、6
; (4) 9と5を比較して、5
; (5) 9と2を比較して、2
; (6) 9しかないので、 9
; (7) 7しかないので、 7
(merge 'vector '(1 3 9 7) '(6 5 2) #'<)
; => #(1 3 6 5 2 9 7)

;; マップ
(map 'vector #'(lambda (x) (expt x 3)) '(1 2 3 4 5))
; => #(1 8 27 64 125)
(map 'vector #'(lambda (x y) (expt x y)) '(1 2 3 4 5) '(5 4 3 2 1))
; => #(1 16 27 16 5)

;; 縮約
(reduce #'(lambda (x y) (+ x (length y))) 
        '("abc" "def" "ghi")
        :initial-value 0)
; => 9
(reduce #'(lambda (n seq) (+ n (reduce #'+ seq)))
        '((1 2) (3 4) (5 6) (7 8) (9 10)) :initial-value 0)
; => 55

;; 第5章の defmacro で紹介した「アロー演算子」
(defmacro -> (&rest rest)
  (reduce #'(lambda (v x)
              (if (atom x)
                  `(,x ,v)
                  `(,(car x) ,v ,@(cdr x))))
          rest))
; => ->

(-> 1
    (+ 2)
    (* 3)
    (/ 4)
    print)
; 9/4
; => 9/4

0 件のコメント :

コメントを投稿