ゼロ除算ができる数、輪を実装してみたので解説 #Haskell

プログラムを実行したら ゼロ除算 の例外が出てしまった経験ってありませんか¹？割り算をするときは当然0で割っちゃダメなんですが、そもそもそれってなんでなんでしょう？

たまたま @matsu_chara 氏とそんな話をしてたとき、 輪（Wheel） という"数"の存在を知りました。どうやらこの"数"には 0による割り算が定義されている らしいのです！

そもそも0で割り算ができないのはなぜでしょう？それは端的にいうと 定義されてないから です。定義されてないのにそれを使ってしまうと $1\times 0 = 2 \times 0 $ 両辺を0で割って $ 1 = 2 $ なんてことが起こってしまうので気をつける必要があります²。定義されてないなら無理やり定義しちゃえばいいじゃんと例えば $1 / 0 = 0$ なんて定義してしまうと、両辺に0を掛けたら $1 = 0$ になってしまって思ったより簡単には行きません。

そもそも 割り算の定義ってなんでしたっけ？ 算数的な話は余計な混乱を招くだけだと思うので、ここでは数学の知識を引っ張ってきましょう（事前にこちら記事とかを読んでおくと安心です Swiftで代数学入門〜 1. 数とは何か？）。私達が日常でよく使う整数とか実数には群・環・体といった代数的構造が備わっています。ある数$x$の掛け算における逆元を $x^{-1}$ と表し、 逆元$x^{-1}$を掛ける操作を「$x$で割る」と呼んでいたのでした 。つまりこれが割り算の定義です。0（加法の単位元）での割り算について考えると、体はそもそも定義に「0以外の元が逆元を持つ」（つまり0で割れない）と書いてありますし、環において0が掛け算の逆元を持つと

\begin{matrix}
a + 0 = a \\
a / 0 + 1 = a / 0 \\
\therefore 1 = 0
\end{matrix}

（※1行目は加法の単位元の定義。1行目から2行目は両辺に0の逆元を掛ける。2行目から3行目は両辺から$a/0$を引く）
となり自明な環になってしまいます

0で割り算ができてしまうと体にはならず環としても面白いものにはならないことがわかりましたが、それでは0で割り算できるような面白い代数的構造は存在するのでしょうか？そう！それが 輪(Wheel) と呼ばれるものなのです！

【定義】 組<H, 0, 1, +, ・, />が輪であるとは以下の条件を満たすことを言う。

1. <H, 0, +> は可換モノイドとなる
2. <H, 1, ・, /> は対合/を持つ可換モノイドとなる

# 分配法則
3. (x + y)z + 0z = xz + yz
4. x/y + z + 0y = (x + yz) / y

# 0に関する法則
5. 0・0 = 0
6. (x + 0y)z = xz + 0y
7. /(x + 0y) = /x + 0y
8. x + 0/0 = 0/0

ひゃー法則がいっぱい出てきましたね！こういうのは後から使っていくうちに慣れていけばいいので今は先に進みましょう。

$/$は対合(involution)と呼ばれる一項演算子で

//x = x
/(xy) = /y/x

という関係式を満たします。

輪においては割り算を 掛け算の逆元との積ではなく、対合との積と定義する ことで0でも割り算ができるようになっています。0に逆元が存在しなくても対合さえあれば割り算ができるので0で割り算ができるからといって全体が自明な構造になってしまうことはありません。一方で逆元が存在する元では、逆元と対合がほとんど一致するので³既存の割り算の拡張としても安心して受け入れられます。

輪を使えば0で割り算ができる以外にも

0で分岐が必要な計算アルゴリズムの実装をシンプルにできるかもしれない
代数幾何学において輪を値域に持つ有理写像を考えることで色々…（わからんorz）

という話があるらしいので詳しい話が気になる人は Wheels - On Division by Zero を読んでみてください（ここまでの輪の定義もこの文献から引用しています）。

輪を実装する

それでは実際に触って遊べる輪の具体例を作ってみましょう！${\mathbb Z}\times{\mathbb Z}$に

(x, y) \sim (x', y') \Leftrightarrow \exists s, s' \in {\mathbb Z}\setminus\{0\}\ \ {\rm s.t.}\ \ (sx, sy) = (s'x', s'y')

という同値関係を入れて割り、

