プログラミングを頑張る日記

プログラミングを勉強して、ハッカーになろう

Common Lispを頑張る(52)

「実践Common Lisp」やっていきます。
第13章はコンスセルについての章です。

リストと木

コンスセルから構成される構造を木として扱うことは自然なことだそう。
コンスセルの集まりはリストとしてか木として扱われますが、その扱いの違いは
関数が要素を見つけだす時のコンスセルの探索の仕方の違いだそうです。
リスト関数はコンスセルの集まりを、1つ目のコンスセルから始めてcdrが参照している先を
nilに到達するまで到っていくと。あるコンスセルのcarが参照しているオブジェクトは
そのリストに含まれる要素ですが、そのオブジェクトが別のコンスセルなら
それは注目しているリスト構造には含まれません。別のリストの先頭ということになるそう。
木構造を扱う関数の場合、carとcdrの両方を、参照先がコンスセルでなくなるまで辿ります。
要素とみなされるのは、辿ってみつけたアトム全てです。

ツリー向けの関数についてもいくつか説明がありますが割愛。
しかしツリー向け関数で破壊的な関数、使える自信がまるでありません。おっかない。

集合

どんなリストでも集合として扱え、集合論的な操作をするための関数もいくつかあるそうです。
とはいえ集合が大きくなるほど非効率になることを肝に命じろ、ということです。
でも記述が簡単になるのは確かで、小さな集合に対してなら効率がよいかも、ということで
一回書いてみてボトルネックになっていたら集合のリストをハッシュテーブルとか
ビットベクタに書き換えてみるということがオススメされています。

集合を組み立てるにはadjoinだそう。これは1つのアイテムと集合を表すリストを引数に、
オリジナルの集合の全要素と引数として与えたアイテムを含む集合を表すリストを返すそう。
集合に既にアイテムが含まれていたら足してはだめなので、まず集合のリストをスキャンします。
そして含まれていなければ新しいコンスセル(オリジナル+アイテム)を生成して返すということです。
含まれていればオリジナルをそのまま返すと。
これは非破壊的ですが、オリジナルを更新してくれるpushnewというマクロもあるそう。

集合にあるアイテムが含まれているかどうかはmember,member-if,member-if-notが使え、
それらはリスト専用のfind,find-if,find-if-notだと思ってしまってよさそう。
アイテムが存在すれば、指定したアイテムを含むコンスセルを返してくれるそうです。
しなければ予想通り(?)、nilが返ってきます。

他の集合論的な関数をざっと。それぞれ2つのリストを引数にとります。
intersection...2つの集合の和を返す
union...2つの集合の積を返す
set-difference...1つ目の引数における2つ目の引数の補集合を返す
set-exclusive-or...2つの集合の対象差を返す
上記全てにnをつけたリサイクルバージョンがあるそうです。
あと便利そうな、subsetpという引数の1つ目のリストが2つ目のリストの
部分集合であるときに真を返す関数が最後に紹介されました。

大学生のころ何となくとった論理学の授業は楽しかったし、
今仕事ではほとんどSQLしかやっていないので集合の話は嫌いじゃないです。
とばしぎみなのは、この章が終わったら「Land of Lisp」に帰ろうと企んでいるからです。
あと5ページばかりありますが。
しかし今回一回も実際に書いていません。ダメダメな感じ。
だけど気にしない、おやすみなさい。

Common Lispを頑張る(51)

「実践Common Lisp」やります。

破壊的操作

先日は関数的なプログラミングとリストの相性についてでしたが、残念ながら破壊的操作があります。
まあ、変数に値をセットすらできないなんて嫌です。特に残念でもないですね。
破壊的操作には大まかに2種類あり、副作用それ自体が目的であるような操作と、
引数のコンスセルを使い回すような操作があるということです。

副作用を目的とした操作では、まあ色々ありそうですね。setfがその最たるものみたいな書かれ方です。
あまりに明らさまだし、今更それらを「破壊的だ」と言うこともないでしょう。
というわけで注意しなくてはいけないは、予想外の場所にその「破壊」が及んでしまうことですね。

CL-USER> (defparameter *list-1* (list 1 2))
*LIST-1*
CL-USER> (defparameter *list-2* (list 3 4))
*LIST-2*
CL-USER> (defparameter *list-3* (append *list-1* *list-2*))
*LIST-3*                                ;*list-3*のコンスセルは*list-2*
CL-USER> (setf (car *list-2*) 0)
0
CL-USER> *list-2*
(0 4)
CL-USER> *list-3*
(1 2 0 4)
CL-USER>

これは予想外の破壊ですね。ふむふむ。

使い回しの操作は、関数的なコードの中で利用することを意図されているそうです。
引数として与えられたコンスセルのいくつかを結果を作りあげるときに必要な加工をしリサイクルすると。
というわけで、オリジナルがもういらない時が安全にリサイクルできるときです。
このリサイクル関数には大抵破壊的でない類似の関数がいますが、
場合によってはリサイクル関数の方が有用でエコであるそうで。

リサイクルな関数と構造共有の組み合わせ

