多相関数を第一級で取り扱う

多相関数を第一級で扱うとはどういうことか

(パラメトリック)多相関数 ((parametric) polymorphic function，generic function) とは，型の一部にパラメータを含み，そのパラメータにどのような型がきても関数として同じ動作を行うような関数のことだ．といっても，何か特別な技巧を知っていないと扱えない何かというわけではなく，Haskell を触っている人なら日常茶飯事的に扱っている．具体的な例として，以下の関数がそうだ:

1
2
3

append :: [a] -> [a] -> [a]
append []     ys = ys
append (x:xs) ys = x : append xs ys

append はリストを2つ受け取ってリストを返すわけだけど，リストの要素についてはパラメータ化されており，すべてのリストの要素の型が同じ型であること以外は特に制限をつけていない．実際に使う場合には，この要素の型は使う側で決めることができる．例えば，

1
2

f :: [Int]
f = append [1,2] [3,4]

とした場合は，型推論によりパラメータ a に Int 型が割り当てられ，上の式中の append は [Int] -> [Int] -> [Int] という型を持つようになる．このように，パラメータが一切存在しない関数は，多相関数と対比して単相関数 (monomorphic function) と呼ばれる．使う場合にパラメータ a に別のパラメータが割り当てられることもある．例えば以下の場合を考えてみる:

1
2

f :: b -> [b] -> [b]
f x xs = append [x] [xs]

この場合， append のパラメータ a には f のパラメータ b が割り当てられ， append :: [b] -> [b] -> [b] という型になる．なお，多相関数はどのような型に対しても成り立つ必要があるので，次のようなものは多相関数にはならず型検査が失敗する:

1
2

f :: a -> Int
f x = x

これは a が Int の場合は大丈夫だが， Bool などの場合はだめだ．どのような型 a でも a -> Int が成り立つというのが多相関数型 a -> Int の意味で，つまりは a が Bool 型の場合でも成り立たなければならないが，実際はそうではない．よって型検査に失敗するわけだ．つまり，多相関数はあくまで 任意の パラメータに対して指定した型が成り立つものであって，指定した型が成り立つパラメータが 存在する関数ではない ということには注意してほしい [1]．多相関数は実際に引数にどういう型を持つ値が来るか特定できないため，通常の関数と比べると実装には工夫が必要になる．多相関数を実行時にどういう表現で持つかは，プログラミング言語それぞれで色々手法があるが，主に

テンプレート方式

多相関数のパラメータが全て何らかの型が割り当てられ，単相になるような使われ方をしている箇所で，その型に対して一つ関数の実体を作る．

型消去方式

多相的な値に対して，実行の動作に必要なメタ情報を追加したデータ型を一つ割り当て，コンパイル時型からメタ情報を作成し，多相関数にはメタ情報を付与した値を渡し，それを扱える操作を組み込む．

の二種類がある．GC 付きの言語では， GC のフラグなども値にメタ情報として付与しなければならないため，そこに幾つかメタ情報を追加するだけで対応できる型消去方式と相性が良い．逆に C++ や Rust などではテンプレート方式が使われている．GHC でも型消去方式が主に使われている [2] ．

ところで，引数に多相関数を受け取るという指定を書けないのだろうか？ 例えば，先ほどの append は共通の型の要素を持つリストであれば，どんな二つを受け取っても動作するわけだ．しかも型消去方式であれば，多相関数に対する実体は，メタ情報などを取り扱うルーチンは組み込まれているものの，一つの関数表現であるはずだ．つまり，以下のような関数が書けてもおかしくないとは思えないだろうか？

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

type Append = [a] -> [a] -> [a]

f :: Append -> ([Int], [Char])
f ap = (ap [1] [2], ap ['a'] ['b'])

appendInts :: [Int] -> [Int] -> [Int]
appendInts xs ys = append xs ys

append :: [a] -> [a] -> [a]
append = ...

