てくのろじーたのしー

Haskellぺろぺろ

(.) . (.) の型

初めましての方が多いかもしれません。にわかプログラマのtechno_tanoCです。

前にふとghciで

:t (.) . (.)

と打ち込んでみたところ、

(.) . (.) :: (b -> c) -> (a -> a1 -> b) -> a -> a1 -> c

と表示されました。

にわかの私はこれだけでもう大混乱です。(b -> c)って何だ!(a -> a1 -> b)ってどこから来たんだ!

どういう超自然的法則によってこのような型になっているのか理解できなかった、というか今でもあまりよく分かっていませんが、自分の理解を深めるためにも頑張って説明してみます。

どこかしら間違えている可能性が高いのでマサカリやツッコミ、罵倒をして頂けると喜びます。


何はともあれとりあえず (.) の定義を確認してみます。

HackageのPreludeを見てみると、 (.) は

(.)    :: (b -> c) -> (a -> b) -> a -> c
(.) f g = \x -> f (g x)

のように定義されていました。

(b -> c)という型のfと、(a -> b) という型のgを受け取って、\x -> f (g x)しています。


まずは(.) . (.)の真ん中の . をこの定義から変形してみます。

(.) . (.)
-- ↓
\f -> (.) ((.) f)

(.)は第一引数としてb -> cという型の関数を要求していますので、xではなくfと書いてみました。
ということでfはj -> kという型です。(定義のa, b, cと紛らわしいのでj, kとします)


\f -> (.) ((.) f) の一つ目の(.)は前置記法になっているので、ラムダ式を使ってこれを中置記法にしてみます。

\f -> (.) ((.) f)
-- ↓
\f -> (\p -> ((.) f) . p)
-- ↓ 括弧を外す
\f -> \p -> ((.) f) . p
-- ↓ 二引数関数にしてもHaskellなら勝手にカリー化してくれるので同じはず
\f p -> ((.) f) . p

p が何者なのかはちょっと置いておいて、見た感じでは「fとpを取って、((.) f)とpを合成する関数」のように見えます。


f は j -> k という型なので、「(. :: (j -> k) -> (i -> j) -> i -> k) f」 は「 (.) に f を部分適用したもの」で、型は (i -> j) -> i -> k です。


(i -> j) -> i -> kと何か謎のpを合成するのですが、
定義では(.)は (b -> c) -> (a -> b) -> a -> cという型で、定義での(b -> c)の部分には \f p -> ((.) f) . pにおける (.) fの(i -> j) -> i -> kという型で決まってしまっています。

つまり

(以下自信無い)


bの部分が(i -> j)で、cが(i -> k)ということになる(はず)。

したがって(b -> c)の部分の型は(i -> j) -> (i -> k)です(多分)。


さて、ここでpはどのような型でなければならないでしょうか。

     b   ->    c

(i -> j) -> (i -> k)

のように対応しているので、

a ->  b

より、p は

m -> (i -> j)

である必要があります。


よって

\f p -> ((.) f) . p :: (j -> k) -> (m -> (i -> j)) -> m -> i -> k

です。

(m -> (i -> j))は括弧を外して (m -> i -> j)になり、

\f p -> ((.) f) . p :: (j -> k) -> (m -> i -> j) -> m -> i -> k

これは、最初の

(.) . (.) :: (b -> c) -> (a -> a1 -> b) -> a -> a1 -> c

と同じ形です。


説明終わり。


なんというか説明というより、「こうやったらなんか知らないけど同じ形になった」というだけな感じもしますが、今回は以上です。

(a -> a1 -> b)の部分は「関数合成の都合上、受け渡し先が関数を要求してるから関数を返す関数、つまり二引数関数だったから」ということなのかな?