リサイクル関数で使った引数の中に後で使うつもりのものがあったら悲しいことになります。
つまり構造共有との組み合わせはあまりよろしくありません。
リサイクル関数を使うときは、どのコンスセルがどこから参照されているのか把握していなくてはいけなくなります。

実践ではリサイクルな関数を使うときにはお決まりのイディオムがあるそうです。
よく使われるのは、リストの前に「コンスしていく」ことで組み立てたリストを
関数から返すときにそれをnreverseし結果を返すというものだそう。
上記のイディオムを使ってゼロから始まるn個の数値をリストを組み立てる関数が例で出てきます。

CL-USER> (defun upto (max)
           (let ((result nil))
               (dotimes (i max)
                 (push i result))
               (nreverse result)))
UPTO
CL-USER> 

このように関数内部で生成されたリストを弄るなら何の心配もなくリサイクルできますな。

他によく使われるイディオムには、リサイクルな関数の戻り値を即座に代入することだそう。

CL-USER> (setf *list-3* (delete 4 *list-3*))
(1 2 0)
CL-USER> *list-2*
(0)
CL-USER>

まあ当然注意が必要で、上では*list-3*と構造を共有していた*list-2*も変わりました。
deleteではなくremoveを使えばこんなことにはならないので、どうせsetfするならそっちを使えばいいような。
あと、上の例で最初は0を消そうとしたのですが、それだと*list-2*は変更されませんでした。
なんでだろう。何度やり直しても同じでした。
まあ、上の2例がリサイクルな関数を使う時のイディオムの8割を占めるそうです。

リストを操作するときは関数的なスタイルでコードを記述するのがベストだそうです。
関数は引数のリストの内容にだけ依存し、引数を変更しないようにするというルールに従えば
破壊的関数もリサイクルな関数も綺麗に排除することができます。
一旦は関数的なスタイルでコードを書きあげ、、最適化が必要なら、引数のリストが他のどこからも
参照されていないことを確認してから非破壊的なリスト操作をリサイクルバージョンに書きかえようとのこと。

あと、sort,stable-sort,margeはリストに適用したときはリサイクルな関数となるらしいです。
リストを破壊せずにソートするには、copy-listで生成したコピーを引数にする必要あると。
本当かな。