-- valid: f append
-- invalid: f appendInts

ここで， f は [a] -> [a] -> [a] 型を持つ多相関数，つまりどれか一つの型でこのような形をしているのではなく，どのような型 T に対しても [T] -> [T] -> [T] の演算ができる関数を要請している．そして，中では一方で a を Int に割り当てて使用し，もう一方で a を Char に割り当てて使用している．この考え方でいうと， appendInts は失格で， Int のリストしか処理できないため f に渡せてほしくない．

このような関数 f を書くことは可能だろうか？ 残念ながら標準の Haskell の範囲ではこのようなことは実現できない [3] ．もしかしたら，以下のように f に型付けをすればいいのではないかと思う人がいるかもしれない:

1
2

f :: ([a] -> [a] -> [a]) -> ([Int], [Char])
f ap = (ap [1] [2], ap ['a'] ['b'])

この関数は型検査が通らないうえに，まるで先ほどの関数と意味が違うものになってしまう．この関数の意味は，どのような型 a を持ってきても，その型に対する リストの結合ができる 関数 を受け取って，値を返せる関数だ．つまり受け取るものは単相関数でもいいわけだ．だが，元々の f は どのような型に対しても リストの結合ができる 多相関数 を受け取りたいわけだ．つまり，前者は f appendInts という呼び出しでも全然構わなくて，その場合 a に Int が割り当てられるだけなわけだが，後者，つまり元々想定していたものは f appendInts は許容したくないわけだ．

さて，多相関数を受け取る関数を書くことは標準ではできないわけだが，実際問題としてこのようなことができると何がうれしいのだろうか？ 実はかなり嬉しいことがあるのだが，ここではその一例を紹介する．より豊富な応用例の紹介は，後の節に譲る．例えば，以下のデータ型に対して，そのデータ型を文字列表現で分かりやすく表示する関数を作ることを考える:

1
2
3
4

data A
  = DInt Int
  | DBool Bool
  | DNode A A

単純には Show のインスタンスを作ればいいわけだが，ここでは Int や Bool の表現は切り替え可能にしたいとする．この時に，多相関数を受け取る関数が書ければ，以下のようなことができる:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

type PolyShow = Show a => a -> String

showA :: PolyShow -> A -> String
showA pshow = go
  where
    go x = case x of
      DInt  i -> "DInt " ++ pshow i
      DBool b -> "DBool " ++ pshow b
      DNode x1 x2 -> "DNode (" ++ go x1 ++ ") (" ++ go x2 ++ ")"

-- >>> d = DNode (DInt 0) (DBool True))
-- >>> showA show d                         == "DNode (DInt 0) (DBool True)"
-- >>> showA (\x -> "(" ++ show x ++ ")") d == "DNode (DInt (0)) (DBool (True))"

showA は，パラメータに割り当てられる型が Show のインスタンスであると制限を付けた多相関数を受け取ることで， DInt や DBool の中身に関して表示を切り替える自由を許している．そして，実際の実行例として上げているものは，一つはそのまま show を使って表示しており，もう一つは Int や Bool の値についても () で挟んで表示するようにしている．こうすることで，表示に対してのパースがより簡単になる．多相関数を受け取る関数を書けない標準の Haskell では， Int や Bool それぞれで関数を引数として受け取らなければならない [4] ．今回は二種類だからいいが，もっと末端の型が増えればその分引数が膨れ上がっていくことになる．また，今回の例でいえば，同じ関数を引数分書くことになり，かなりボイラープレートが増えるだろう．これらは，上のように多相関数を受け取れるようになれば解決できるわけだ．

RankNTypes

というわけで， Haskell 標準では多相関数を受け取る関数は書けなかったわけだが，我らが GHC にはそれを可能にする拡張がある．それが， RankNTypes だ．具体的なシンタックスとして，一番最初の多相的な append を受け取る関数は，以下のように書ける:

1
2
3
4

