読者です 読者をやめる 読者になる 読者になる

bitterharvest’s diary

A Bitter Harvestは小説の題名。作者は豪州のPeter Yeldham。苦闘の末に勝ちえた偏見からの解放は命との引換になったという悲しい物語

Haskellで学ぶ圏論・ウォームアップ編 小学生に戻って足し算

1.足し算

小学校に入って最初に学ぶのが足し算である。小学校低学年での足し算は、自然数(0で始まる正の整数)に自然数を加えることである。従って、圏論で考えると、対象は自然数\( \mathbb {N}\)、射は自然数を加える( \(+i \in \mathbb {N}\) )ということになりそうである。そこで、これを図で示すと以下のようになる。
f:id:bitterharvest:20150128091609p:plain

上記の図で、射の合成は次のように定めた。\( (+j) \circ (+i) (x) = (+i) ( (+i) (x)) \)、ここで、\(x \in \mathbb {N}\)である。

2.Haskellでの実装

最初に自然数を用意する必要があるが、ここでは、newtypeを用いて自然数を用意する(もちろん、dataを用いても実現できるが、この場合は既存の型、ここではInteger、を利用した方が便利であるし、処理時間なども早くなるので、newtypeを利用した)。次のようになる。

newtype Natural = MakeNatural Integer deriving (Eq, Ord, Show, Read)

また、自然数がNumのインスタンスとなり、加算が行えるように次のようにした。

toNatural :: Integer -> Natural
toNatural x
  | x >= 0 = MakeNatural x
  | otherwise = error "No natural number."

fromNatural :: Natural -> Integer
fromNatural (MakeNatural i) = i

instance Num Natural where
  x + y       = toNatural (fromNatural x + fromNatural y)

これを用いて足し算を行ってみる。

*Arithmetic> (+ (MakeNatural 3)) (MakeNatural 15)
MakeNatural 18
*Arithmetic> (+ (MakeNatural 5)) (MakeNatural 18)
MakeNatural 23
*Arithmetic> ((+ (MakeNatural 5)) . (+ (MakeNatural 3))) (MakeNatural 15)
MakeNatural 23

少し見にくいのだが、一番最初の例は、対象である自然数\( \mathbb {N}\)の一つの要素(MakeNatural 15)に射の一つである(+ (MakeNatural 3))を施したものである。二番目の例も同様である。最後の例は合成関数で、二つの射(+ (MakeNatural 3))と(+ (MakeNatural 5))を連続して施したものである。答えは正しく得られている。

3.掛け算

足し算が終わると、引き算を学び、その次に学ぶのが掛け算である。ほとんどの人が九九を覚えるのに多くの時間を費やしたことと思うが、この時、「学ぶということは辛抱することだ」という経験を積んだのではないかと思う。掛け算も足し算と同じように対象と射を考えることができる。対象は足し算と同じで、射は足し算の記号が掛け算の記号に変わっただけである。また、射の合成も同じように考えることができる。足し算の場合と同じように、図で示すと次のようになる。
f:id:bitterharvest:20150128104129p:plain
HaskellでのプログラムはNumのインスタンスの定義のところで掛け算を定義してあげればよい。そこで、プログラムの全体を示すと以下のようになる。

module Arithmetic where

newtype Natural = MakeNatural Integer deriving (Eq, Ord, Show, Read)

toNatural :: Integer -> Natural
toNatural x
  | x >= 0 = MakeNatural x
  | otherwise = error "No natural number."

fromNatural :: Natural -> Integer
fromNatural (MakeNatural i) = i

instance Num Natural where
  fromInteger = toNatural
  x + y       = toNatural (fromNatural x + fromNatural y)
  x * y       = toNatural (fromNatural x * fromNatural y)
  abs x       = undefined
  signum      = undefined
  x - y       = undefined

上記のプログラムで、Naturalが型クラスNumのインスタンスとして定義するとき、Numが有する関数を定義する必要があるが、必要のないものはundfinedとした。これを用いてプログラムを実行すると次のような結果が得られる。

*Arithmetic> (* (MakeNatural 3)) (MakeNatural 15)
MakeNatural 45
*Arithmetic> (* (MakeNatural 5)) (MakeNatural 45)
MakeNatural 225
*Arithmetic> ((* (MakeNatural 5)) . (* (MakeNatural 3))) (MakeNatural 15)
MakeNatural 225

4.足し算と掛け算は構造が一緒

足し算の図と掛け算の図をよく見ると、構造がよく似ているように見える。もっとよく見ると同じであるように見える。例えば、下図のような対応関係を与えることができる。
f:id:bitterharvest:20150128110309p:plain

上の図は、対象については要素ごとに、射については射ごとに対応をとったものである。この図から、\(+\)を\(\times\)に変えるだけで、足し算の図が掛け算の図に変わることが分かる。また、逆も真である。

足し算から掛け算への対応関係を\(F\)で表すこととする。この時、任意の\(i,j \in \mathbb {N} \)に対して
\begin{eqnarray*}
F( (+j) \circ (+i) ) & = & ( \times j) \circ ( \times i) \\
& = & F( (+ j) ) \circ F( (+ i) )
\end{eqnarray*}
が成り立つことが分かる。

圏論では、二つの圏が同じ構造を持っている場合、関手で対応づけすることができる。関手であるための主要な条件は、任意の射\(f: X \rightarrow Y \) および\(g: Y \rightarrow Z \)に対して\( F( g \circ f ) = F(g) \circ F(f ) \)が成り立つことである。関手であるためのもう一つの条件は、恒等関数は恒等関数に写像されるというものである。

足し算と掛け算の図をそれぞれ圏とみなせば、対応関係\(F\)は、関手であるための二番目の条件も満たすので、足し算と掛け算の圏を対応づける\(F\)は、関手となり、二つの圏は同じ構造であることが分かる。