2007年05月19日 18:00 [Edit]

List は Array にあらず

無謀というより、もともと違うものを一緒にすることはないと思う。

Matzにっき(2007-05-07)
こういうの(Lazy List)を将来のArrayクラスに突っ込みたいんだけど、無謀かなあ。

そう。もともとListとArrayは別物なのだから。


確かに、List(リスト)とArray(配列)には、Ordered Collection of Data -- 順番に並んだデーター --という共通点がある。この共通点があるが故に、特にLLにおいてはどちらも同じように扱われる場合が多いけれども、重要な違いが一つある。

Listが Sequentially Accessible なのに対し、 Array が Randomly Accessible だというのが、その違いだ。n番目の要素にアクセスする手間がO(n)なのかO(1)なのかという違いと言ってもいい。特に大きなデータを扱うに当たっては、この違いは意識せざるを得なくなってくる。Listはやや不便だが、その代わり全データをメモリーに持っている必要はなく、必要なときに必要なデータを動的に生成しても外部から持ってきてもよい。Arrayはその逆で、便利な代わりに全データをメモリー上に持っていなければならない。厳密にはshiroさん指摘のように、Off MemoryなArrayも可能だけど、実装は楽でなかったり、実装した場合にListより低速だったりもするのでたいていOn Memoryになる。

実は、Perlではこの二つは厳密に区別されている。

my @array = (1, 2, 3);

というのは、「1, 2, 3という配列を@arrayに代入」しているのではない。「1, 2, 3というリストを、配列に変換した上で@arrayに代入」しているのだ。

my $mtime = lstat($filename)[9];

がうまく行かない理由がここにある。これは、

my $mtime = (lstat($filename))[9];

とすればうまく行くが、()がリスト→配列変換演算子だと考えれば納得がいく。

Mi manca qualche giovedi`? - Erlang の得意・不得意
むむむ。ということは Lisper や Heskeler には既知の事実であったか。ということで以下の記事は「Erlang には Ruby/Python/Perl の言う『配列』はないよ!」と読んでいただければ嬉しい。

賢明な方はお気づきのとおり、Perl 5ではそれとは逆に、リストというデータ構造はもっていても、nativeなリスト変数というものを持たない。厳密に言えば、ファイルハンドルがそれに近いが、用途が限定されている上アクセスするのに違う構文を使う以上、それをリストと呼ぶのは不適切だろう。

それで困っているかと、ほとんど困っていない。nativeなリスト変数がなくてもOOがあるので必要とあらばリストとして振る舞うオブジェクトは簡単に作れるし、実装もCPANにいくつも上がっている。そしてtieを使えば、実際はリストなのに配列として振る舞う変数も簡単に作れる(e.g. Tie::LazyList)

こうやって、似ているが違うものを自然に扱うのに、OOはどうしてきたかというと、それぞれに違うクラスを割り当てた上で、同様の操作に対して同名のメソッドを与えるというやり方を取ってきた。それであれば、

head = unknown.shift();

とやった際に、unknownがリストか配列かは意識しなくていい。duck typingが自然にできる。

このやり方の優れたもう一つの点は、片方のクラスにあってはならないメソッドがあった場合にエラーにするということも簡単にできることだ。

tail = unknown.pop();

は、unknownが無限リストだった場合には、エラーにしてくれる方が親切だろう。私がrubyでのけぞったことの一つが、Queueのメソッドにpop()があったこと。Queueというからには、shift()だけできてpop()できないのが親切なのではないだろうか。

結論としては、無限リストを言語の標準仕様ないし標準モジュールとして加えるのは賛成だが、配列に無限リストとしての機能を持たせるのは反対ということになる。Haskellはそうなっているし、Perl 6もそうなっているし(もっとも、my @array is lazyという構文を明示的とみなすかどうかは微妙だが)、Perl 5もCPANまで敷衍すれば、(無限リストを実装しているModuleがすでに複数あるので)そうなっているし、Rubyもgemまで敷衍すればそうなっていると言えるのではないか。

ましてや、Rubyは型の代わりにクラスを持ち、クラスの変換は明示的に行うというタイプの言語である。いちいちstr.to_iとやるのが面倒だとPerl Userは思っても、それがいいところだと思っているRuby Userも多いはず(おかげでこないだRangeでちょっとはまったが)。Arrayに無限リストの機能を持たせるのは、Rubyの魅力をむしろ損ねるものだと思うのですがいかが?

Dan the Lazy Programmer


この記事へのトラックバックURL

この記事へのトラックバック
先日の「LazyListの機能を(Rubyの)Arrayに追加したい」というエントリへの 弾さんのコメント。 まあ、自分でも「このアイディア、サイコー」と思ってるわけではないので、 批判やら指摘やらは歓迎するのだが、 それでも、ListはArrayではない、というのは適切な「読み」で...
404 Blog Not Found:List は Array にあらず 【Matzにっき】at 2007年05月26日 00:15
前回記事は理解不足を元に書いた部分についてあれこれツッコミをいただいたり、言及してもらったりして、色々勉強になりました。ありがとうございます。 せっかくの機会なので、いただいたツッコミをまとめたり、思うところを不勉強なりに述べてみる。 404 Blog Not Found:
[erlang]「Erlang の得意・不得意」その後【Mi manca qualche giovedi`?】at 2007年05月21日 13:05
この記事へのコメント
弾さんでも「はまる」事があるんだなぁ、と何故か少し安心しました。
Posted by azt at 2007年05月20日 14:39
PerlにおけるListが Sequentially Accessible だとお思いなのですか?
自分はLisp等のListとPerlのListは別のものを指していると思っているのですが。、
Posted by H.I. at 2007年05月20日 01:20
shiroさん、
実はそうなのですよね。Perlの場合も、tieでobjectをwrapした場合、「O(1)だけどオンメモリーでない」Arrayが出来上がることもありますし。
ななしさん、
うーむ、Proc.new[arg]に通じるきしょさを感じる。
素直にenqueue, dequeueでもいいと思う(PerlのThread::Queueはそうなっている)。でもqueueって長いのでenq, deqをaliasしとくか。
Dan the Lazy Programmer
Posted by at 2007年05月19日 20:08
Queue#shiftってのはpopへのaliasです。

enq = << = push
deq = shift = pop

経緯は「ruby queue shift」で検索してください。
Posted by ななし at 2007年05月19日 19:58
重箱の隅ですが、「O(1)アクセスであること」と「データを全てオンメモリで持っておくこと」とは直交すると思います。Arrayの性質として重要なのはあくまでO(1)アクセスであると。
Posted by shiro at 2007年05月19日 19:39