From: "NARUSE, Yui" <naruse@...>
Date: 2008-02-15T10:19:19+09:00
Subject: [ruby-dev:33787] Re: Array の product   	の戻り値

成瀬です。

Yukihiro Matsumoto wrote:
	> まつもと ゆきひろです
> 
> In message "Re: [ruby-dev:33752] Re: Array の product  	の戻り値"
>     on Wed, 13 Feb 2008 15:21:51 +0900, "NARUSE, Yui" <naruse@airemix.com> writes:
> 
> |あれから他の方に教えて頂いたのですが、「Enumerator」と「配列的メソッドを
> |備えたもの」は「C++ における Iterator」に一般化でき、その分類によると、
> |* Enumerator -> Input Iterator
> |* 配列的メソッド -> Random Access Iterator
> |にあたるそうです。
> 
> 自分で勉強するべきなのかもしれませんが、最近のC++事情には疎
> いので(私がC++プログラマだったのは10年以上前)、「C++ におけ
> る Iterator」というのはInput IteratorとRandom Access
> Iteratorの他にもいろいろあるんですかね。

あ、参照を張ろうと思って忘れていました。
http://www.kuzbass.ru/docs/isocpp/lib-iterators.html

図にすると以下の通り、

Random access -> Bidirectional -> Forward -> Input
                                          -> Output
それぞれ以下のようになります。
Input: 入力のみ一方向シーケンシャル
Output: 出力のみ一方向シーケンシャル
Forward: 入出力一方向シーケンシャル
Bidirectional: 入出力双方向シーケンシャル
Random access: 入出力ランダムアクセス

ちなみに、boost だとちょっと変わって、
Incrementable -> Single Pass -> Forward Traversal
-> Bidirectional Traversal -> Random Access Traversal
http://www.boost.org/libs/iterator/doc/new-iter-concepts.html
となっていますが、区別の本質は同じですね。

> |* だから、「配列的メソッド」を備えた Enumerator、
> |　つまり Indexer が欲しい。
> |* なお、「配列的メソッド」のキモは [], []=, length であり、
> |　これらが実装されていれば、あとはそれを用いて実装できる
> |ということが言いたかったのです。
> 
> うーん、lengthが必須であるならば配列にしてしまっていけない理
> 由があまり思いつかないのですが。メモリ効率？

まず、メモリ効率と実行効率両方です。これは String.bytes が返す Indexer
の場合がいい例かと。

次に、実体を一つにしたいというケースです。これも String.bytes の例です
が、これが整数列を返す場合、これにたいして書き込みを行っても元の String
が変更されません。

加えて、独自のメソッドを追加したい場合です。Array のインスタンスに特異メ
ソッドを使う方法は面倒ですし、Array を継承した場合は [] を再定義しても
first が依存していないのでこれも使えません。独自クラスに Indexable を
include する方法ならば、これもすっきりします。

> lengthがないならばLazyなList が作れるという理由が思いつくのですが。

Requirements については議論の余地がある点だと思っています。今回 length
を加えたのは String.bytes が返すものに対しての採用を期待しているからで、
そのために length が必要になりました。
length や []= のない Indexer というのも存在しうると思っていますが、まず
は目下欲しい String.bytes に必要なメソッドとして、[], []=, length を挙げ
ました。

> もうちょっといろいろ議論しないと、なぜRandom Access Iterator
> が必要なのか見えてきません。

目下の主張としては、[ruby-dev:33447] の
> うーん、どうしようかなあ。専用クラス化した方が性能が上がると
> かいいこともあるんですがねえ。でも、byteアクセスとbyte列挙子
> を同一視することになんとなく抵抗感があります。
についてで、「byteアクセスはbyte列挙子の延長にある」というものです。
String.bytes.each{|x| p x}
String.bytes[idx]
String.bytes[idx]=
はそれぞれ自然なものであるというのが第一の主張です。

よって String.bytes は Random Access Iterator を返すべきというのが第二。
それを Enumerator につっこむのはさすがに違いすぎるだろうから Indexer と
いう別のものにしよう。
他のオブジェクトにも使えるだろうから Indexable もあるといいね。
ところで、String.bytes 前提だと length が必要だね。
となって、今に至るという感じでしょうか。

-- 
NARUSE, Yui  <naruse@airemix.com>
DBDB A476 FDBD 9450 02CD 0EFC BCE3 C388 472E C1EA