型「の」計算にレッツチャレンジ
はいどーも、ちゅーんさんです。 最近「楽園追放」見てきたのですが、楽しかったです。(小学生並のry
いやあの、普通に良作でしたので、興味のある方なんかは、是非劇場で見に行くと良いと思います。 ハデだし。
いえい
はい、で、この記事はあれです。
Haskell Advent Calendar 2014 - Qiita
の、7日目の記事です。
皆さん!型は好きですかーっ!?
お れ は 好きだぜーっ!!!
とゆーわけで、今日は代数的データ型とゆー概念そのものに関する、ちょっといっぱい数学っぽい話をしようと思います。 この「っぽい」っての大事、超大事。
型の足し算
ここにUnit
型がありますでしょ。
data () = () deriving Eq
突然ですが、Unit
型は1です。
あ、それからここにBool
型があります。
data Bool = True | False deriving Eq
これまた突然ですが、Bool
型は2です。
ちょっと思い立ったので、ここにBoolUnit
型を作ってみました。
data BoolUnit = Bub Bool | Buu () deriving (Show, Eq)
Bool
は2で()
は1なので、1+2は3ですね。そう、つまりBoolUnit
は3なんです。
ちょっと何言ってるのか(ry
さて、母さんが夜なべをして手袋を編んでくれたので、手袋型を定義します。
data Tebukuro = T1 | T2 | T3 deriving (Show, Eq)
いきなりなんでビックリしないでくださいね?
はっきり言わせてもらうとTebukuro
は3です。
あれ?BoolUnit
もTebukuro
も3でしたね、つまりこういう事でしょうか?
いえいえ、でもやっぱりBoolUnit
はBoolUnit
だし、Tebukuro
はTebukuro
なので、
イコールで繋ぐのは気が引けますね。
おっと、ここで天からという記号を使って、両方共同じく3である事を表すと良いとのお言葉を頂きました。
もっというと、BoolUnit
はBool
の2とUnit
の1を足し算して3なので、次のように書いても良いですね。
いやでもちょっとマテ茶、そもそもこの1とか2とか3.14についてちゃんと説明が無いじゃないですか(#゚Д゚)ゴルァ!!
いや、なんとなくわかりますよ、データコンストラクタの合計数と同じっぽい事くらい。 でもやっぱり違う型って事は別物なわけですよ。 大体このグラディウスのビッグコアのレーザーにミミズがくっついたみないな記号は何なんですかっ!? ちゃんと説明してくださいっ!
同型とは何ぞや
例えば、次のような Tebukuro -> Int みたいな関数を作ったとしますよね?
f :: Tebukuro -> Int f T1 = 1 f T2 = 2 f T3 = 3
これはTebukuro
からInt
への関数であって、BoolUnit
からInt
への関数では無いです。
あ、いやでも兄さん、ちょっと落ち着いて考えてみて下さい、次のような関数作ったとするじゃないっすか。
bu2te :: BoolUnit -> Tebukuro bu2te (BUB True) = T1 bu2te (BUB False) = T2 bu2te (BUU ()) = T3
そしたら関数合成で BoolUnit -> Int
っていう関数作れますでしょ?
ghci> :t f . bu2te f . bu2te :: BoolUnit -> Int
こういう時に理屈っぽ人は、関数合成で作れる関数は、その関数があるのと同じ事にしちゃうんだそうです。
つまりbu2te
とf
があれば、BoolUnit -> Int
なる関数が初めからあるのと大差ねぇじゃんっていう話です。
逆いきましょう、逆。ここにBoolUnit -> Bool
なる関数g
があるじゃろ?
g :: BoolUnit -> Char g (BUB True) = 'a' g (BUB False) = 'b' g (BUU ()) = 'c'
これをこうして・・・
te2bu :: Tebukuro -> BoolUnit te2bu T1 = BUB True te2bu T2 = BUB False te2bu T3 = BUU ()
こうじゃ!
ghci> :t g . te2bu g . te2bu :: Tebukuro -> Char
えー、bu2te
, te2bu
ふたつの関数によって、BoolUnit
とTebukuro
型は互いに互いの代用を務める事ができるようになりました。
あくまで性質の話ですけど。
で、本当にBoolUnit
とTebukuro
が同じものとして扱えますよーっていう事を示す、一般的な方法があります。
te2bu
とbu2te
について、次のような性質を満たす事が確認出来れば良いのです。
te2bu . bu2te = id かつ bu2te . te2bu = id
もうちょっと厳密に言えば、このような等式を満たすような互いに変換しあう関数が実装可能ならば、 互いに互いの代用を務める事ができるわけですから、乱暴に「同じ型」として見ても良い事になります。
このような時、その二つの型は同型であるといい、AとBが同型である事をのように書きます。
理屈っぽい人達にとって「実装することが出来る」と「実装されてる」の差は大した問題ではありません。
BoolUnit
とTebukuro
は上記二つの関数を実装する事が可能です、
従ってこの二つのデータ型は同型である、という事がいえるわけです。
もうちょっとちゃんと確かめる
このくらい簡単な例なら、なんとなく目で見て、あー、確かに同型っぽい、うん、同型だよ同型。 みたいな感じに言える気がしますが、いやでももっと複雑な例になると確かめるのが大変になりそうな気がしますし、 ここはエンジニアらしく簡単に確かめられる仕組みを作っておきましょう。
といっても、データ型の定義からいきなり同型である事を厳密に示すのには、 CoqやAgdaのような証明系と呼ばれるなんかおっかないもんを使わなくてはいけないので、 あくまで変換する関数は人力で実装した上で、だいたいまぁ、同じっしょ? というような事が言える仕組みが欲しいぜ隊長!
というわけで、みんな大好きTest.QuickCheckの出番です。
instance Arbitrary BoolUnit where arbitrary = elements [BUB True, BUB False, BUU ()] instance Arbitrary Tebukuro where arbitrary = elements [T1, T2, T3] propIso :: (Arbitrary a, Arbitrary b, Eq a, Eq b) => (a -> b) -> (b -> a) -> (a, b) -> Bool propIso f g (x, y) = (g . f) x == x && (f . g) y == y main :: IO () main = do quickCheck $ propIso bu2te te2bu
これを普通に動作させて、テストが成功する事をチェック・・・
+++ OK, passed 100 tests.
んで、あえて失敗するケースを作って試してみましょう。bu2te
関数を次のように書き換えます。
bu2te :: BoolUnit -> Tebukuro bu2te (BUB True) = T1 bu2te (BUB False) = T1 --ここが違う bu2te (BUU ()) = T3
んで、実行っと・・・
*** Failed! Falsifiable (after 2 tests): (BUB False,T3)
おk、大丈夫そうですね。 こうしておけば、Eqインスタンスになっているデータ構造の同型性なら簡単に確認する事ができます。
色々準備
いつまでもBoolUnit
とかTebukuro
とかわけのわからん型を使ってると大変なので、
とりあえずまず、1〜6くらいまでのデータ型を定義して、この足し算の性質について探って行くことにしましょう。
まずデータ定義しますでしょ?QuickCheckしたいのでArbitrary型クラスのインスタンスにしますでしょ?
data T1 = T1C1 deriving (Show, Eq) data T2 = T2C1 | T2C2 deriving (Show, Eq) data T3 = T3C1 | T3C2 | T3C3 deriving (Show, Eq) data T4 = T4C1 | T4C2 | T4C3 | T4C4 deriving (Show, Eq) data T5 = T5C1 | T5C2 | T5C3 | T5C4 | T5C5 deriving (Show, Eq) data T6 = T6C1 | T6C2 | T6C3 | T6C4 | T6C5 | T6C6 deriving (Show, Eq) --quickCheck用 instance Arbitrary T1 where arbitrary = elements [T1C1] instance Arbitrary T2 where arbitrary = elements [T2C1, T2C2] instance Arbitrary T3 where arbitrary = elements [T3C1 .. T3C3] instance Arbitrary T4 where arbitrary = elements [T4C1 .. T4C4] instance Arbitrary T5 where arbitrary = elements [T5C1 .. T5C5] instance Arbitrary T6 where arbitrary = elements [T6C1 .. T6C6]
うわきもい
で、予行練習がてら、bool型とT2、T1とUnitが同型である事をチェックしてみましょう。
main :: IO () main = do quickCheck $ propIso t1_unit unit_t1 quickCheck $ propIso t2_bool bool_t2 ---- -- T1 =~ Unit t1_unit :: T1 -> () t1_unit T1C1 = () unit_t1 :: () -> T1 unit_t1 () = T1C1 ---- -- T2 =~ Bool t2_bool :: T2 -> Bool t2_bool T2C1 = True t2_bool T2C2 = False bool_t2 :: Bool -> T2 bool_t2 True = T2C1 bool_t2 False = T2C2
実行結果、OKです。
+++ OK, passed 100 tests. +++ OK, passed 100 tests.
あ、ここからはテストコードのみ載せるので、実行結果は読者が直接手で確認してみてください。 基本的には通るはずです。
型の足し算++
さて、足し算の話をもうちょっとしましょう。 足し算・・・つまり直和型は、新しく型を定義しても良いですが、Either型を使うほうが簡単に作れます。
それを利用して
を確認してみましょう。
main :: IO () main = do quickCheck $ propIso t2p3_t5 t5_t2p3 ---- -- T2 + T3 =~ T5 t2p3_t5 :: Either T2 T3 -> T5 t2p3_t5 (Left T2C1) = T5C1 t2p3_t5 (Left T2C2) = T5C2 t2p3_t5 (Right T3C1) = T5C3 t2p3_t5 (Right T3C2) = T5C4 t2p3_t5 (Right T3C3) = T5C5 t5_t2p3 :: T5 -> Either T2 T3 t5_t2p3 T5C1 = (Left T2C1) t5_t2p3 T5C2 = (Left T2C2) t5_t2p3 T5C3 = (Right T3C1) t5_t2p3 T5C4 = (Right T3C2) t5_t2p3 T5C5 = (Right T3C3)
さて、直和型は整数の加算のように結合則および交換則を満たす事がわかっています。 つまり、どんな型についても
が成り立つという事ですね。
なんか直感的に正しそうです。 っていうかこのへんの定義の話、もうちょっと定理証明に詳しければわざわざテストコード書くまでも無いきがするのですが 色々と復習してる時間無かったり、ましてやわかりやすくブログで説明できる自信もないので、頑張ってテストする事にします。
具体的な型をベタ書きするのはかなりしんどいので、次のような多相な関数を作りましょう。
associative_from :: Either (Either a b) c -> Either a (Either b c) associative_from (Left (Left x)) = Left x associative_from (Left (Right x)) = Right (Left x) associative_from (Right x) = Right (Right x) associative_to :: Either a (Either b c) -> Either (Either a b) c associative_to (Left x) = (Left (Left x)) associative_to (Right (Left x)) = (Left (Right x)) associative_to (Right (Right x)) = (Right x)
そのまま使おうとすると最終的に記述量がえらい長くなってしまうので、短く書くための型の別名と関数を定義します。
type Associative a b c = (Either (Either a b) c, Either a (Either b c)) -> Bool propAssociative :: (Arbitrary a, Arbitrary b, Arbitrary c, Eq a, Eq b, Eq c, Show a, Show b, Show c) => Associative a b c propAssociative = propIso associative_from associative_to
あとはpropAssociative
に型シグネチャを付けて、quickCheck
関数に渡せばおk・・・
なのですが、T1〜T6全て組み合わせを試すとやたら組み合わせ多くてつらぽよ度高いので、 適当に何パターンか繕って実行してみます。
main :: IO () main = do quickCheck $ (propAssociative :: Associative T1 T1 T1) quickCheck $ (propAssociative :: Associative T3 T3 T3) quickCheck $ (propAssociative :: Associative T6 T6 T6) quickCheck $ (propAssociative :: Associative T1 T2 T3) quickCheck $ (propAssociative :: Associative T2 T3 T4) quickCheck $ (propAssociative :: Associative T3 T4 T5) quickCheck $ (propAssociative :: Associative T4 T5 T6)
これを実行してみてください、何百回やっても、Associative
の型引数をどう変えても必ずテストが通るはずです。
本当は全パターン試せる上手いやり方無いかな〜とか思ったんですが、ちょっとすぐには思いつかなかったのでこれで勘弁してください。
続いて、交換則の話にうつりましょう、 こっちはもっと簡単なので一気にいきます。
main :: IO () main = do quickCheck $ (propCommutative :: Commutative T1 T1) quickCheck $ (propCommutative :: Commutative T2 T2) quickCheck $ (propCommutative :: Commutative T3 T3) quickCheck $ (propCommutative :: Commutative T3 T4) quickCheck $ (propCommutative :: Commutative T4 T5) quickCheck $ (propCommutative :: Commutative T5 T6) ---- -- a + b =~ b + a commutative :: Either a b -> Either b a commutative (Left x) = Right x commutative (Right x) = Left x type Commutative a b = (Either a b, Either b a) -> Bool propCommutative :: (Arbitrary a, Arbitrary b, Eq a, Eq b, Show a, Show b) => Commutative a b propCommutative = propIso commutative commutative
足し算と来たら次は引き算・・・と行きたいところですが、 代数的データ型には引き算とか割り算に相当する概念は存在しないので、すっとばして掛け算いきましょう。
型の掛け算
型の足し算が直和型だったので、もうわかると思いますが、 型の掛け算は直積型です。
例えば、T2
とT3
の直積は次のように定義できます。
data T2T3 = T2T3 T2 T3 deriving (Show, Eq) --quickCheck用 instance Arbitrary T2T3 where arbitrary = do t2 <- arbitrary t3 <- arbitrary elements [T2T3 t2 t3]
直和の時にEitherを使ったのと同じように、直積はタプルを使えば簡単に作る事ができます。
今作ったT2T3
と(T2,T3)
が同型な事をちゃちゃっと確認してしまいましょう。
main :: IO () main = do quickCheck $ propIso t2T3_Tuple tuple_T2T3 ---- -- T2T3 =~ (T2, T3) t2T3_Tuple :: T2T3 -> (T2, T3) t2T3_Tuple (T2T3 t2 t3) = (t2, t3) tuple_T2T3 :: (T2, T3) -> T2T3 tuple_T2T3 (t2, t3) = T2T3 t2 t3
さて、直積型は次のような規則をもっている事がわかっています。
一つ目の規則は単位元則、そして残りは直和の場合と同じく、結合則と交換則といいます。 単位元は、右単位元と左単位元とありますが、交換則があれば片方を示す事でどちらも成り立たせる事ができるので、片方だけテストします。
さあさ、テストコード、だだーっといきますよ。
main :: IO () main = do quickCheck $ (propIdentityElem :: IdentityElem T1) quickCheck $ (propIdentityElem :: IdentityElem T2) quickCheck $ (propIdentityElem :: IdentityElem T3) quickCheck $ (propIdentityElem :: IdentityElem T4) quickCheck $ (propIdentityElem :: IdentityElem T5) quickCheck $ (propIdentityElem :: IdentityElem T6) quickCheck $ (propAssociative' :: Associative' T1 T1 T1) quickCheck $ (propAssociative' :: Associative' T3 T3 T3) quickCheck $ (propAssociative' :: Associative' T6 T6 T6) quickCheck $ (propAssociative' :: Associative' T1 T2 T3) quickCheck $ (propAssociative' :: Associative' T2 T3 T4) quickCheck $ (propAssociative' :: Associative' T3 T4 T5) quickCheck $ (propAssociative' :: Associative' T4 T5 T6) quickCheck $ (propCommutative' :: Commutative' T1 T1) quickCheck $ (propCommutative' :: Commutative' T2 T2) quickCheck $ (propCommutative' :: Commutative' T3 T3) quickCheck $ (propCommutative' :: Commutative' T3 T4) quickCheck $ (propCommutative' :: Commutative' T4 T5) quickCheck $ (propCommutative' :: Commutative' T5 T6) -- 1 * a =~ a idelem_from :: ((), a) -> a idelem_from ((), x) = x idelem_to :: a -> ((), a) idelem_to x = ((), x) type IdentityElem a = (((), a), a) -> Bool propIdentityElem :: (Arbitrary a, Eq a, Show a) => IdentityElem a propIdentityElem = propIso idelem_from idelem_to ---- -- (a * b) * c =~ a * (b * c) associative_from' :: ((a, b), c) -> (a, (b, c)) associative_from' ((x, y), z) = (x, (y, z)) associative_to' :: (a, (b, c)) -> ((a, b), c) associative_to' (x, (y, z)) = ((x, y), z) type Associative' a b c = (((a, b), c), (a, (b, c))) -> Bool propAssociative' :: (Arbitrary a, Arbitrary b, Arbitrary c, Eq a, Eq b, Eq c, Show a, Show b, Show c) => Associative' a b c propAssociative' = propIso associative_from' associative_to' ---- -- a * b =~ b * a commutative' :: (a, b) -> (b, a) commutative' (x, y) = (y, x) type Commutative' a b = ((a, b), (b, a)) -> Bool propCommutative' :: (Arbitrary a, Arbitrary b, Eq a, Eq b, Show a, Show b) => Commutative' a b propCommutative' = propIso commutative' commutative'
んで、もういっこ、直積・直和にまつわる分配法則という重要な法則があります。
そうです、中学校の数学でやったあれです。 この法則が数の足し算掛け算だけでなく、型に関しても成り立つ事を確認しましょうできました。
main :: IO () main = do quickCheck $ (propDistributive :: Distributive T1 T1 T1) quickCheck $ (propDistributive :: Distributive T3 T3 T3) quickCheck $ (propDistributive :: Distributive T6 T6 T6) quickCheck $ (propDistributive :: Distributive T1 T2 T3) quickCheck $ (propDistributive :: Distributive T2 T3 T4) quickCheck $ (propDistributive :: Distributive T3 T4 T5) quickCheck $ (propDistributive :: Distributive T4 T5 T6) ---- -- a * (b + c) =~ a * b + a * c distributive_from :: (a, Either b c) -> Either (a, b) (a, c) distributive_from (x, Left y) = Left (x, y) distributive_from (x, Right y) = Right (x, y) distributive_to :: Either (a, b) (a, c) -> (a, Either b c) distributive_to (Left (x, y)) = (x, Left y) distributive_to (Right (x, y)) = (x, Right y) type Distributive a b c = ((a, Either b c), Either (a, b) (a, c)) -> Bool propDistributive :: (Arbitrary a, Arbitrary b, Arbitrary c, Eq a, Eq b, Eq c, Show a, Show b, Show c) => Distributive a b c propDistributive = propIso distributive_from distributive_to
関数はどーすんの
さて、Haskellの関数を表す(->)は型引数を二つとるコンストラクタでもありましたね。
*Main> :k (->) (->) :: * -> * -> *
Haskellは強い型システムを持っていますから、こんなふーに関数自体も他の型とおんなじよーな感じで扱う事ができますし、 今日やってるような「型の計算」で、関数を扱えないという事はまさか無いでしょう。 実の所、「型の計算」においては、関数を扱えるようになってからが本番なのですっ!
おっとここでまた天の声が聞こえてきましたよ?型の計算において関数は「べき乗」のように扱うんだそうです。
例えば、A -> B
という関数はBAのように記述します。
当然、この「型のべき乗」にも、直和型や直積型と同じようにいくつかの法則があります。
すっげー身近な所だと、curry
とuncurry
は、次のような同型関係を表してるんです。
(a × b) b a
所で、このcurry
とuncurry
の関係は、高校数学で習う指数法則のうちの一つとそっくりですね?
そんな感じで、他の指数法則も適用できます。
a b
(a + b)
a a
a
それぞれ、こんな感じに実装できますね。
---- -- C^A*C^B =~ C^(A+B) exponent1_from :: (a -> c, b -> c) -> (Either a b -> c) exponent1_from (f, g) (Left x) = f x exponent1_from (f, g) (Right x) = g x exponent1_to :: (Either a b -> c) -> (a -> c, b -> c) exponent1_to f = (f . Left, f . Right) ---- -- (B*C)^A =~ B^A*C^A exponent2_from :: (a -> (b, c)) -> (a -> b, a -> c) exponent2_from f = (fst . f, snd . f) exponent2_to :: (a -> b, a -> c) -> (a -> (b, c)) exponent2_to (f, g) = \x -> (f x, g x)
あー、指数法則のQuickCheckでのテストはめちゃんこややこしいので無しで良いですか?
ところで、そもそもの話なんですけど、ちゅーんさんがこの辺のお勉強をしてた時、 ちゃんと数値計算のべき乗と同じように
n
が成り立つかって情報を得ることができなかったので、あんまり自信なかったのです。 ので、2パターンほど試してみました。
main :: IO () main = do mapM_ quickCheck propExponential mapM_ quickCheck propExponential' ---- -- T2 * T2 =~ T2^T2 exponential_from :: (T2, T2) -> T2 -> T2 exponential_from (T2C2, T2C1) = ft2 exponential_from (T2C1, T2C2) = id exponential_from (T2C1, T2C1) = \_ -> T2C1 exponential_from (T2C2, T2C2) = \_ -> T2C2 ft2 :: T2 -> T2 ft2 T2C1 = T2C2 ft2 T2C2 = T2C1 exponential_to :: (T2 -> T2) -> (T2, T2) exponential_to f = (f T2C1,f T2C2) propExponential :: [((T2, T2), T2) -> Bool] propExponential = [ \(xy, _) -> (exponential_to . exponential_from $ xy) == xy , \(xy ,z) -> let f = exponential_from xy in (exponential_from . exponential_to $ f) z == f z ] ---- -- T2 * T2 * T2 =~ T2^T3 exponential_from' :: (T2, T2, T2) -> T3 -> T2 exponential_from' (T2C2, T2C1, T2C1) = \x -> if x == T3C1 then T2C2 else T2C1 exponential_from' (T2C1, T2C2, T2C1) = \x -> if x == T3C2 then T2C2 else T2C1 exponential_from' (T2C1, T2C1, T2C2) = \x -> if x == T3C3 then T2C2 else T2C1 exponential_from' (T2C1, T2C2, T2C2) = \x -> if x == T3C1 then T2C1 else T2C2 exponential_from' (T2C2, T2C1, T2C2) = \x -> if x == T3C2 then T2C1 else T2C2 exponential_from' (T2C2, T2C2, T2C1) = \x -> if x == T3C3 then T2C1 else T2C2 exponential_from' (T2C1, T2C1, T2C1) = \_ -> T2C1 exponential_from' (T2C2, T2C2, T2C2) = \_ -> T2C2 exponential_to' :: (T3 -> T2) -> (T2, T2, T2) exponential_to' f = (f T3C1, f T3C2, f T3C3) propExponential' :: [((T2, T2, T2), T3) -> Bool] propExponential' = [ \(xyz, _) -> (exponential_to' . exponential_from' $ xyz) == xyz , \(xyz, w) -> let f = exponential_from' xyz in (exponential_from' . exponential_to' $ f) w == f w ]
色々書いてた感じ、だーいたいの法則性は分かりました、証明したわけでは無いですが、ちゃんと成り立つっぽい。
まとめ
とゆーわけで、「型の計算」と題して、型を式にして色々変換してみる手法を紹介してみました。はい。 あ、一点だけ意識していただきたいのですが。今回はわりと自明な内容なのもあり、色々手を抜く目的でQuickCheckiを使ったテストを行いましたが、本来はちゃんと数学的に証明するか、網羅的なテストを行うべきです。
さて、こーゆー型の性質を実際のプログラミングに応用するのは、一定の経験値が必要そうな気はしますが、 OOPにしても関数型にしても、データ構造の持つ性質に着目する事は、重要そうに見えますね?
まー、この記事はそれ以前に「どや、面白いやろ?」という話ですので、 そこんとこ、楽しんで頂ければハッピーです。
あとあれ、識者の方は色々つっこむ所あればつっこんでください。 ちゅーんさんもにょきにょき成長したいです。
では、この辺でノシノシ