CL-USER> (defparameter *list* (list 4 3 2 1))
*LIST*
CL-USER> (sort *list* #'<)
(1 2 3 4)
CL-USER> *list*
(3 4)
CL-USER>

本当でした。

リスト操作関数

リスト操作のためのライブラリ関数を眺めていきます。
carとcdrをずっと使っていますが、firstとrestという同じ機能の関数があるようです。
まあ、そっちのほうがぱっと見でわかりやすい...のかな。今となってはどっちでも。
また、先頭から2番目の要素が欲しいとかいうときのため、secondからtenthまでの関数もあるそう。
これは便利そうですね。

CL-USER> (defparameter *list* (list 0 1 2 3 4 5 6 7 8 9))
*LIST*
CL-USER> (cadddr *list*)
3
CL-USER> (fourth *list*)
3
CL-USER> (cadddr (cdddr (cdddr *list*)))
9
CL-USER> (tenth *list*)
9
CL-USER>

凄い便利です。
じゃあもうcarやcdrなんて要らないのかななんて思いますが、
これらの関数はリストを扱うものというよりツリーを扱うためのもの、とあり用途によって使い分けると
プロ意識があるように見せかけられるかもしれません。
ツリーのデータを扱うときにfirstとか使ってたら実際変な感じがしますよね。多分。
でも多分これからもcarとcdr使っちゃいそうな気がします。secondとかは活用したいです。

他にも色々リスト操作関数が紹介されていますが、日常的に使いそうなのは
consp,atom,listp,nullぐらいな気がします。

マッピング

関数的スタイルのもう1つの重要な側面として高階関数の利用があるそうです。
おさらいですが、高階関数とは関数を引数として取ったり、戻り値が関数だったりするものです。
そしてCommon Lispにはリスト専用の6つのマッピング関数があるそうです。

1つはmapcar。ほぼmapですが、戻り値の型はリスト限定なので戻り値の型指定の引数が要らず、
第一引数に関数、それ以降の引数に関数に適用する要素を持つリストを取ります。
maplistはmapcarに似ているけど、関数に渡されるのがリストの要素ではなくコンスセルになるという
違いがあるようです。ふむ。

CL-USER> (maplist #'list '(1 2 3) '(10 20 30))
(((1 2 3) (10 20 30)) ((2 3) (20 30)) ((3) (30)))
CL-USER>

なるほど。なかなか使いどころはありそうですね。
mapcanとmapconは、それぞれmapcarとmaplistに似た動作をするそうです。戻り値の組立て以外。
mapcar,maplistは結果を保持するのに完全に新しいリストを作るのに対し、
mapcanとmapconは結果をnconcのように繋ぎ合わせるそうです。

CL-USER> (defparameter *list-2* (list 3 4))
*LIST-2*
CL-USER> (defparameter *list-1* (list 1 2 ))
*LIST-1*
CL-USER> (nconc *list-1* *list-2*)
(1 2 3 4)
CL-USER> *list-1*
(1 2 3 4)
CL-USER> *list-2*
(3 4)
CL-USER>

ふむふむ。これがnconc。

CL-USER> (mapcan #'+ *list-1* *list-2*)
6
CL-USER> *list-1*
(1 2)
CL-USER> *list-2*
(3 4)
CL-USER> (mapcon #'list *list-1* *list-2*)
((1 2) (3 4) (2) (4))
CL-USER> *list-1*
(1 2)
CL-USER> *list-2*
(3 4)
CL-USER> (mapcar #'+ *list-1* *list-2*)
(4 6)
CL-USER> (maplist #'list *list-1* *list-2*)
(((1 2) (3 4)) ((2) (4)))
CL-USER> (mapcan #'list *list-1* *list-2*)
(1 3 2 4)
CL-USER> 

関数を適用した結果の1つ1つをリストにしてそのリストを繋ぎ合わせていくイメージでしょうか。
残りはmapcとmapl。mapcは使ったことがあります。どちらとも関数ではなく制御構文だそう。
mapcがmapcarの、maplがmaplの一派で、いずれも最初のリスト引数をそのまま返します。
適用する関数の副作用だけを目当てに使うようで、また新たにリストを生成しない分速いらしいです。
「Land of Lisp」にそう書いてあった気がします。

久し振りに更新することができた満足感でいっぱいです。おやすみなさい。

Common Lispを頑張る(50)

amazon primeで観れるシリコンバレーが面白いです。
おもわずCommon Lispよりもそちらの話をしたくなってしまうぐらいですが、
それは抑えて、「実践Common Lisp」をやります。

There is no List.

リストってなんでしょう。もはや哲学的な問いのようです。
リストを理解する手掛かりは、そのほとんどがより基本的なデータ型のインスタンスである
オブジェクトの上に構築された幻想だと理解することにあるそうです。
その単純なオブジェクトとはコンスセルと呼ばれる値のペアであり、consにより作られます。

consは2つの引数をとり、その2つの値を保持する新しいコンスセルを返します。
2つ目の値がnilか他のコンスセル以外なら、ドット対(ドットペア、ドットリスト)を返します。

CL-USER> (cons 1 nil)
(1)
CL-USER> (cons 1 '(2 3))
(1 2 3)
CL-USER> (cons 1 2)
(1 . 2)
CL-USER>

コンスセルに含まれる2つの値は、それぞれcarとcdrと呼ばれます。どちらともsetf可能な場所です。
コンスセルに含まれる値はどんな種類のオブジェクトでも良く、
コンスセルを繋ぎあわせ巨大な構造を作れます。
この仕組みはLisp固有のものではなく、単方向リンクリストと呼ばれていますが、
Lisp族以外でこの簡素なデータ型に広範なサポートを与えているものがほぼ存在しないのも事実なよう。

うむむ...まあ色々書いてありますが結論、リストはコンスセルあるいはnilへの参照であると。
あ、あと木構造を表わすのに便利。

関数型プログラミングとリスト

関数型プログラミングとは、副作用がないことです(あってますよね)。
で、その利点はプログラムの理解が容易になること。

さて。数値は不変なオブジェクトなので、それを扱う関数は当然関数的になります。
それに対してリストはcarやcdrへのsetfで変化しえます。
とはいえ。含まれている要素によって値が決まるという考えをすれば、リストも関数的データ型と言えると。
うむむ。まあ、そうでしょうな。しかしその理屈で言うとほとんど関数的データ型では。
そうでもないのかな。わからん。とりあえず納得したことにします。

Common Lispのリスト操作関数のほとんどは関数的に書かれているそうです。
その理由は、与えられた引数とコンスセルを共有する結果が返せるようになるから。

CL-USER> (append '(1 2) '(3 4))
(1 2 3 4)
CL-USER>

上でappendの最終的な仕事は、(1 2 3 4)というリストを返すことです。
もちろんその4つのコンスセルを含むリストを作ってもいいのですが、そこまでせずとも、
1と2をそれぞれ含むコンスセルを2つ作り、2つめのコンスセルのcdrが
2つめの引数の(3 4)を指すようにすれば楽です。

へぇ~、って感じの話でした。とはいえちょっとびっくりしたので今日はここまで。
本当は早くシリコンバレー視聴に戻りたいのでした。

Common Lispを頑張る(49)

11月はめちゃくちゃ風邪を引きます。例年。
多少体調が良くなったのでやります、「実践Common Lisp」。
シーケンスについての話が続きます。

シーケンス述語

シーケンス全体に述語を適用して評価値を得る便利な関数が4つあり、
それはevery, some, notany, noteveryです。名前からして大体働きが想像できますね。
第一引数は述語で、残りの引数であるシーケンスと同じ数の引数を取るものとなります。

シーケンスマッピング関数

最後のシーケンス関数は総称的なマッピング関数だそう。
mapはシーケンス述語関数に似ていて、N個の引数を取る関数とN個のシーケンスを取ります。
戻り値になるのはシーケンスの各要素に関数を適用した新しいシーケンスです。
種類は指定しなくてはなりません。これstringとか指定することあるのでしょうか。

CL-USER> (map 'vector #'(lambda (x) (* x x)) '(1 2 3 4 5))
#(1 4 9 16 25)
CL-USER>

map-intoは、第一引数として渡したシーケンスに値を設定します。それ以外はmapに似ていると。

CL-USER> (defparameter *a* '(1 2 3 4 5))
*A*
CL-USER> (defparameter *b* '(10 20 30 40 50))
*B*
CL-USER> (defparameter *c* '(100 200 300 400 500))
*C*
CL-USER> (map-into *a* #'+ *a* *b* *c*)
(111 222 333 444 555)
CL-USER> *a*
(111 222 333 444 555)
CL-USER>

各シーケンスの長さが違う場合、最も短いシーケンスの要素と同じ数にだけ影響するそう。

最後のシーケンス関数はちょっと変わっているreduce。
第一引数が関数、第二引数がシーケンスで、シーケンスの第一要素と第二要素に関数を適用し、
その結果と残った要素を一つずつ関数に適用していきます。

CL-USER> (reduce #'+ '(1 2 3 4 5 6 7 8 9 10))
55
CL-USER>

reduceは非常に役に立つ関数で、特にシーケンスから1つの値を引き出したいときに有用だと。

CL-USER> (reduce #'max '(1 2 3 4 5 6 71 8 9 10))
71
CL-USER>

基本的なキーワード引数は全部取ることができ、また:initial-valueという
キーワード引数で、最初に関数に渡す値を指定することができます。

ハッシュテーブル

Common Lispに用意されているシーケンス以外の汎用目的のコレクションとしては
ハッシュテーブルがあるそうです。ベクタは整数でインデックス付けされたデータ構造で、
ハッシュテーブルは任意のオブジェクトをキーとして使うことができます。

引数なしのmake-hash-tableはeqlによって同じオブジェクトだった場合に2つのキーが等価だと
判定するハッシュテーブルを悪性します。
つまり、デフォルトではeqlで判定できない、例えば文字列などはキーに使えません
そういう時はお馴染、:testにequalを渡してmake-hash-tableを作成します。

ハッシュテーブルの要素にアクセスするには、gethashを使います。
キーとハッシュテーブルを引数として、キーが合致する値を返し、なければnilを返します。

CL-USER> (defparameter *h* (make-hash-table))
*H*
CL-USER> (gethash 'foo *h*)
NIL
NIL
CL-USER> (setf (gethash 'foo *h*) 'bar)
BAR
CL-USER> (gethash 'foo *h*)
BAR
T
CL-USER>

見ての通り、gethashは多値を返します。
nilが返ってきたときに値が見つかってnilなのか、見つからずnilなのかが分かるように真偽値があります。
多値の使い方は前どっかでやった気がするので割愛。

ハッシュテーブルからエントリを削除するには、remhashを使います。
引数はgethashと同じです。clrhashを使えばハッシュテーブルの全てのキーと値のペアを削除します。

ハッシュテーブル上の反復

ハッシュテーブルのエントリを反復して操作する手段が一通りあり、
一番シンプルなのがmaphashを使うことだそう。
とりあえず使い方の例がこんな感じのようです。

CL-USER> (maphash #'(lambda (k v) (format t "~a => ~a~%" k v)) *h*)
FOO => BAR
FIZZ => BAZZ
NIL
CL-USER>

反復処理の最中にハッシュテーブルの要素を追加したり削除したりしたらどうなるかわからないそうです。
とにかくそういう意地悪はやめたほうがよさそうであるとのこと。
ただし例外として、現在のエントリの値を変更するにはsetfがgethashとの組み合わせで使え、
現在のエントリを削除するにはremhashが使えるそうです。

とりあえずこんなもんでこの章は終わりです。
次の章ではいよいよリストの話。おやすみなさい。

Common Lispを頑張る(48)

よっしゃ! やっていきます「実践Common Lisp」。

高階関数

シーケンス反復関数(という名で呼んでいいのか)には高階関数の亜種が2種類用意されているそうです。
両方とも、アイテム引数の代わりにシーケンスの各要素について呼び出される関数を引数にするそう。
1種類目は基本関数に-ifをつけ足した名前の関数で、
引数で渡した関数が真を返す場合に基本関数の動作を行なうようです。
もう1つは、名前に-if-notがついたもので、1つめと逆の動作をします。

CL-USER> (count-if #'evenp '(1 2 3 4 5))
2
CL-USER> (count-if-not #'evenp '(1 2 3 4 5))
3
CL-USER> (remove-if-not #'(lambda (animal) (eql (car animal) '猫))
                        '((猫 たま) (犬 ぽち) (猫 みー) (猿 ぼぶ)))
                        
((猫 たま) (猫 みー))
CL-USER> 

後者の-if-not関数は言語の標準で非推奨とされているそうですが、
どうも非推奨にすべきではないという意見が多数らしく、標準が変わるとしたら非推奨でなくなるだろうということ。
特にremove-if-notは名前から受ける印象と違い、述語を満たすものを返すので使い勝手がいいとべた褒め。

これらの高階関数もキーワード引数を取ることができます。関数を引数でもともと持つので:test以外ですが。
と言うことは、:keyを使えば先程の例がもっとスマートに書けますね。

CL-USER> (remove-if-not #'(lambda (animal) (eql animal '猫))
                        '((猫 たま) (犬 ぽち) (猫 みー) (猿 ぼぶ)) :key #'car)
                        
((猫 たま) (猫 みー))
CL-USER>

removeにはremove-duplicateという更なる亜種がいて、引数のシーケンスの重複を取り除いて
結果を返すようです。シーケンス内の全ての要素が対象になるので:countはキーワードにできないそう。

シーケンス全体の操作

シーケンス全体を一度に操作する関数もいくつかあるそうです。
copy-seq,reverseはいずれもシーケンス1つを引数にとり、同じ型の新しいシーケンスを返すそう。
注意点として、どちらも新たに作成されるオブジェクトは全体の容器としてのシーケンスだけであり、
その中身の各要素はコピーされて新しく作られるわけではないということです。
ちょっと難解な言い回しな気がしますが、浅いコピーということですかね。

CL-USER> *vec*
#(Z B D E F H)
CL-USER> (reverse *vec*)
#(H F E D B Z)
CL-USER> (copy-seq *vec*)
#(Z B D E F H)
CL-USER> (defvar *copy-vec* (copy-seq *vec*))
*COPY-VEC*
CL-USER> (vector-pop *copy-vec*)
; Evaluation aborted on #<TYPE-ERROR expected-type: (AND VECTOR (NOT SIMPLE-ARRAY))
             datum: #<(SIMPLE-VECTOR 6) {1002F5F05F}>>.
CL-USER> (vector-pop *vec*)
H
CL-USER> *copy-vec*
#(Z B D E F H)
CL-USER> *vec*
#(Z B D E F)
CL-USER> (elt *copy-vec* 0)
Z
CL-USER> (setf (elt *copy-vec* 0) 'a)
A
CL-USER> *copy-vec*
#(A B D E F H)
CL-USER> *vec*
#(Z B D E F)
CL-USER> (type-of *copy-vec*)
(SIMPLE-VECTOR 6)
CL-USER> (type-of *vec*)
(VECTOR T 10)
CL-USER>

なんか思ってたのと違いました。型が違っている...。うーん、わからん。
それ以外どれぐらい違うのでしょう。とりあえずほとんど普通にベクタとして使えるのかな。
配列,ベクタ,シーケンス : セマンティックウェブ・ダイアリー
ありがたい記事。「生成後動的に大きさが変わらない」というところにひっかかったようです。
コピーをするとフィルポインタまでは引き継がれない、よし。

CL-USER> (type-of (make-array 5))
(SIMPLE-VECTOR 5)
CL-USER> (type-of (make-array 5 :fill-pointer t))
(VECTOR T 5)
CL-USER>

concatenate関数は、任意の数のシーケンスを繋ぎ合わせ新しいシーケンスを返してくれます。
そうか、文字列もリストもシーケンスという共通点があってconcatenateで使えていたんですね。

CL-USER> (concatenate 'vector #(1 2 3) '(4 5 6))
#(1 2 3 4 5 6)
CL-USER> (concatenate 'list #(1 2 3) "456")
(1 2 3 #\4 #\5 #\6)
CL-USER> (concatenate 'string #(1 2 3) '(4 5 6))
; Evaluation aborted on #<TYPE-ERROR expected-type: CHARACTER datum: 1>.
CL-USER> (concatenate 'string #(#\1 #\2 #\3) '(#\4 #\5 #\6))
"123456"
CL-USER>

stringは文字しか受けつけない...以前もやらかしてました...。

ソートとマージ

シーケンスをソートするには、sortとstable-sortという2種類の関数が使えるそう。
いずれも引数にシーケンスと述語を取り、ソートされたシーケンスを返します。そして、破壊的関数。
stable-sortのsortと違う点は、述語によって等価だと判断された値の順序を絶対に変えないというとこ。
ついでに破壊的関数とは言っても書き方には注意があるそうなのでそれは下記で。

CL-USER> (defparameter *vec* (vector "foo" "bar" "baz"))
*VEC*
CL-USER> *VEC*
#("foo" "bar" "baz")
CL-USER> (setf *vec* (sort *vec* #'string<)) ;ソート関数はシーケンスを好き勝手に変更し得るので
#("bar" "baz" "foo")                    ;必ず戻り値を利用することを心がける
CL-USER>

merge関数は2つのシーケンスと述語を取り、2つのシーケンスを述語に照らし合わせてマージした結果を返します。
戻り値のシーケンスは、元のシーケンスを両方とも同じ述語でソートしてから
マージしたシーケンスと同じになるそうです。
また第一引数として、生成されるシーケンスの型を明示してあげる必要があるそうです。

CL-USER> (merge 'list #(1 6 3) #(2 8 0) #'<)
(1 2 6 3 8 0)
CL-USER> (merge 'list #(1 6 3) #(2 8 0) #'>)
(2 8 1 6 3 0)
CL-USER>

めちゃくちゃですね。どういう順序で並んでいるのかわかりません。
各シーケンスの先頭要素を述語で比較して、残ったほうと次の要素を比較して、という感じ?
引数のシーケンスはソートされている必要があるのかな。

CL-USER> (merge 'list #(1 3 6) #(0 2 8) #'<)
(0 1 2 3 6 8)
CL-USER> (merge 'list #(1 3 6) #(0 2 8) #'>)
(1 3 6 0 2 8)
CL-USER> (merge 'list (reverse #(1 3 6)) (reverse #(0 2 8)) #'>)
(8 6 3 2 1 0)
CL-USER>

そうっぽいですね。

部分シーケンス操作

既存のシーケンスの部分シーケンスを操作するための一番基本的な関数は、subseqというそう。
開始インデックスから終了インデックス、あるいは開始からシーケンスの終わりまでを取り出せます。

CL-USER> (subseq "foobarbaz" 3 6)
"bar"
CL-USER> (subseq "foobarbaz" 3)
"barbaz"
CL-USER> (subseq '(foo bar baz fiz foo bar) 3 5)
(FIZ FOO)
CL-USER>

また、setfもできますが、それによってシーケンスが伸長することはないそうです。

CL-USER> (defparameter *str* (copy-seq "foobarbaz"))
*STR*
CL-USER> (defun subseq-test (str s e)
           (setf (subseq *str* s e) str)
           *str*)
SUBSEQ-TEST
CL-USER> (subseq-test *abc* 3 6)
; Evaluation aborted on #<UNBOUND-VARIABLE *ABC* {10044623F3}>.
CL-USER> (subseq-test "abc" 3 6)
"fooabcbaz"                             ;部分シーケンスと新しい値が同じ長さ。問題なし。
CL-USER> (subseq-test "barrrr" 3 6)
"foobarbaz"                             ;新しい値が長すぎ。余分なとこは無視。
CL-USER> (subseq-test "xx" 3 6)
"fooxxrbaz"                             ;新しい値が短すぎ。あるぶんだけ変更。
CL-USER>

シーケンス中の複数の要素を1つの値に設定するときは、fillというのを使うそう。
必要な引数は、対象のシーケンスと埋める値。キーワード引数の:startと:endで範囲を指定します。
デフォルトの範囲はシーケンス全体だそう。

CL-USER> (fill *str* #\x :start 3 :end 6)
"fooxxxbaz"
CL-USER>

シーケンスから部分シーケンスを探すときはsearchが使え、
似た関数であるpotitionは要素を探すときに使い、searchはシーケンスを探すという違いがあるようです。

CL-USER> (position #\a *str*)
4
CL-USER> (position "bar" *str*)
NIL
CL-USER> (search "bar" *str*)
3
CL-USER> (search #\a *str*)
; Evaluation aborted on #<TYPE-ERROR expected-type: SEQUENCE datum: #\a>.
CL-USER> (search "a" *str*)
4
CL-USER>

searchの方が便利な気がしてしまします。

共通のプリフィックスを持つ2つのシーケンスから最初の差分になる場所を見つけたいときは、
mismatch関数が使えます。

CL-USER> (mismatch "ヨヨヨヨヨヨヨヨ" "ヨヨヨヨEヨヨヨ")
4
CL-USER> (mismatch "ヨヨヨヨヨヨヨヨ" "ヨヨヨヨヨヨヨ")
7
CL-USER> (mismatch "ヨヨヨヨヨヨヨヨ" "ヨヨヨヨヨヨヨヨ")
NIL
CL-USER>

最近出てきた標準的なキーワード引数は全て取ることができるそうです。

久しぶりに長めになりました。今日はここまで!

Common Lispを頑張る(47)

今日も「実践Common Lisp」をやります。先日に引き続きベクタの話です。

特殊ベクタ

ここまで見てきたベクタは、どういった型のオブジェクトでも要素とできました。
特殊ベクタとは、ある型の要素だけを保持するように制限したものだそうです。
わざわざそれを使うメリットとしては、コンパクトにデータを保存できるようになるかもしれないこと、
アクセスが早くなるかもしれないことが挙げられるようです。
微妙な言い方なので、そんな目に見えて変わるものでないのかもしれません。
それよりもそれ事態が重要なデータ型であるような特殊ベクタがあるそうです。

まず、文字だけを保持する特殊ベクタ、つまり文字列。なるほど。
ダブルクォートで括る独自の読み書き、印字のシンタックス、専用の関数がありますが、
結局はベクタの一種なのでベクタにできることは文字列にもできるそうです。

"foo"のような文字列リテラルは、#()シンタックスによるリテラルに似たもので、変更はできないと。
サイズの変更ができる文字列を作るなら、make-arrayに:element-typeを指定するそうです。
:element-typeは、見た通りに型を指定するためのものだそう。
文字列を作るためというよりかは、特殊ベクタ全般のためのような気がしますね。

CL-USER> (make-array 5 :fill-pointer 0 :adjustable t :element-type 'character)
""
CL-USER> (defparameter *str* 
           (make-array 5 :fill-pointer 0 :adjustable t :element-type 'character))
*STR*
CL-USER> (defun push-string (str target)
           (let ((x (concatenate 'list str)))
             (labels ((push-list (y)
                        (if (eql y nil)
                            target
                            (progn (vector-push-extend (car y) target)
                                   (push-list (cdr y))))))
               (push-list x))))
PUSH-STRING
CL-USER> CL-USER> (defun push-string (str target)
           (let ((x (concatenate 'list str)))
             (labels ((push-list (y)
                        (if (eql y nil)
                            target
                            (progn (vector-push-extend (car y) target)
                                   (push-list (cdr y))))))
               (push-list x))))
PUSH-STRING
CL-USER> (push-string "string" *str*)
"string"
CL-USER>

探せばありそうな文字列をベクタに突っこむ関数をせっかくなので自作して試しました。
久しぶりに再帰を書きたかったのです。なるほどなるほど。

文字列以外の特殊ベクタとしては、ビットベクタというものがあるそうです。
その名の通り、0あるいは1のみを要素として持つということ。
印字のシンタックスは、#*0101といった感じのようです。
2つのビット配列の論理積をとるとかの関数がたくさん用意されているらしいです。
make-arrayで作るときに:element-typeに渡すのは、シンボルbitです。

シーケンスとしてのベクタ

ベクタとリストはシーケンスという型のサブタイプである、ということで
ここから紹介されるシーケンス関数は、ベクタにもリストにも適用できるようです。

基本的なシーケンス関数としては、lengthとeltがあるそうです。
lengthはシーケンスを一つ引数にとり、引数に含まれる要素の数を返します。
eltはelementの略で、引数にシーケンスとインデックスとしての整数をとり、
シーケンスの要素のうちインデックスに対応する要素を返してくれます。

CL-USER> *vec*
#(A B D E F H)
CL-USER> (elt *vec* 0)
A
CL-USER> (elt *vec* 3)
E
CL-USER> (elt *vec* 6)
; Evaluation aborted on #<SB-KERNEL:INDEX-TOO-LARGE-ERROR expected-type: (INTEGER 0 5) datum: 6>.
CL-USER> (setf (elt *vec* 0) 'z)
Z
CL-USER> *vec*
#(Z B D E F H)
CL-USER> (elt '(a b c) 1)
B
CL-USER>

ふむふむ。setfも可能です。最後は本当にリストでできるのか確認したくなりました。

シーケンス反復関数

lengthとeltさえあれば、理論上シーケンスへの全ての操作は可能だそうです。
でもだからって他の関数が無かったらやばいですよね。というわけで豊富なライブラリがあるそう。
いくつか例として関数が紹介されます。

CL-USER> *vec*
#(Z B D E F H)
CL-USER> *str*
"string"
CL-USER> (count #\s *str*)              ;シーケンスの中の要素の数を調べる
1
CL-USER> (find #\i *str*)               ;要素の検索、要素かnilを返す
#\i
CL-USER> (find #\z *str*)
NIL
CL-USER> (position 'b *vec*)            ;要素のインデックスか、見つからなければnilを返す
1
CL-USER> (position 'a *vec*)
NIL
CL-USER> (remove 'h *vec*)              ;引数と一致した要素を取り除いたシーケンスを返す
#(Z B D E F)
CL-USER> (remove 'a *vec*)              ;破壊的関数じゃなかった...
#(Z B D E F H)
CL-USER> (substitute 'a 'z *vec*)       ;要素の置き換え
#(A B D E F H)
CL-USER> *vec*                          ;やっぱり非破壊的
#(Z B D E F H)
CL-USER> 

これらの関数もキーワード引数で振舞いを変更できるそう。
例えば、どの関数もシーケンス中の要素と引数の型が同じであることが期待されていますが、
変更する方法も2つあるそうです。
1つ目は、真偽値を比較する関数はデフォルトがeqlなので、:testキーワードでそれを変更すること。
2つ目は、:keyキーワードで1引数関数とやらを渡す方法だそうです。
使ったことはあるけど、言葉にされると全然よくわかりませんなあ。困った。
とにかく。この1引数関数がシーケンス中の各要素に対して呼び出されキーの値になり、
その値がアイテムとの比較に使われるというわけですね。

CL-USER> (find 'a '((a b) (b a) (c b)))
NIL
CL-USER> (find 'a '((a b) (b a) (c b)) :key #'car)
(A B)
CL-USER>

関数の効力をシーケンスの特定の部分に限定するときは、:startや:endによる指定を行なえばいいそう。
また、:from-endにnil以外の値を与えればシーケンスを逆側から走査しますが、
findとposition以外の関数の結果には直接影響しないということです。

CL-USER> (remove 'a '#(a b c a d e f a) :start 2 :end 6)
#(A B C D E F A)
CL-USER> (find 'neko '#((neko tama) (inu hiroshi) (neko el)) :key #'car :from-end t)
(NEKO EL)
CL-USER>

ただし、取り除いたり置き換えたりする要素の個数を指定する:countキーワードと:from-endを組み合わせると
当然removeやsubstituteの結果は通常と異なるものになりがちです。
それと、:from-endは:keyや:testで指定した関数が副作用を含んでいる場合には注意すべきだそうです。

なかなか使いでのあることがいっぱい出てきてなかなか楽しいです。
でも疲れたので寝ます。おやすみなさい。

Common Lispを頑張る(46)

また月曜日が始まりましたね。どうでもよいのです。
「実践Common Lisp」第11章、やっていきます。

Common Lispにも複数の値を1つのオブジェクトにまとめた標準的なデータ型があります。
特に有名なのはリストですね。

ところがこの本はリストをまだあんまり扱う気がないようです。
もっとそれぞれの場合により適したデータ構造があるのだから、
あんまりリストに特化した考えかたをしてほしくないという思いがあるよう。

そういうことなら自分も一旦リストを忘れて読んでいきます。

ベクタ

ベクタは整数でインデックスされたCommon Lispの基本的なコレクションです。
ベクタには2つの亜種がいるそうで、まず固定サイズのもの。
これはベクタの要素を保持している連続したメモリの塊の表面に薄い化粧板を張ってまとめたようなもの。
そして可変サイズ。要素の追加や削除に応じてベクタが伸縮し、実際のストレージを抽象化します。

特定の値を含む固定サイズのベクタはvector関数で作成できます。
vector関数は任意個の引数を取り、引数で与えた要素を含む固定サイズのベクタを新しく確保します。

CL-USER> (vector)
#()
CL-USER> (vector 1)
#(1)
CL-USER> (vector 1 2)
#(1 2)
CL-USER>

前にも書きましたが、#(...)というのはLispの読取器や印字器が使うベクタのためのリテラル表記です。
別に直接#(1 2)とコードに書いてしまってもいいけれど、
リテラルオブジェクトに変更を加えたときの動作は未定義だからvectorを使うって話ですね。

さて、もうmake-arrayという関数もあり、こちらはvactorよりも汎用の関数で、
固定サイズと可変サイズのベクタを作ることができます。
さらに、任意次元の配列を作ることができるそうです。

make-arrayには引数として、配列の次元を表すリストが必要であるそうです。
ベクタは1次元の配列なので、ベクタの場合はベクタのサイズを示す数を1つ含んだリストを引数に。
利便性のため、リストの代わりに数値を引数にすることもできます。
他に引数がなければ初期化されていない要素を含んだベクタを生成するそうで、
初期化されていない要素にアクセスしたとしたらその場合の動作も未定義です。やめます。
:initial-element引数を渡せば、その引数で値を初期化することができます。

CL-USER> (make-array 5 :initial-element 'neko)
#(NEKO NEKO NEKO NEKO NEKO)
CL-USER>

可変サイズのベクタは、固定サイズのベクタよりもちょっぴり複雑なオブジェクトだそう。
要素を保持するのに使っているメモリと空いているスロットを記録するのに加えて、
実際にベクタに保持している要素の数も当然記録していないといけないからです。
そしてこの数はベクタのフィルポインタとやらに記録されるそうです。

フィルポインタを持ったベクタを作るには、:fill-pointer引数を渡します。

CL-USER> (defparameter *vec* (make-array 5 :fill-pointer 0))
*VEC*
CL-USER> *vec*
#()
CL-USER>

サイズが変更できるベクタの末尾に要素を追加するにはvector-pushというのを使うそう。
フィルポインタの示す場所に要素を追加、フィルポインタの値を1つ増やし、
追加要素のインデックスを返してくれるということです。
vector-popというのは、最後に追加された要素を返し、フィルポインタの値を減らすと。

でもこれでは可変ベクタと呼ぶ気になりません。フィルポインタはいいのですが、要素数が固定では。
というわけで、任意のサイズに変更できるベクタを作るには:adjustable引数を追加します。
可変ベクタに限界を越えて要素を追加するには、vector-push-extendを使います。

CL-USER> (defparameter *vec* (make-array 5 :fill-pointer 0 :adjustable t))
*VEC*
CL-USER> (vector-push 'a *vec*)
0
CL-USER> *vec*
#(A)
CL-USER> (vector-push 'b *vec*)
1
CL-USER> (vector-push 'c *vec*)
2
CL-USER> *vec*
#(A B C)
CL-USER> (vector-pop *vec*)
C
CL-USER> *vec*
#(A B)
CL-USER> (vector-push 'd *vec*)
2
CL-USER> (vector-push 'e *vec*)
3
CL-USER> (vector-push 'f *vec*)
4
CL-USER> *vec*
#(A B D E F)
CL-USER> (vector-push 'g *vec*)
NIL
CL-USER> *vec*
#(A B D E F)
CL-USER> (vector-push-extend 'h *vec*)
5
CL-USER> *vec*
#(A B D E F H)
CL-USER>

久し振りに短くしめます。おやすみなさい。