さて、次に紹介するのも高階関数モドキだ。ソーティング関数だ。
Cの標準ライブラリでも配列をソートするqsortと言う関数が提供されているが、g_slist_sortもそれに似ていて、コールバック関数として関数ポインタを受け取る。
g_slist_sortが受け取る関数ポインタの型はGCompareFuncとなっている。
なお、GLibには、このテの「高階関数モドキ」が受け取る関数ポインタの型をCallbacksとしてたくさん定義している。
注意事項。g_slist_sort関数にはGSListとして返り値があるが、同時に受け取ったGSListの順序を破壊的に変更する。性質的にはANSI Common Lispのstable-sortに近い。安定ソートではあるが破壊的だ。
Schemeでは仕様上sortは定義されてないが、実装上、破壊的じゃないsortを採用しているケースの方が多いだろう。
しかし、他の言語でsortを備えてる場合、オリジナルのリストをそのまま保持しておくより、オリジナルのリストそのものを破壊的変更するケースが多い。
と言うのも、リストを2つ保持しておくのはメモリ効率が明らかに悪い、と言う事情に由来する。例えば、30,000も要素を持つリストに対してソート済みのリストを別に生成する、ってのはかなりの確率で無駄だ。大体、データには「整然と並んでて欲しい」ケースの方が通常は多く、「ぐちゃぐちゃの状態のデータを取っておきたい」って事はほぼ無いわけだ。
よって、関数型言語ユーザーだと信じられないだろうが、現実的なエンジニアリング言語では「ソート前の状態」なんぞ保持しないケースの方が多い。
よって、この辺は関数型言語に慣れてるとピットフォールなんで注意してた方がいいだろう。
g_slist_sortの使用例は例えば次のようなカンジだ。
原理的にはsorting関数の類は高階関数で、「どういう比較をするか」をコールバック関数として与えなければならない。ここではコールバック関数としてmy_comparatorと言う関数を定義している。
心臓部はg_ascii_strcasecmp関数で、gchar*(文字配列)をアスキー文字で大文字小文字を無視して比較し、結果をgintとして返す。
GLibだと事実上、これくらいが提供されている「文字配列」の唯一の比較関数だ。と言う事は、「日本語の文字列」に関しては自作したりせなアカンくなるだろう。
と言うのも以前チラっと書いたが、C言語の仕様上、C99までは、デファクトスタンダードであるUTF-8を扱えない。C11以降だとまた違ってくるが、いずれにせよ、「過去の仕様を含み対応をしている」GLibだとこれ以上はどうしようもないんだ(笑)。
結果、ASCII文字以外をどうにかする場合、「最新仕様の」Cに含まれてるstrcmp系関数を上手く使うか、あるいはUTF-8をエンコード/デコードする別種ライブラリを持ってくるか、と自分で何とかせなアカンくなる。
いずれにせよ、ソーティングには「比較」が絡んでくる。
また、上のコード例の通り、g_slist_sortは返り値があるにせよ、「破壊的変更」が前提な以上、何らかの関数の引数に直接g_slist_sortによる「計算結果」を手渡すより、変数listに再代入した方がいい。
じゃないと、「どっかでソートにより破壊的変更が成される」と言った事になるんで、場合によっては見つけにくいバグの原因になるだろう。
この辺の事が気になる人は、g_slist_copy/g_slist_copy_deep辺りを使ってオリジナルのGSListをコピーして、そっちのコピーをソーティングすればいいと思う。
なお、上記のコードをRacketのようなLispで書くと、
(define lst (cons "Chicago"
(cons "Boston"
(cons "Albany" '()))))
(set! lst (sort lst string<?))
(printf "The first item is now '~a'~%" (car lst))
(printf "The last item is now '~a'~%" (last lst))
って事だ。
次はLispのmemberにあたる関数、g_slist_findとその亜種だ。
これは、データを含んだ部分GListを返す、と書いてある。
結果、Lispで言うmemberそのまんまだ。
使用例は次のようなモノだ。
g_slist_findはオブジェクトが同一かどうかを調べるので、実質的にはSchemeのmemqに近い。
従って、例によって、g_slist_prependにg_string_newを使った生成式を直接ツッコむより、オブジェクト定義は外部に置いてそれを参照した方が良い。
また、g_slist_findは「目的のオブジェクトが見つからなかった場合」NULLを返す。
と言うわけで、後続の処理によってはセグフォを起こす事があり得るんで、何らかの新しいGSListを作っておいて、そこに結果を代入して、継続処理を決める、と言うようなプログラミングの方が安全かもしれない。
上のコードのdelta云々、はそういう「見つからなかった場合」のデモンストレーションになっている。
g_slist_findに関する注意点はその程度だ。
そして、g_slist_findよりも汎用的なのが、g_slist_find_custumだ。
g_slist_find_customは三引数関数で第一引数には対象のリスト、第二引数には「探したいデータ」、そして第三引数にコールバック関数(関数ポインタ)を受ける。
と言う事は、g_slist_findのように「オブジェクトの同値」と決め打ちじゃない。コールバック関数の設定次第では受け取ったオブジェクトの「内情」を調べるように書くことが可能だ。
そして、ここでは「コールバック関数」は二引数以下の関数だと仮定されている。一引数関数なら第二引数にNULLを置くが、二引数関数なら、その第一引数にリスト、そしてその第二引数にg_slist_find_customの第二引数がそのまま渡される。
それで、関数my_finderは二引数関数でコールバック用だ。ここで関数としては「GString *」型を受け取ると仮定してて、そこからstrフィールド/スロットを引きずり出して、g_ascii_strcasecmpで比較してる。
なお、上のコードはRacketのようなLispで書くと、次のような意味だ。
(define lst (cons "first"
(cons "second"
(cons "third" '()))))
(printf "This should be the 'second' item: '~a'~%"
(car (memq "second" lst)))
(printf "Again, this should be the 'second' item: '~a'~%"
(car (member "second" lst string=?)))
(define item (memq "delta" lst))
(printf "'delta' is not in the list, so we get: '~a'~%"
(if item (car item) "(null)"))
さて、Lispのmemberみたいな関数がある、って事は連想リスト検索関数assocも書ける、って事だ。かなり酷いコードにはなるが(笑)。
連想リストの定義が冗談みてぇに酷い状態になっている(笑)。まぁ、そこは置いておこう。
連想リスト検索関数g_slist_assocは単純にはg_slist_find_customをラップするだけ、だ。g_slist_find_customもLispのmemberよろしくアイテムを見つけたらそこを含む残りのGSListを返す、ってのは既に見た。
と言う事は、assocを成立させる為にはそこのcarを取ればいい。GLibならdataフィールド/スロットを返せばいいだけ、なんで発想的には難しくはない。ただ、そのdataフィールド/スロットもGSListなだけだ。
だからg_slist_assocは「連想リスト検索関数」なので、コレの返り値は自然とGSListになる。
あとは、アイテムが見つからなかった時、だ。アイテムが見つからなかった時にdataフィールド/スロットを返そうとすると、例によってセグフォが起きる(何故ならその時点でNULLを指してるからだ)。
よってg_slist_find_customがNULLを返す時(つまりアイテムが見つからなかった時)にはそのままNULLを返させて、そうじゃない場合はdataフィールド/スロットを返すように書く。
そしてg_slist_assocの第三引数に渡すコールバック関数の書き方の方にむしろ工夫がいる。前提が連想リストな以上、第一引数item1に渡されてくるのはGSListだ。よってその先頭要素を取り出したモノと第二引数item2を比較せねばならない。この「比較の為のコールバック関数は連想リスト想定」ってのがこのプログラム上の肝となるんだ。
あとは、連想リストの定義はクソだが(笑)、実行結果自体は「想定通り」の結果になるだろう。
連想リスト上で"hi"と3、"you"と8はキーとデータとして結びついている。一方、"i"はどれとも結びついていない。
Lisp系言語で「お馴染みの」結果を得ることが出来る。
当然(ある程度プログラムを書き換える必要はあるが)、１つのキーに対して２つの値を持ってる連想リストにも対処出来る。
相変わらず連想リスト設定は酷いが(笑)、一応キーが1のリストを取り出す事が出来る。
数値比較のコールバック関数は、割に典型的な、Cの標準関数のqsort相手での作成法と同じだ。
とは言っても、これはあくまで「連想リストもプログラム出来る」と言った例であり、実用性はない(笑)。なんせ連想リストを「打ち込む」のがクソ面倒くさいし、こんな事をやるなら(そのうち紹介するかもしれないが)GLibのハッシュテーブルを利用した方が遥かにマシだろう。
最後の例としては、Lispには備わっていない「挿入」を紹介する。
Lispだと「consセルの繋ぎ替え」は再帰的にcar、cdr、cons、appendなんかを駆使して行い、「ポインタ連鎖」を破壊的につなぎ替える事はあまりしない。
一方、C言語による「データ構造とアルゴリズム」の宿題的な意味では、そのテの破壊的変更を前提としたコードを作る。
基本はg_slist_insertで狙った場所(インデックス)に要素を挿入する。g_slist_insert_beforeは狙った場所(インデックス)の「前に」要素を挿入する。
そしてg_slist_insert_sortedは高階関数的で、ソーティングされた順番に従って、適切な位置(インデックス)に要素を挿入しようとする。
どれも、g_slist_sortと同様に、「返り値はあるけど破壊的な」関数になっている。よって使用時には明示的に変数に「再代入」する使い方をした方がいい。じゃないとバグの温床になるだろう。
いずれにせよ、これらはLispではあまり見かけない関数だ。割にリストの「内臓」を直接手で甚振ってる印象で、個人的にはかなり気持ち悪い(笑)。
ただ、連結リストを「宿題で実装した」って人にはお馴染みの機能なんだろうから、最後に紹介した。
俺は使わんだろうなぁ(笑)。
あとは若干余談を書いていく。
まずはg_slist_prependと言う構築子。これは機能的にはほぼLispのconsと同じだ。しかしハッキリ言って使いづらい。
原因はハッキリしてる。Lispのconsと引数順序が違うから、だ。
それだけ、で、リストの先頭に近ければ近いほどその要素の記述が後ろへ行く。
「関数の引数順序なんてどーでもいい」って人もいるだろうが、実は極めて重要なんだ。引数順序の設計とは、その関数を連鎖して書いた時に苦にならない順序にする、と言う大原則がある。g_slist_prependはその原則に違反してるんで、こうも使いづらく、結果、必要性もないのにリストへの再代入、と言う記法が蔓延せざるを得ない理由になっている。
恐らく、引数順序をg_slist_appendと同じにしたい、と言う理由なんだろうけど、そういうのはbad designだと思ってる。g_slist_appendとは要素を追加する方向が違う。
よって、こういう「統一性」ってのは悪い統一性だろう。
単純な解決策はg_slist_prependをラップしてしまうことだ。このように。
たったこれだけ、つまり引数順序を取り替えるだけ、でおっそろしい程GSListは構築しやすくなる。
書く量、つまりタイピング量は全く変わらないのに、g_slist_prependに比べるとg_slist_consの方が「見やすい」し「意味が分かりやすい」だろう。GSListの「要素順」と「記述」が一致してる。
こういう「何でもない」ように見える事が、プログラムの構築しやすい/しづらいに関わってくる、ってのが良く分かると思う。
また、別にC言語やGLibに限った話じゃないけど、特定のプログラムを書く際に、ある言語の提供ライブラリ関数の「引数順序」に難を覚えた場合、こうやってラップして「引数順序を交換してしまう」ってのは「アリ」なんだ。
何も我慢して「提供されたままで」使う必要はない。ソースコードの「見栄え」が良くなるんだったらラッピングは積極的に行うべきだと思う。
次、「なんでLispのlist関数にあたる関数がないのか?」って問題もある。list関数があれば、g_slist_prependやg_slist_appendを使いまくらなくても、簡単にGSListが構築出来るのに、と。
> (list "Albany" "Boston" "Chicago")
'("Albany" "Boston" "Chicago")
>
これは単純に言うと、stdarg.hで#includeするC言語の可変長引数機能がおっそろしく使いづらいから、だ。
そこへ行く前に、Lispのlist関数の一般的な定義を見てみよう。
Schemeなんかではこんなカンジだ(※1)。
(define (my-list . args)
(if (null? args)
args(cons (car args) (apply my-list (cdr args)))))
リスト生成は原則、再帰だ。そもそもリスト構造自体が「再帰的なデータ構造」なんで(GSList同士がリンクを張ってる事を鑑みれば当然だろう)、至極自然な関数定義となる。
ところが、やれないワケじゃないんだけど、C言語で再帰は書きづらい。少なくとも「可変長引数処理」に於いて、そのシステムが再帰と相性が悪いんだ。
C言語だと可変長引数を設定した場合、その引数群はリスト「モドキ」に纏められる。それがva_listと言うマクロなんだが、例によってこいつには終端がない。つまり、可変長引数を受け取ってもその長さが分からない、と言った欠陥を抱えている。
欠陥なんだよ。こういうバカな設計のままにしてる、ってのは(笑)。
「C言語を扱えばメモリが分かる」んじゃないんだ。剥き出しのメモリだと単にこういう設計上の不具合に遭遇するばっか、って事になる。
終端を持たないような「配列」なんざ使い勝手が悪くてしゃーないわ。
しょーがないんで、例によって、C言語でよく使われるテクニック、つまり引数として長さを与えると言う形式にしよう。そうすれば、関数としてはLispのlist関数とmake-list関数を混ぜたようなカタチになってしまうが、反面、実装は簡単になる。
単純にはva_listと言うマクロでポインタ変数を宣言し、va_startマクロでポインタ変数と可変長引数の「先頭アドレス」(この例だとdataだ)を結びつける。
dataは可変長引数の先頭アドレスなんで、g_slist_appendを使って(Lisp的表現だが)NULLにdataをconsしてしまう。
いや、実際はconsじゃなくって逆consしてるんだけど、それはconsだと逆順のGSListが生成されてしまうから、だ。最後にreverseするのも何なんで、g_slist_appendを使ってるわけだ。
そしてループに入る。va_startは返り値がないんで、先頭アドレスだったdataを使ったが、va_argはポインタ変数を型分(ここではgpointer型)だけ一個進め、しかもそこの値を返してくれるんで、それを使ってGSListにg_slist_appendしていくわけだ。
ループが終了すれば、まずはva_endでポインタ変数を解放する。
あとは、生成したGSListを返せばいい。
実行例はこんなんだ。素でg_list_prependを使用するよか全然見やすいコードが書けるだろう。
マジでこれが組み込みだったら連想リストも簡単に書けるのに、と歯ぎしりしてる(笑)。
まぁ、だからこのテの簡単なユーティリティは、是非とも自分で作ってライブラリ化してた方が使い勝手は上がるよな、って話だ。
そして最後の余談。
GSListのような「片方向連結リスト」はLispのリストに近い。近いがそのもの、ではないんだ。
何故なら、Lispなら次のようなリストを作る事が出来る。
> (cons 1 2)
'(1 . 2)
このリストのcdr部はリストじゃない。この場合2は単なる整数データだ。
Lispではこういうリストをドット対とかドットペアとか呼ぶが、こういうデータをGSListは作れない。Lisp用語で言うcdr部は、NULLを指せる以外は必ずGSListじゃないとならない。
こういうコードを書くと、gccやclangのようなコンパイラは通してしまうけど、明らかに危険なコードだろう。想定外の使い方な筈だ。
これは結局、「ポインタ変数が保持してるアドレス」の正体が何だかんだ言っても整数値以外の何物でもないから、誤認で実行している。つまり、GSListと指定されたポインタに、何でもいいからアドレス値を渡すと実行してしまう、と言う一種バグだろう。
いや、あるいはC言語は静的型付け言語、と言いながらその型付けは弱い。所詮全て整数値塗れで、なおかつ本当の意味で型情報も持たない。C言語の設計の危険な部分がモロに出てるのが上のコードの「実行可能」な部分なんだ。
いずれにせよ、原理的にはGSListではドット対は作れない。と言うか作ろうとしてはいけない。
じゃあ、Lispはどうしてるのか、と言うと、原理的にはGSListの定義に似てるが、GLib風に言うと大まかにはこういう定義になってると思えばいい。
まず、gpointerと言う「何でも指せるポインタ」をsex型、として定義する・・・いや、sexってアレじゃないよ(笑)?S式(S-expression)の事だ(笑・※2)。
そしてS式の定義は次のようになっている。
- アトムである事。あるいは、
- x, yが共にS式で(x . y)と言うドット対である事。
アトム、とはLisp用語(なだけではなく、Prologなんぞも採用している)で、コンスセルじゃないモノ、を指す。つまり具体的には数値や文字列等の、事実上リストじゃないモノをアトムと言う。
そして、S式の定義にはコンスセルが含まれる。と言う事は、事実上S式の定義そのものが一種の再帰的定義であり、結局S式の定義にコンスセルが含まれる以上、cdrは「何でも指せる」(sex型 = )gpointer型なんで、cons_cellと言うデータ型も指せる、って定義になる。
まぁ、プラクティカルな意味で言うと、こんな単純な定義ではないんだけど、GSListの「構造体定義」とLisp実装の「基礎」は似てはいるんで、余談として書いておく事としたわけだ。
と言うわけで、GSListの基本的な使い方は以上、だ。
あとは自分で色々と弄ってみて欲しい。
※1: これは「関数型言語による杓子定規なリストの定義」であって、実際のトコ、例えばSchemeでは
(define (my-list . args)
args)
と書くだけで終わってしまう。
と言うのも大方のLispでは、「可変長引数はリストに纏められる」と言うのを仕様としていて、可変長引数自体がリストに深く関係して設計されている事。
また、引数リストだろうが何だろうが、全てがリストを基礎としてシームレスに設計されている以上、可変長引数如きで「例外」が生じないから、だ。
フツーの言語だと、プログラムの式に現れる括弧と、関数引数を表示する為の括弧が「構文上意味が異なる」と言う事があり得るが、Lispにはそういう「意味の違い」が生じない(と言うか「生じる筈がない」)設計を用いてるんだ。
※2: 良くある表記法で、Sexpとかが使われるが(多分このようにSexと誤認されるのを避ける為だろう・笑)、ところがLispに慣れてると、語尾のpはpredicate(述語)のpとこれまた紛らわしく感じるんだ。
つまり、「セックスですか?」って訊かれてるように感じる(笑)。バカにしてんのか、とかムカムカしてくるんだ(ムラムラ、ではない・笑)。
まぁ、そんなワケで、どっちにしてもムカつくのなら漢らしくsexでエエやろ、って思ってる。
なお、expressionは本来なら「表現」の事で、こだわる人は「S表現」と訳したりする。
一方、「式」は数学的にはequationが正しい。しかし、Lispに限らず、プログラミングでは通例、expressionは「式」と訳すようだ。
言っちゃえばこれも誤訳なんだけど、かなり恣意的で、結局「数学が得意な日本人」の誰かが、敢えてexpressionを「式」と訳したんだろう。
数学が得意な(貴方が自覚が無くても、世界レベルでは「数学が得意な」方なんだ)日本人の面目躍如だ。
