ランク2多相の、ふたつの側面

はじめに

この記事はhaskell-jpというslack上での、やりとりのなかで、気づいたことをまとめたものです。ランク2多相には、「できることを、ふやす」という側面と「できることを、明示的に制限する」という側面とがあるということに、気づかせてもらいました。とりあえず、いそいで書いたので、読みぐるしい点や、誤りなどあると思います。

ランク2多相の、かんたんな説明

ランク2多相について、かんたんに説明します。以下の記事も参考にしてください。

Higher Rank Type とは

ふたつの木の要素の数、または高さを足し合わせる

ランク2多相が必要で、なおかつ、かんたんで意味のある例というのは、なかなか思いつきません。すこし作為的ですが、ふたつの木の要素の数を足しあわせる関数と、ふたつの木の高さを足しあわせる関数とを、一般化した関数の例を、みてみましょう。

まず、木の要素数を求める関数も、高さを求める関数も、つぎのような型になります。

length :: Tree a -> Int
height :: Tree a -> Int

これらの関数を、第1引数としてとる関数であれば、2種類の操作を一般化したものとなります。また、ふたつの木の、それぞれの要素の型は異なっていても良いものとします。すると、求める関数の型は、つぎのようになります。

foo :: (Tree a -> Int) -> Tree b -> Tree c -> Int

しかし、このような型付けで、求める関数を定義することはできません。このように型付けされた関数fooは、つぎのような型の関数をまとめて定義したのとおなじことです。

foo1 :: (Tree Double -> Int) -> Tree Char -> Tree Bool -> Int
foo2 :: (Tree String -> Int) -> Tree [Int] -> Tree (Maybe Char) -> Int
foo3 :: (Tree (Int, Char) -> Int) -> Tree () -> Tree Double -> Int
foo4 :: (Tree () -> Int) -> Tree Double -> Tree () -> Int
.
.
.

つまり、それぞれの最終的に適用される段階でのかたちには、多相性はなく、型変数にはいる型はひとつに定まっている必要があります。最終的に適用される段階でのかたちに、多相的な関数を含ませるためには、2階の多相性、つまりランク2多相が必要になります。正しくは、つぎのようになります。

bar :: (forall a . Tree a -> Int) -> Tree b -> Tree c -> Int

このように、予約語forallを使うことによって、第1引数について「どのような型の値を要素として持つ木でも、引数としてとれる関数」として、適切に型づけすることができます。

ランク2多相を使うと、関数の多相性を保ったまま、引数として、とることができます。実際に試すことのできる、関数の定義を載せておきます。

bar :: (forall a . Tree a -> Int) -> Tree b -> Tree c -> Int
bar f t1 t2 = f t1 + f t2

height :: Tree a -> Int
height (Node _ []) = 1
height (Node _ ts) = 1 + maximum (map height ts)

このファイルを読み込んで、つぎのように試してみます。

> bar length (Node 1 [Node 2 []]) (Node 'a' [Node 'b' [], Node 'c' []])
5
> bar height (Node 1 [Node 2 []]) (Node 'a' [Node 'b' [], Node 'c' []])
4

できることが、ふえる

上記の例で、ランク2多相を使うことで、できることが、ふえているのがわかります。ひとつの多相関数を使って、複数の、それぞれ型のちがう、値を処理することは、ランク2多相を使わなければできません。

できることが、制限される

forallを明示して、ランク2多相としたことで、できなくなることもあります。上記の例では、第1引数の関数fには、「多相関数でなければならない」という制限がつきます。つぎの、ふたつの型付けをくらべてみてください。

hoge :: (Tree a -> Int) -> Tree a -> Int
piyo :: (forall a . Tree a -> Int) -> Tree b -> Int

関数piyoの第1引数には、前述の関数lengthやheightのような、多相関数しかとることができません。しかし、関数hogeでは、たとえば、Tree Integer -> Intのような関数を、第1引数にすることができます。その結果、つぎのようなことも可能になります。

> hoge sum (Node 1 [Node 2 []])
3

しかし、つぎのようなことは、できません。

> piyo sum (Node 1 [Node 2 []])
(型エラーとなる)

できることを制限するという使いかた

ランク2多相には、「できることを制限する」という使いかたもあります。

mmorphパッケージのMFunctorでは、クラス関数のhoistの型は、つぎのように定義されています。

hoist :: (forall a . m a -> n a) -> t m a -> t n a

このようにすることで、第1引数である関数が、型aについて多相的であることを、明示的に要求しています。これは、型aに具体的な型をとることで可能となる演算を禁止しているとも考えられます。たとえば、

f :: [a] -> Maybe a

では、a型の値について、何らかの処理をすることはできません。しかし、

g :: [Int] -> Maybe Int

このような型の関数gでは、たとえば数を2倍することもできるし、総和をとることもできます。

引数が多相関数であることを要求することによって、その関数が構造に対してだけ作用する関数であり、なかみの値については、いじることがないということを保証していると考えることができます。

最後に

ざっと、書いてきました。ランク2多相について、こういう見方もできるよ、という話でした。