空の区間はすべて等しいか

経緯

社内で勉強会を開いていて、こんな話をしました。

$l \leq x \lt r$ のような片側の端点だけを含む区間を半開区間といい、$[l,r)$ のように表記します。
配列のスライス（連続する部分列）を表すときは、半開区間を使って「$l$ 番目から $r$ 番目まで（$l$ 番目を含み、$r$ 番目を含まない）」とすると便利です。この方法のいいところは、 $l = r$ とすれば空の区間を表すことができ、それを要素と要素の間を表すのにも使えるという点です。たとえば $[0, 0)$ は最初の要素の直前、$[1, 1)$ は最初の要素と $2$ 番目の要素の間、$[N, N)$ は最後の要素の直後、といった具合です。¹

ここまで説明したところで、聴衆の数学ガチ勢からツッコミが入りました。「それはおかしい、まるで $[1, 1)$ と $[3, 3)$ が異なるものだと言っているように聞こえる。」

......なぬ？空の区間で要素と要素の間を表すと言ったからには、確かに $[1, 1)$ と $[3, 3)$ が異なるものだと言っていることになります。どこかおかしいでしょうか？

ここで区間の定義を見てみましょう。

区間とは

Wikipedia で「区間（数学）」を引いてみると、このように定義されています。

半開区間（左閉右開）
$[a,b):= \lbrace x\in \mathbb {R} \mid a \leq x \lt b \rbrace$

この定義に従えば、 $[1, 1)$ と $[3, 3)$ はどちらも空集合なので等しいことになります。区間はその端点で特徴づけられると私は思い込んでいたのですが、実際には区間は集合の一種に過ぎないので、その要素で特徴づけられるべき（c.f. 外延性の公理）だったわけですね。

インデックスのペアで区間と要素の隙間の両方を表すというアイデアは有用ですが、説明にあたっては数学上の区間と結びつけることは避けたほうが賢明でしょう。

諸言語ではどうなのか

脚注 ¹ の通り、C++ は伝統的に範囲をイテレータの組で表してきました。プログラマは最初に会った言語を親だと思いこんでついていく習性がある（要出典）ので私はこんな勘違いをしてしまったわけですが、諸々の言語ではどうなっているのでしょうか？

C++

C++20 から ranges が導入されたようなので試してみます。こんな感じかな？

#include <iostream>
#include <ranges>
#include <vector>

using namespace std;

int main() {
    auto view1 = ranges::iota_view(1, 1);
    auto view2 = ranges::iota_view(3, 3);
    bool result = view1 == view2;
    cout << result << endl;
}

prog.cc: In function 'int main()':
prog.cc:10:25: error: no match for 'operator==' (operand types are 'std::ranges::iota_view<int, int>' and 'std::ranges::iota_view<int, int>')
   10 |     bool result = view1 == view2;
      |                   ~~~~~ ^~ ~~~~~
      |                   |        |
      |                   |        iota_view<[...],[...]>
      |                   iota_view<[...],[...]>

抜かりなくコンパイルエラーになりました。std::ranges::subrange も試してみましたが、やはり == は定義されていませんでした。あと一昔前に比べてコンパイルエラーが見やすくなっていて感動する。

Scala

Scala には標準の scala.collection.immutable.Range クラスがあります。

scala> (1 until 1) == (3 until 3)
val res0: Boolean = true

空の区間は等しいと判定しました。コードも見てみましょう。

  final override def equals(other: Any): Boolean = other match {
    case x: Range =>
      // Note: this must succeed for overfull ranges (length > Int.MaxValue)
      if (isEmpty) x.isEmpty                  // empty sequences are equal
      else                                    // this is non-empty...
        x.nonEmpty && start == x.start && {   // ...so other must contain something and have same start
          val l0 = last
          (l0 == x.last && (                    // And same end
            start == l0 || step == x.step       // And either the same step, or not take any steps
          ))
        }
    case _ =>
      super.equals(other)
  }

