星田さんの記事に対するコメント。
おおっ！？要素の任意の場所をソートの対象に出来るのか・・carを使った指定もシンプルで素晴らしい！これがあるんだったらますますレコード型いらないような(^_^;)
うん。Lisperはそう考えたがる(笑)。リストサイコー!(笑)。
ただし、だ。
以前書いたような問題があるんだな。
- 定型的なデータが欲しい。リストの場合、「自由過ぎる」ので、同じデータ形式で揃えてたつもりが間違ってデータ項目を増やしちゃったりすると目も当てられない。フォーマットを事故的に崩すのは望んでない筈だ。
- 要素に名前を付けたい。リストは原則、carとcdrで管理するので、欲しい項目が「先頭から数えて何番目にあるか」プログラマが覚えておかないとならないんでメンド臭い。構造体/レコード型なら項目に名前が付けられるので管理が簡易化する。
- スピードの問題。原則、構造体/レコード型は「タグ(名前)付き」配列、あるいはベクタなんで、項目へのアクセスはリストより高速。
例えば。
このデータを学生番号、生徒名、テスト成績と言う3つのフィールド(あるいはスロット)を持つデータ形式として固定したら便利だ、って事もある。
Racketでも構造体のスロット名(あるいはフィールド名)をキーワードとして指定すれば簡単にソートを噛ましてくれるし、Gaucheだと多分こんなカンジ?
安定ソートって？と思ったけどいわゆるいつもファイル操作で使ってるソートだった。確かに不安定ソートって嫌だなあ（自分で作るのは安定版は面倒そうだけど）。
日本だと「安定ソート」って訳語になってて、じゃあ不安定ソートは何が不安定なんだ、とか意味が分からなかったりする(苦笑)。
これは元々stableなんだよな。もちろん、安定、って意味もあるんだけど、むしろ不変なんだよ、この場合。stable sortは不変ソートと訳した方がいいだろとか思うんだけど、毎度毎度感じるのはプログラマって言語中枢がイカれてるんじゃねぇか、って思う程言葉が不自由なんだよなぁ(苦笑)。とにかく言葉のセンスがねぇ。
それでパッと見、意味不明な訳語ばっかになる・・・・・・。
要するに、元データで同値のデータがあった場合でも、順序を元データのままで変えないのを安定ソート、って読んでるわけ。変わっちゃったら不安定ソート。と言う不安定な訳語なんだなこれが。
だから分かりづらい(苦笑)。
> sort
うん、えーと、ちと考え過ぎかも(笑)。
まず、matchは便利なんだけど、これに振り回されすぎないように。
結局ね、挿入ソートはこう書いてもいいわけじゃない。
結局、与えられたリストをlet使って分解するのがメンド臭いからmatchを使ってるだけで、ロジックそのものはフツーの再帰関数と変わらないんだ。
上のifを使ったヴァージョンより短く書けますよ、ってだけでロジックの本質は何も変わらない。
そして一回Racketで確かめて欲しいんだけど、
このケースの場合、確かにnはnを受け継いでる。
Dr. Racketは親切過ぎる程親切なIDEなんで、シンボルをマウスオーバーすれば、使われてる束縛の連鎖が矢印で見える筈。
そして、ここの`(,n)は星田さんが考えてる通り、(list n)って記述のショートカットだ。だから(list n)って書いて当然良い。
ただ、Lisp慣れてくるとこれでも長ぇよ、とか思っちまうんだよな(笑)。だからlistを使うよりは逆クオートを使いたがる(ようになる)。
一方、単に(n)と書いて実行させよう。
うん、これがエラーの正体だ。クオートしない限りリストの0番目の要素は関数じゃなきゃならない。nは関数ではなくって9と言う数値だ。だから「9は関数じゃねぇぞ」って怒られてるわけ。
多分エラーメッセージ自体はRacketの方が詳細でしょ。Gaucheのエラー表示は、
*** ERROR: invalid application: (9)
「間違った(関数)適用です」って言ってて、Racketのメッセージと最終的には同じ事言ってるんだけど、ちと短すぎるよな(笑)。どっちにせよ「9は数値データだけど関数じゃない」から問題が起きてる。
だから(n)と書いてはいけないんだ。
あと、RacketとGaucheのmatchだと空リストの表記方法の違いがある。
Gaucheの場合、は実は空リストをクオートせんでいいんだ。
だからGaucheでは次のように書いても動く。
んで、Racketの前身・・・PLT Schemeでも昔は良かったのね、こう書いても。
で、いつ頃だったかしらん。やっぱ4.0になるかならないか、の辺りでPLT Schemeはこういう「表記の揺れ」を許さなくなって厳格になったわけ。つまりクオート無しの、カッコだけ、の記法で空リストを表現しようとすると、エラーになるようになったわけ。
んで、空リストの扱いは、Gaucheだと()と'()をどっちも同じ意味で受け取ってくれるのね。
だから僕が書いたコードは手癖でRacket寄りになってる。Gaucheに甘えてるわけだ(笑)。
この辺がGaucheとRacketの動作が変わる部分なんだ(※1)。
(let ((hoge ())) (display hoge))
;;; 変数に空リストを束縛する場合、Gaucheだとこれは通るがRacketだと通らない。不自然な例に思うかもしれないが、名前付きletでアキュムレータに空リストを設定する際に、要クオートになるかならないか、と言うのがやはりGaucheとRacketの大きな違いとなる。
> compose
うーん・・(define (h x)...) h ということでhの場所が変だ。内側のdefineからはみ出している。つまり最後は関数hを返り値として返してるってことで・・もしかしてこれが・・これがクロージャーってことなのか！？
その通り、です。
実際は次のように書いても構わないんだけど。
(define (compose f g)
(lambda (x) (f (g x))))
ただ、まぁ、OCamlのコードの直訳を狙うならローカル関数hの定義を利用して、hを返した方がわかりやすいだろう、ってのが一つ(Schemeにはinとかねぇけど、見た目は似てるだろう、って事)。
もう一つは、前回書いた通り、ローカル関数定義に慣れて欲しいから。もう一度書くけど、Schemeだとローカル関数定義を「息を吸うように」行う。
例えば次のようにletrecを利用しても良い。
(define (compose f g)
(letrec ((h (lambda (x) (f (g x)))))
h))
ただ、大方のSchemeユーザーは、letrecを使うよりinternal defineを使う方を好むかな。
いずれにせよ、今初めてOCamlのコードを読んで、Lispで書く、ってのは頭の体操的にも良い訓練だとは思う。
ただね、やるなら負担にならん方がエエだろ、と(笑)。そういう事です。
咀嚼もやりすぎると単なる負担だしね。
※1: Schemeの観点で見てみると、(RacketはSchemeそのものではないが)一体どちらが正しいのだろう?
実は海外のメジャー処理系、GuileやChicken Schemeの場合、Racket同様、()と言う表記は許されない。
じゃあGaucheが間違っているのだろうか。
数値定数、文字列定数、文字定数、ベクタ定数、バイトベク
タ定数、ブーリアン定数はそれ自身に評価されます。quote
する必要はありません。
上はR7RSからの抜粋だが、R5RSでも似たような事が書かれている。いずれにせよ、定数はそれ自体に評価されるので、クオートする必要はないわけだ。
問題は、だ。歴史的経緯に関わる。
要するに空リストは定数なのか否か、って話だ。
SchemeにはNILと言う用語はないが、例えばANSI Common Lispでは空リストとNILと言う特殊なシンボルは全く同じ意味を表す。そしてこれは唯一の値なので確かに定数なんだ。
そしてANSI Common Lispの偽値もNILだ。つまり、ANSI Common Lispでは真はT、偽はNILとなる。言い換えると空リストは偽を表す。
素っ頓狂に思うかもしれないけど、Lispは伝統的にはこういう言語で、すなわち、こういう事が出来る。
こんな演算は現行のSchemeでは出来ない。
Schemeでは空リストと偽値(#f)が分かれてしまったから、だ。
もっと重要な問題がある。
実装上、properなリストを作成すると、最後のコンスセルのcdrはすべてメモリ上同一の特殊な場所、NILを指すようになってるだろう。
一般に、Lisp実装ではどんなproperなリストのケツのcdrでも全部NILを指す。つまり同一の、唯一のメモリ上のとある特殊な場所を共有してる。
その「メモリ上のとある特殊な場所」が空リストの正体だ。
> '(1 2 3 . ())
'(1 2 3)
> '(a b c . ())
'(a b c)
>
;;; Schemeでドットペアで明示的にcdrで空リストを指定すると、フツーのリストに変換表示される。
ところが、Schemeの仕様書だとこの空リスト、つまりNILが具体的に何なのかイマイチ分からない。
一応、R5RSでは次のように書かれている。
空リストは，それ独自の型に属する一つの特殊なオブジェク
トである (ペアではない)。空リストに要素はなく，その長
さはゼロである。
と言う事はクオートを付けなくてもいい筈、なんだ。つまり、GuileもChicken SchemeもR5RSに違反している、って事になるだろう。
一方、この辺がR7RSでは変わってしまった模様だ。
メモ: 多くの Lisp 方言では空リスト () は自分自身に評価される
正当な式です。Scheme ではエラーです。
と言う事は、字面通りに受け取ると、今度はGaucheが確かにR7RSに違反してる、ってことになる。
もう、この辺はホントややこしいし、かつ、「権威がない」仕様書だとこういう細かい辺り(しかも結構重要な部分だと思う)で各実装、食い違いが生じてる。
困ったモンだ。