type Append = forall a. [a] -> [a] -> [a]

f :: Append -> ([Int], [Char])
f ap = (ap [1] [2], ap ['a'] ['b'])

なお，直接 f :: (forall a. [a] -> [a] -> [a]) -> ([Int], [Char]) と書いてもよい．これは，かなり直感的な型表記だと思う．そのままの意味で， Append 型は「どのような型 a を持ってきても， [a] -> [a] -> [a] が成り立つ型」と言っている．なお，この拡張下では以下のような表記も書ける:

1
2
3

append :: forall a. [a] -> [a] -> [a]
append []     ys = ys
append (x:xs) ys = x : append xs ys

なお，この拡張下でも標準と同じく forall a. の部分は省略してもよいわけだが，こう書くとより append が多相関数でパラメータ a を使用していることが直感的に分かりやすいだろう． forall の後に型制約を書くことも可能なので， showA についてもこの拡張下では実現できる:

1
2
3
4
5
6
7
8
9

type PolyShow = forall a. Show a => a -> String

showA :: PolyShow -> A -> String
showA pshow = go
  where
    go x = case x of
      DInt  i -> "DInt " ++ pshow i
      DBool b -> "DBool " ++ pshow b
      DNode x1 x2 -> "DNode (" ++ go x1 ++ ") (" ++ go x2 ++ ")"

これはコンパイルが通るようになる．また，この拡張下ではデータ型に多相関数を格納することも可能だ:

1

newtype WrapId = WrapId (forall a. a -> a)

WrapId は多相関数，つまりどんな a に対しても a -> a が成り立つ関数しか受け取れないため， WrapId (not :: Bool -> Bool) みたいな特定の型のみで a -> a の形になるものは型検査が通らないことに注意だ．

なお， RankNTypes の単語の意味だが，元々の概念として，

• 単相型を rank-0
• $\sigma_{n + 1} \mathrel{::=} \sigma_n \mid \sigma_n \mathrel{\text{\texttt{->}}} \sigma_{n + 1} \mid \text{\texttt{forall a.}}\, \sigma_{n + 1}$ を満たす型，つまり関数型の引数部分に rank を一減らした型を指定していいという型を rank-$(n + 1)$

と呼ぶ型システムがあり，通常の Haskell の範囲では rank-1 までしか使えないが，それを任意の $n$ に対して rank-$n$ の型が扱えるようにするという意味で命名されている．ただ，この意味が分かりにくいので「arbitary rank types (任意のランクの型)」という名称が一般的には用いられている．この拡張下では，任意の位置で多相関数を受け取れ，また多相関数を受け取って何かをするような多相関数すら受け取れるので，多相関数を通常の関数と同じように扱うことができる [5] ．

RankNTypes の応用

RankNTypes の強みの一つとして，上の例のように違う型に対する処理を一つにまとめて提供できるというものがある．これは事実上型クラスがやっていることでもあるのだが，それを一々型クラスを作らなくても自然な形でプログラミングできるのが，強みと言えるだろう．前挙げた例以外でも，例えば Http サーバを作ることを考えてみた時に，リクエストの型によらずに実装できる部分は多い．具体的には，エラーが起きた時に 500 エラーレスポンスを返す際は，リクエストに対して特に言及をしなくてよいはずだ．ただ， 500 を返すか，それとも 503 などを返したい場合などもあるのかを，ユーザに委ねたい場合もあるはずだ．その場合に，

1
2
3
4
5
6
7