Scala の Range は (始点, 終点, 刻み幅, 終点を含むかどうか) の 4 パラメータからなります。 Int.MaxValue を越える長さの区間にも対応するためちょっとややこしくなっていますが、正しく動いていそうです。終点を含むかどうかのフラグを参照していないのが気になりましたが、終点を含まない場合あらかじめ終点から $1$ 引かれているらしく、期待通り動きました。

Python

>>> range(1, 1) == range(3, 3)
True

空の区間は等しいと判定しました。リファレンスにも詳しい説明があります。

== および != による range オブジェクトの等価性の判定は、これらをシーケンスとして比較します。つまり、二つの range オブジェクトは同じ値のシーケンスを表すなら等しいとみなされます。(なお、二つの等しいとされる range オブジェクトが異なる start, stop および step 属性を持つことがあります。例えば range(0) == range(2, 1, 3) や range(0, 3, 2) == range(0, 4, 2)。)

Ruby

irb(main):001:0> (1 ... 1) == (3 ... 3)
=> false
irb(main):002:0> (1 ... 1) == (1 ... 1)
=> true

ここに来て区間の同値性を両端点で判定する言語が見つかりました。単にオブジェクトの同一性を判定している（(1 ... 1) はインスタンスがキャッシュされている）だけかもと思いましたが、 __id__ が異なっていたのでちゃんと同値比較をしています。

Range クラスのある馴染み深い言語を調べてみましたが、必ずしも挙動は一致しないようです。他の言語の事情も気になるところ。このあたり、あらぬバグの原因になるかもしれないので注意したいですね。

設計思想

同値比較だけを見ると Ruby は数学的直感に反するように見えるかもしれませんが、そもそも諸言語の Range を数学上の区間と同一視していいのか、というところも気になってきます。というのも、「区間」は英語で interval であって、 range ではないからです。

Scala の Range クラスの定義を見てみると、 Seq[Int] (配列のように振る舞うクラスの共通インタフェース)　を継承しています。 (0 until 10).contains(5) は true ですが、 (0 until 10).contains(5.5) は false です。また、 $[0.5, 1.5)$ のような実区間も表現できず、コンパイルエラーになります。

Python の挙動も Scala と同じです（range(0.5, 1.5) がコンパイルエラーではなく実行時エラーになるという違いはありますが）。したがって、Scala と Python の Range は整数列の略記法と捉えるのがいいのでしょう。

一方 Ruby では (0 ... 10).include?(5.5) が true になります。実区間だ！......と考えるのも早合点です。Ruby の Range は ('aa' ... 'zz') のように、文字列を端点とする区間、すなわち離散区間も作れるからです。

include? の他に cover? というメソッドもあります。 ('a' ... 'c').cover?('ab') は true を、 ('a' ... 'c').include?('ab') は false を返します。 'a' <= 'ab' < 'c' なので cover? は true で、 ['a', 'b'].include?('ab') ではないから include? は false のようです。ただし、「数値については、例外として Range#include? も連続的に扱います。」との記載もあります。

こうして見ると、Ruby の Range (l ... r) は $ \ \lbrace x \ | \ l \leq x \lt r \rbrace$ としての面と、 $\lbrace x \in \lbrace l, \text{succ}(l), \text{succ}(\text{succ}(l)), \ldots \rbrace \ | \ x < r \rbrace$ としての面の両方を持っていて、どちらを適用するかはメソッド自身が選択していると言えそうです。そうなると、データモデルとしての Range は両端点のペア以上の何者でもないように思われ、両端点で同値比較をすることも合理的に思えてきます。

Python のようにそれが含む要素によって特徴づけるものを「区間 (interval)」、Ruby のように両端点によって特徴づけるものを「範囲 (range)」と呼んで区別するのが綺麗なのでは、という気もしてきますが、Interval クラスという名前を使っている言語は寡聞にして知りません。

数学とプログラミング、近いようでいて意外なところに隔たりがあるもののようです。

1. 実際にこのような形式で、C++ の std::equal_range はソート済み・値の重複がありうるコンテナの中から値を検索し、見つかればその値がある範囲を、見つからなければその値を検索順序を保ったまま挿入できるような位置を返します。 ↩ ↩²