all関数が空配列に対してtrueを返すべき4つの説明
少し前に、配列の全ての要素が条件を満たすかどうか判定する関数が、空配列に対してどういう挙動をするべきかが議論を呼んでいました。ネット上にあまりまとまった情報が見つからなかったので、自分なりの説明をメモとして残しておきます。
1: 論理学による説明
一般的な論理学では、空集合に対する全称命題は真とします（Vacuous truth）。これに従うと、定義から空配列に対しては true を返すのが正しいです。 ただ、初めて聞いた人にとってはこれを言われただけではモヤモヤする人もいるかもしれないので、以下はプログラミング的な観点からの嬉しさについて説明します。
2: 自然な実装による説明
Python ライクなコードでの実装例です。
- ループによる実装
def all_of(a: list[T], condition_func: Callable[[T], bool]):
for x in a:
if not condition_func(x):
return False
return True
- 再帰による実装1
def all_of(a: list[T], condition_func: Callable[[T], bool]):
if len(a) == 0:
return True
return condition_func(a[0]) and all_of(a[1:], condition_func)
これをそのまま実行すると、空配列に対しては true を返します。 逆に、空配列に対して false を返すには別のロジックを追加する必要があると思います。
3: 使用例による説明
all_of 関数を用いてなにか処理を書いてみることを考えてみましょう。
ここでは例えば、長さ n（1 以上）の配列に対し、k 番目（k は 0 以上 n 未満の整数）の要素を除いた全ての要素が条件を満たすかどうかを判定する関数を実装することを考えてみます。
判定したい条件は、index が k 未満のものからなる配列と、index が k より大きいものからなる配列について all_of の条件が両方成り立つことと言い換えられ、これを実装してみると以下のようになります2。
def all_of_without_k(a: list[T], k: int, condition_func: Callable[[T], bool]):
assert 0 <= k < len(a)
return all_of(a[:k], condition_func) and all_of(a[k + 1:], condition_func)
これは上で実装した all_of を用いると実際に正しいです。
では、もし all_of が空配列に対して false を返している場合はどうでしょうか。この場合もほぼ正しく動きますが、k=0,n-1 のときに挙動がおかしくなってしまいます。
具体的には、見ている 2 つの配列が空配列になり、それに対する all_of が false を返すので、もう 1 つの配列の中身によらず all_of_without_k は false を返してしまうことになります。
そのため、正しく実装するためには all_of_without_k 内で空配列をコーナーケースとして扱わなければならなくなります。
4: モノイドの単位元による説明
2,3 の代数学的な背景には、モノイドの単位元が関わってきます。 モノイドとは特定の条件を満たす二項演算のことで、例えば以下のようなものが当てはまります。
- boolean に対する
and - int に対する
+(和) - float に対する
*(積)
単位元とは、その二項演算において何も影響を与えない元のことで、上の例には true, 0, 1 が対応します。
今回の論点は、二項演算の fold に空集合を与えた場合に何を返すべきかと捉えることができますが、単位元を返すことで、空集合をコーナーケースと扱う必要がなくなり見通しがよくなることが多いです。3
議論が分かれるものとして、
- minなど単位元に議論が分かれる（inf, 型の取りうる最大値, 十分大きい数など）二項演算
- 動的型付け言語において、複数の型をサポートしている二項演算の単位元が定まらない
などのケースがありますが、今回はtrueという自明な単位元が存在するのでそれを返すのが最も自然です。 もちろん、プログラミングにおいては状況によって例外はあると思いますが、上記の内容はプラクティスの1つとして踏まえた上で判断すると良いと思います。