前回記事は理解不足を元に書いた部分についてあれこれツッコミをいただいたり、言及してもらったりして、色々勉強になりました。ありがとうございます。
せっかくの機会なので、いただいたツッコミをまとめたり、思うところを不勉強なりに述べてみる。
- 404 Blog Not Found：List は Array にあらず
- http://blog.livedoor.jp/dankogai/archives/50834465.html
Listが Sequentially Accessible なのに対し、 Array が Randomly Accessible だというのが、その違いだ。n番目の要素にアクセスする手間がO(n)なのかO(1)なのかという違いと言ってもいい。特に大きなデータを扱うに当たっては、この違いは意識せざるを得なくなってくる。
補足を書くときに、きっとそういうことなのだろうなあと思いつつ、さすがにそこに推測を重ねるわけにはいかず。おかげで明確になりました。
n番目の要素にアクセスするコストが「O(1)のものだけある」場合と「O(1) と O(n) の両方が用意されている」場合(いわゆる配列とイテレータとか。ちょっと違うけど DOM と SAX とか)は見知っていたわけだが、「O(n) のものだけある」という経験はなく、それを特別に感じてしまったというのがハズしてしまったポイントだったわけだ。
とはいえ、関数型言語未通過の人だと同じように「O(n) のものだけある」経験がないだろうから、そういう人に向けて手続き型とはいろいろ違うんだよ！ という周知のきっかけになったという意味はあった……と思いたい。
もっとも、Erlang の List はその「n番目の要素にアクセスする」方法さえ用意されていない（「リストのｎ番目に値を設定する」関数が存在していない）わけだが……。*1
あと Java には "ArrayList" なるものが……
- lethevert is a programmer - Erlang ： 配列
- http://d.hatena.ne.jp/lethevert/20070519/p1
とりあえず、先に、これ（http://ancient.s6.xrea.com/erlang/cookbook.html#Ref%3C0.0.0.49%3E）を読んどきましょうね。
Erlangで配列のようなものが欲しければ、リストではなくてタプルかバイナリを使いましょうね、ということではないかと。特にタプルは、関数的な人が想像するあれとはちょっと違う感じがするので注意。
Erlang のタプルには確かにいくつか「配列っぽい操作」が用意されているわけだが、タプルそもそもが繰り返し処理に使えるデザインではないので、いわゆる「配列」とはかけ離れていると認識している。Array と List が違う以上に、Array と Tuple は違う。
もちろん、その「配列っぽい操作」を使えば、Erlang ではタプルで繰り返し処理を記述することは可能だ。インデックスを再帰でインクリメントしながらタプルのサイズに達するまで繰り返せばいい。でもそれって、手続き型言語ならまだしも、仮にも関数型言語では許容しえないほど不自然なコードのように思えるのだが……これも勘違いだったりする？
あと、Erlang のバイナリを配列代わりに使う、というのは全く方法が想像つかなかった。実はうまい方法がある、と教えてもらえたりなんかするととても嬉しい。
なお、ここだけ読んじゃった人のための補足。Erlang のタプルに用意されている「配列っぽい操作」とはサイズの取得・n番目の要素へのアクセス（読み、書き≠上書き）・要素の追加などであり、いわゆる「配列」によくあるソートや逆順や連結、リストにある map や filter などはさすがにない（タプルのソートってほんまにあったら気持ち悪いなあ）。
*1:ちなみに自作すれば確かに O(n) となる
