haskellの練習で数列の問題を解こうとして、(!!)を使いたいことがありました。そのとき、ふと、疑問に思ったのですが、なぜhaskellではリストのインデックスが0から始まる、と考えるのでしょうか?
takeやdropなどを合わせて考えると、1から数えるとした方が、なんとなく、ですが良いような気がするのです。
おそらく、意味があってのことなのだろうと思いますが、なぜなのでしょうか?
-
自分用まとめ ・インデックスが非負整数(集合論による自然数)であると、加法・乗法・整除法が扱える。特にインデックスを整数まで拡張するとき、整数z, 非負整数iについて i = z mod nで z = 0 → i = 0 と対応付けられる。 ・n個の要素の列の部分列を考えるとき、部分列の表記はインデックスiを用いて、(m ≦ i < k)とするのが望ましい。この表記に従うならば、n個の要素の列を(1 ≦ i < n + 1)と表すよりも、(0 ≦ i < n)と表したほうが良い?よくわかんない...…– kazurego7Commented 2018年4月21日 14:47
-
takeやdropも、take m = 0 ≦ i < m , drop m = m ≦ i < n と考えるべき?– kazurego7Commented 2018年4月21日 23:37
-
何故、リストの内包表記[a..b]は、(a≦i<b+1)なんだろう?– kazurego7Commented 2018年4月23日 7:03
4 件の回答
Haskell にかかわらず多くのプログラミング言語ではリストや配列のインデックスは 0 から始める習慣があります。これには歴史的背景や、メモリアクセスに関する最適化のしやすさなどが理由として挙げられることが多いです。
また、私の知る限り、「Haskell では〇〇だから 0 から始めなければいけない」といった、Haskell 個別の理由はありません。単にデザインの問題だと思います。
例えばCにおいてarrを配列だとすると、arr[5]といった配列へのインデックスアクセスは、ポインタ加算及びメモリアクセス*(arr+5)と等価だとみなされるため高速です。arrは配列のベースポインタ(つまり配列の始まりのアドレス)のことであり、+5というのはここではarrの要素の型のサイズ(例えばlongなら8bit)×5をarrに加算するといった意味論になります。0スタートだとここらへんの最適化処理が簡単になりますというのが極めて一般的な回答だと思われます。
しかしおそらくそれだけが理由でhaskellの言語設計者が0スタートをよしとしたのではないと思います。コンパイラ設計者が頑張れば実はインデクスが1スタートでも問題がないです。だってarr[5]を*(arr+4)と解釈させればいいのですし、例えばfortranも1でスタートしてますよね。
(純粋関数型言語haskellの)設計者たちは必ず次のようなことを考えたはずです。
「宣言的記述arr[5]が命令的にどう実行されるかは重要ではない。6番目の要素を指すべきか、5番目の要素を指すべきなのかが宣言的記述として重要だ。」
そうした判断を踏まえたうえでゼロスタートのほうが好ましいと判断したのではないかとまず考えます。
僕はゼロスタートが採用されているのはメモリアドレスなどのハードウェアが理由ではなくコンピュータサイエンスと親和性の高い数学の集合論に基づいた結果だと考えます。集合論において自然数はゼロから始まります。ラムダ計算におけるチャーチ数や集合論における自然数の定義を見て頂ければわかりますが、ゼロから始めないとマッピングが汚くなります。そのことを踏まえて上記のCの例をもう一度見てもらいたいのですが、宣言的記述arr[5]が命令的記述*(arr+4)にマッピングされるというのは集合のマッピングとしてやはり汚いと思います。宣言的か命令的か、そして綺麗汚いというのは所詮相対的なものですが、上記のような「勝手に引数がデクリメントされる」ようなマッピングを正とすると非常に実装がナーバスになると思いませんか?
個人的所感では納得頂けないとは思うので、ダイクストラ先生の意見も引用いたします。
http://www.cs.utexas.edu/users/EWD/transcriptions/EWD08xx/EWD831.html
-
ご回答ありがとうございます。「宣言的記述arr[5]が命令的にどう実行されるかは重要ではない。6番目の要素を指すべきか、5番目の要素を指すべきなのかが宣言的記述として重要だ。」に対して、「宣言的記述arr[5]が命令的記述*(arr+4)にマッピングされるというのは集合のマッピングとしてやはり汚いと思います。」が矛盾しているように感じられました。現在、参考URL先の「Why numbering should start at zero」を読んでおります。 Commented 2018年4月21日 7:00
-
部分列の表記において、下限を含む理由は分かったのですが、上限を含まない理由の「inclusion of the upper bound would then force the latter to be unnatural by the time the sequence has shrunk to the empty one.」の部分がよくわからないです。 Commented 2018年4月21日 7:07
-
-
すいません、発想力が貧困なものであまりよくない例示をしてしまったようです。まずhaskellは関数型言語なのでチャーチチューリングテーゼ、つまり計算可能なプログラムは帰納的関数のクラスであるということと、機能的関数の定義が集合論に基づいており、ゼロスタートであること(つまり初期値を0という特別な値に格納し、関数適用の繰り返しによって1,2,3とイテレーションするイメージ)、また集合論に則さない1スタートのインデックスを実装したならば、ポインターの例のように実装上の不便が生じており、これは単に実装上の問題だとか、命令的記述の問題だとかではなく集合論のマッピングとして崩れているからそんなことになっていると言いたいわけです。 Commented 2018年4月21日 8:07
-
例えばarr[1]はarr[1+0]と同じであるべきだと考えると、加減算含めインデックスに使用する自然数集合を最小化することを考えるならば0からインデックスを始めたいわけです。インデックスの集合として1も1+0もokだけど0はダメというのは美しくない。これが私が汚いと言っているものの正体だと思います。 Commented 2018年4月21日 8:18
自然数を0はじまりで考える。つまり最初は0ということではないかと思います。
加法演算の単位元0を含めておいたほうがいろいろ便利だろうという立場かな?
インデックスは最初の要素からのオフセットだと考えると0から始まるのは悪くない選択でしょう。
-
自然数の話も多少思ったのですが、インデックスにその話を持ってくるのは筋が悪いかなと思ったのと、出典が見つからなかったので私の回答には書きませんでした。もしオブジェクトレベルの自然数も0から始めることに統一するのでしたら、
take
やdrop
もそれに揃えないのは何故だろうという部分も気になります。ありえない話では無いのですが……。– nekketsuuu ♦Commented 2018年4月20日 2:28 -
10始まりか1始まりかの議論だと思ったので、自然数かなと考えました。take や drop の引数はインデックスではなく個数なので、そもそも揃えるという発想がありませんでした。Haskell固有の理由ではなくデザインの問題だとは思います。(個人的には0始まりの方が好きです) Commented 2018年4月20日 12:15
-
ああ。ちょっと思いつきの屁理屈ですが、(!!) = (head .) . flip drop だと思えば、揃っているともいえますね:) Commented 2018年4月20日 13:08