TL;DR
やったこと:
佐野さん(@taketo1024)の「Swiftで代数学入門」を読み、これをPythonicにするとどうなるか気になったので書きました。さらにペアノの公理から全て再帰的に演算してるので100*100すらきついですが、速度等は気にせず定義から構成的に数学を作れている実感を大事にしました。有理数までです。
えられたこと:
Pythonicなクラスの書き方の知識が増えました。プログラムで数学を具現化すると定義の循環などに敏感になれました。無限の現れないものならできるんだなあと思いました。
ソースコード
自然数について解説
自然数とは{0, 1, 2, 3, ...}という集合です。0を含めない場合もあります。当たり前に存在するものですが、何が自然数か、数とは何かをしっかりちゃんとルールを決めることで、矛盾を抑えて数学することができます。そして、自然数を構成するルールといえば、ペアノの公理です。
そこで、ペアノの公理を参考に自分なりにpythonicに実装してみました。批判的に見てもらえたらと思います。
英語で書いているのは英語wikiのペアノの公理の対応するであろうものです。
class NaturalNumber:
def __init__(self, p=None):
self.predecessor = p
def __eq__(self, x):
if self.predecessor is None and x.predecessor is None:
return True
elif (self.predecessor is None and x.predecessor is not None) \
or (self.predecessor is not None and x.predecessor is None):
return False
else:
return self.predecessor == x.predecessor
pythonでは__eq__(self, x)を書くことで、self == x の結果を制御することができます。
公理 1 : def __init__(self, p=None):
0という前者のない元を作ることができる。
1. 0 is a natural number.
8. For every natural number n, S(n) = 0 is false. That is, there is no natural number whose successor is 0.
Pythonでは__init__がコンストラクタになります。この例ではNaturalNumber()とすると、pがNoneとして実行され、predecessorというインスタンス変数がNoneな、つまり持たないオブジェクトが生成されます。
公理 2 : self.predecessor = p
元を前者としてもつ元が存在する。
6. For every natural number n, S(n) is a natural number.
NaturalNumber(x)とすると、pがxとして実行され、predecessorというインスタンス変数としてxを持ったオブジェクトが作られます。NaturalNumber(NaturalNumber())が1な訳ですね。
公理 3 : if self.predecessor is None and x.predecessor is None:
1.の性質をもつ元同士は等しい。
ここについては、例えばすべての元をシングルトンで構成していれば、単にreturn self is x というように記述することもでき、そういった選択肢もありました。等しい、等しくないことにより自覚的にできそうかなと思い、今回は、等しいけれども同一でないオブジェクトを生成できるようにしています。等しいことと同一であることの違い、==とisの違いが感じられます。
公理 4 : elif (self.predecessor is None and x.predecessor is not None)
1.の性質をもつ元と1.の性質を持たない元は等しくない。
8. For every natural number n, S(n) = 0 is false. That is, there is no natural number whose successor is 0.
これがなければ単一の元になってしまいます。実際にこの行をプログラムしなければ、すべての元が等しくなりますね。
公理 5 : or (self.predecessor is not None and x.predecessor is None):
aとbが等しいことと、bとaが等しいことは同値である
3. For all natural numbers x and y, if x = y, then y = x. That is, equality is symmetric.
これも当たり前なようなんですが、これがなければ違うことの判定が不完全になってしまいます。数学的にこのことを説明できるようになるより前にプログラムのエラーがその不完全さを教えてくれました。
公理 6 : return self.predecessor == x.predecessor
前者同士が等しければ、後者同士は等しい
7. For all natural numbers m and n, m = n if and only if S(m) = S(n). That is, S is an injection.
英語wikiの公理と比べて余ったものを見て見ましょう。
2. For every natural number x, x = x. That is, equality is reflexive.
4. For all natural numbers x, y and z, if x = y and y = z, then x = z. That is, equality is transitive.
5. For all a and b, if b is a natural number and a = b, then a is also a natural number. That is, the natural numbers are closed under equality.
私の公理3も余っています。英語の2については、私の公理３と５から出てくる類のものかなという感じがします。
英語の5については確かにこれはあった方が良さそうです。つまり、pythonの実装で後から等しくなる元を作れるように別のクラスを用意することは可能だからです。具体的にはpredecessorというインスタンス変数をNone持たせるだけで0元でクラスの違うものを作ることができます。プログラミング用語でいうとタイプチェックせよという公理ですね。
英語の4についてなんですが、ここではなぜ必要かよくわかりませんでした。（わかる方コメントお待ちしてます。）
自然数の算術
とまあこんな感じでwikiを参考に演算を作っていきました。
def __add__(self, x):
if x == N_ZERO:
return self
else:
return NaturalNumber(self + x.predecessor)
def __mul__(self, x):
if x == N_ZERO:
return N_ZERO
else:
return self + self * x.predecessor
その後、整数と有理数を構成し、演算も作っています。テストも書いたので、簡単に試してもらえると思います。
試し方
git clone https://github.com/yhay81/pythonic-algebra.git
cd pythonic-algebra
python -m unittest tests/test_natural_number.py
python -m unittest tests/test_integer.py
python -m unittest tests/test_rational.py
python
>>>from numbers.natural_number import *
>>>one = NaturalNumber(NaturalNumber())
>>>two = one + one
>>>three = two + one
>>>four = two * two
>>>n256 = four ** four
>>>x = n256 % three
>>>x == one
>>>for n in four:
>>> print(n)
などなど、pythonでできそうなことはだいたい詰め込みました！もっと知りたい方はぜひコードを見てください。気に入ってもらえたらスターお願いします。