\begin{matrix}
(x, y) + (x', y') &=& (xy'+x'y, yy') \\
(x, y) \cdot (x', y') &=& (xx', yy') \\
/(x, y) &=& (y, x)
\end{matrix}

というような足し算と掛け算と対合を入れると輪になります。$(a, 1)$を$a$と略記することにすれば、有理数に近いなにかだと思うことができるでしょう（例えば$(2,3) = (2, 1) \cdot /(3, 1) = 2/3$）。このように得られる輪は分数輪(wheel of fractions)と呼ばれていて、環の局所化みたいですが局所化と違ってペアのどちらも ${\mathbb Z}$ 全体を動くことができるので0を分母に持ってくることができるようになっているのがポイントです。分数輪を$\bigodot_{{\mathbb Z}\setminus{0}} {\mathbb Z}$と表記するのですが、この$\bigodot$が車輪に見えることから輪（Wheel）と呼ばれているそうです⁴。
これをHaskellで実装してみましょう！

data Wheel = W Integer Integer

instance Eq Wheel where
  (W 0 0) == (W 0 0) = True
  (W 0 0) == (W _ _) = False
  (W _ _) == (W 0 0) = True
  (W x y) == (W x' y') = x * y' == x' * y

整数のペアWheelを作り同値関係を入れました。輪は抽象的な代数的構造なのでこれ自体をWheelと名付けることに多少違和感はありますが、オリジナルの輪はこのように定義されていたものなので⁵ここでは目をつぶることにしましょう。$\bigodot_{{\mathbb Z}\setminus{0}} {\mathbb Z}$は有理数に近いなにかだと思えるという話をしましたが、実は集合として有理数に$/0, 0/0$という２つの元をを加えたものに等しくなっています。これを考慮してShowのインスタンスを作ってみましょう。

instance Show Wheel where
  show (W 0 0) = "0/0"
  show (W _ 0) = "/0"
  show (W a b)
    | a `mod` b == 0 = show $ a `div` b -- 分母が1になるなら整数として表示する
    | otherwise      = let d = gcd a b  -- そうでなければ約分して表示する
                        in show (a `div` d) ++ "/" ++ show (b `div` d)

ghciで試してみると

> W 1 1
1

> W 1 0
/0

> W 0 1
0

> W 0 0
0/0

> W 2 4
1/2

うまく動いてそうですね。次はWheel上の演算を定義してみましょう。

import Data.Ratio (denominator, numerator)

instance Num Wheel where
  (W x y) + (W x' y') = W (x * y' + x' * y) (y * y')
  (W x y) * (W x' y') = W (x * x') (y * y')
  negate (W x y)      = W (-x) y
  abs    (W x y)      = W (abs x) (abs y)
  signum (W x y)      = W (signum x * signum y) 1
  fromInteger n       = W n 1

instance Fractional Wheel where
  recip (W x y)  = W y x
  fromRational r = W (numerator r) (denominator r)

素直に定義することができましたね。以上でWheelが完成したので早速ghciで遊んでみましょう！

> 1 + 1 :: Wheel
2

> 1 / 0 :: Wheel
/0

> 1 + 0 / 0 :: Wheel
0/0

見事０で割り算することができました！

まとめ

輪を実装してゼロ除算が例外にならずに無事行えることを確認できました個人的には応用も気になるところで、今回作ったWheelでゼロ除算を回避する必要があるいくつかのアルゴリズムをシンプルにできるか考えてみたのですがまぁそう簡単には行かないようでした（結局$0/0$に吸い込まれてしまう…）。なにか面白いアルゴリズムを発見したら誰か教えてください！あとWheels - On Division by Zero 面白いので読んでみてください！対合モノイドの定義から輪の圏論的な性質や輪上の加群まで色々書いてあります。

Pythonにはなんの恨みもないので悪しからず…。 ↩
https://ja.uncyclopedia.info/wiki/1%3D2 ↩
実際次の等式が成り立ちます$x^{-1}+0/x=/x+0x^{-1}$（出典 Wheels - On Division by Zero） ↩
"the term inspired by the topological picture $\bigodot$ of the projective line together with an extra point 0/0"（出典 Wheels - On Division by Zero） ↩
Anton Setzer, "Wheels" http://www.cs.swan.ac.uk/~csetzer/articles/wheel.pdf ↩