{-# LANGUAGE BlockArguments #-}

server
  :: (forall req. req -> IO (Request req) -> IO (Response req))
  -> Request -> IO (Response Request)
server handle req = handle req do
  ...

などにしておくと，この関数をテストしたい場合に Request を簡易的なものにした TestRequest 型を使うようにしておいても，同じユーザから渡された関数で処理のエミュレートができるだろう．もし， RankNTypes がない場合は Request と TestRequest 両方に対して関数を定義してもらわなければならないが，それが解決できるわけだ．ところで，これはモジュラリティにも貢献している．ユーザはエラーを処理する関数において，実際のリクエストに対して触れることができない．つまり，ある程度できることが制限できるわけだ．そして， Request 型の実装とは独立に，エラー処理関数の実装が行えたことを型システムで保証できるわけだ．

一般に， RankNTypes はある種のモジュラリティを保証するために使用することもできる．その利用例として有名なのが ST モナドだ． ST モナドは破壊的変更を伴った操作をプログラム中で書くことができ，しかもそれを純粋な世界に紐とく関数 runST :: (forall s. ST s a) -> a が提供されている．ただ， ST モナドはなんでも操作を許容しているわけではなく，配列操作やリファレンスをいじる操作のみを ST モナドの s に言及した多相関数として定義しており，必ず破壊的な操作にはパラメータ s が多相的なまま残るようになっている．そして， runST はその多相的なまま残った s に対して， s によらずに a の型が決まるならば ST s を外せることにしている．そして， s によらずに a の型が決まる場合に，破壊的操作で生まれた配列のインスタンスやリファレンスが実行時にどのような実体を持っていようとも，結果が決定的になることを保証できるよう， API がうまく設計されている．このより詳細な解説は，「STモナドはなぜ変更可能な参照を外へ持ち出せないのか調べてみた」で行われているので，ぜひ参照してほしい．一般に，このような API 設計による型安全なメモリ管理の仕組みを実現する方法は， monadic region という名前で知られている．興味があれば，そちらも調べてみてほしい．

RankNTypes のもう少し別の応用として，中間データ構造を削減するための手法が知られている．例えば，リストは GHC では融合変換により，自動的にいい感じに関数合成の中間で生まれたデータが削減されるわけだが，それを明示的に RankNTypes で模倣することができる．整数のリストを例にとってみよう．まず，整数リストを以下のように表現する:

1
2
3

newtype IList = IList
  { unIList :: forall r. (Int -> r -> r) -> r -> r
  }

この表現に対して，通常のリストの相互変換が以下のように定義できる:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

{-# LANGUAGE BlockArguments #-}

toList :: IList -> [Int]
toList (IList xs) = xs (:) []

fromList :: [Int] -> IList
fromList xs = IList \c n -> go c n xs
  where
    go :: (Int -> r -> r) -> r -> [Int] -> r
    go _ n []     = n
    go c n (x:xs) = c x (go c n xs)

このリストに対して，次のような map を提供する:

1
2

map :: (Int -> Int) -> IList -> IList
map f (IList xs) = IList \c n -> xs (\x r -> c (f x) r) n

ちょっと読みにくいが，この関数は，上の相互変換において，元のリストの map と同じ相当の操作を行える．詳しいことは説明しないが，ここで重要なのは，どこにもコンストラクタが現れていないということだ．本来 map ではコンストラクタのパターンマッチによる分解と，コンストラクタを新たに付与する操作が必要だったわけだが，この map ではそのような操作は必要ない．これはいわばイテレータによる map で， IList は [Int] のイテレータ表現と言うとしっくりくる人がいるかもしれない．とにかく，この map を並べて使うと，通常のリストを融合変換下で通常の map を並べるのとそう変わらない効率で使うことができる．このように RankNTypes による連続処理で中間構造生成を必要としない表現へのエンコードは，リスト以外でも研究されている．興味があれば，調べてみてほしい [6]．

Advanced Topics

さて，これまで RankNTypes は多相関数を第一級として扱えると紹介してきたわけだが，実は話はそう簡単ではなく，この拡張は幾つかの点でそれを逸脱している．最後にそれにさっと触れて終わろうと思う．

まず， RankNTypes を使うと次のような関数を書くことができる:

1
2
3
4
5
6
7

class A a where
  giveInt :: Int

class A Int => B

f :: B => (A Int => Int) -> Int
f r = r

この関数 f が言っていることは，

1. B のインスタンスがあるときに，
2. A Int のインスタンスがあるとき Int の値を返せる関数を受け取って，
3. その関数は今， B のインスタンスから A Int のインスタンスを導けるはずなので，
4. そこから Int の値を返せる

ということだ．ただ，現実問題として A Int のインスタンスは存在せず， B のインスタンスもないため，この関数は無意味ということにはなる．もちろん，他のモジュールで orphan インスタンスがあればこの関数を実行することはできるわけだが，正直あまり有用なようには見えないだろう．このような関数が有用な場面はあるんだが，この記事の内容から少し逸脱するので，興味があれば調べてみて欲しい [7] ．とりあえず，ここで言いたいことは，以上の関数が RankNTypes を有効にすると書けるようになるということだ．では，なぜ RankNTypes を有効にすると，このようなものが書けるようになっているのだろう？実は上の関数は，この特別な機能なしでも容易にシュミレートできる．以下のようにだ:

1
2

f :: B => (forall a. (a ~ Int, A a) => a) -> Int
f r = r

そう，多相的なものに type equality で制約を適当に入れてやることで，実現できる．上の表記はこのエイリアスで，簡単に書けるようにしたものと思ってもらってもいい．なので，厳密には RankNTypes とは arbitary rank types + 上のことを書くための便利な簡易構文を追加する拡張と言った方が正確だろう．

上のは単に RankNTypes はおまけもついてるよという話なのだが，もう一つ致命的な注意点がある．それは， RankNTypes でも以下のようなプログラムは書けないということだ:

1
2

f :: (forall a. a -> Bool, forall a. a -> Int)
f = (const True, const 0)

これは， forall a. a -> a 型の多相関数のリストを作ろうというプログラムだ．やってることは，そう複雑ではなさそうだが， GHC ではこのプログラムを RankNTypes 下でコンパイルすることはできない．もし，これ相当のことがしたい場合，以下のように newtype を挟んでやる必要がある:

1
2
3
4

newtype ConstFunc r = ConstFunc (forall a. a -> r)

f :: (ConstFunc Bool, ConstFunc Int)
f = (ConstFunc (const True), ConstFunc (const 0))

一般に， RankNTypes には「型のパラメータに，多相的な型を割り当てることはできない」という制約がある．上の例では，タプルのコンストラクタは， (,):: forall a b. a -> b -> (a, b) という型を持つため，パラメータ a に forall a. a -> Bool という多相の型を， b にも forall a. a -> Int という多相の型を割り当てる必要が出てくる．これが RankNTypes の制約に違反するのだ．newtype で作った型の方は単相であり，多相的でないため，この制約を回避できるわけだ．

上記の制約は，可述的多相 (predicative polymorphism) という名前の体系として知られており，この制約さえ取っ払ってしまった体系を非可述的多相 (impredicative polymorphism) または第一級多相 (first-class polymorphism) と呼ぶ．可述的多相では上記のように，多相関数を要素に持つタプルなどは直接は作れないわけで，その意味で単相的な値より劣るわけだが，非可述的多相になるとそれすら取り扱えるようになる．そうなると多相関数を第一級で取り扱えると言って良いだろう．しかし，この体系は幾つか理論的・技術的な困難が知られている．興味があれば調べてみると良いだろう [8] ．

まとめ

というわけで RankNTypes 拡張の紹介をした．見て回った感じ，案外 RankNTypes の日本語文献がなかったのが書こうとした動機．なお，この記事中で，いくつか書かなきゃなみたいなこと結構省略したし，割と何も考えずに今持ってる知識だけで書いてるので，間違い結構あるかもしれん．その内，需要ありそうだったら，ちゃんと参考文献とか諸々付けたものをどっかに寄稿したいなとは思ってる．未来の俺，がんばってくれ．てことで，以上．