map ∷ (a→b) → [a] → [b] -- can be implicit
map f [] = []
map f (x:xs) = f x : map f xs
-- instantiation is always invisible
sqrs = map (^2) [1..10]Ingo Wechsung 氏による寄稿
パラメータ多相続論
プログラマは皆、同じことの繰り返しを避けようとするものです。共通のパターンに気づいたときはいつでも、一般化された解法を様々な形で (すなわち多相的に) 再利用できるように、そのパターンを抽象化しようとします。多相性を実現するには主に、オブジェクト指向における部分型、およびパラメータ付きの型の二つの手法があります。
パラメータ多相 は各種の主流プログラミング言語に導入されてからかなり経つものの、多くの人にとってこの用語は馴染みがありません。例えば Java では、総称型 という名前になっています。
基本となる考え方はシンプルです。関数やデータ型（あるいはメソッドやクラス）の型宣言において、型を 型変数 として与え、具体的な型を後で決定することができます。このような型変数は特定の場所で 導入する ことができますが、その場所は言語によって異なります。例えば Java では明示的に型変数を導入することが必要になります。その後で、関数やデータ型を使用する際、導入した形式的な型変数は具体的な型 (そのコンテクストで有効な他の型変数の場合もある) で インスタンス化 されます。
以下に挙げたのは、Frege による古典的な map 関数の抽象的な型宣言とその実装、および具体的な型として整数のリストを取った時の使用法です。
Haskell による古典的な map 関数
また以下に、もしこれを Java で実装した場合にどうなるかを大まかに示します。
Java による map 関数の仮実装
// generic types are explicit
public static<A,B> List<B> map(Function<A,B> f, List<A> xxs) {
// ... details omitted ...
}
// instantiation is visible
static List<Integer> sqrs = <Integer, Integer>map(
x -> x*x,
Arrays.asList(1,2,3,4,5,6,7,8,9,10));Frege の型推論 は map の型を完全に自動で推論できますが、通常の場合、明示的に型宣言を付けます (Eclipse プラグインのようなツールを使用すればワンクリックで可能です)。
重要なのは、Frege では、型変数の導入は 暗黙的 に行うことができ、型変数のインスタンス化は常に目に見えない形で行われるということです。しかしながら、推論の結果 map は sqrs の右辺に現れる型である (Int→Int) → [Int] → [Int] でインスタンス化されます。ただし目に見えないだけあって、多くの Haskell や Frege のプログラマは、インスタンス化の存在すらまったく関知しません。
一方 Java では、メソッド宣言における型変数の導入は必ず明示せねばならず、そのインスタンス化とともにコード上で明らかに見て取れます。Java のコンパイラは、常にではありませんが、場合によってはインスタンス化された結果をうまく推論してくれることもあります。
ジェネリクスでは多相性が不十分な場合
コード中で関数 (reverse や drop n) が、「最初にその関数を第一のリストに適用し、次に第二のリストにも適用し、それぞれの結果を zip でまとめる」のような形で繰り返し使用されるとしましょう。
同じパターンの繰り返し
zip (drop n somelist) (drop n otherlist)
zip (reverse somelist) (reverse otherlist)このパターンが複数回登場する時、reverse や drop n はいずれも、ある型を同じ型に移すように見えます。
reverse と drop n の型
∀a.[a] → [a] --(1)この記事では意味を明確にするため、(1) のように型に明示的に量化子 (∀a.) をつけて表記します。実際のコードではこの量化子は必須ではなく、通常省略されます。
このような型を持つ関数で、よく使われるものを例として以下に挙げます。
∀a.[a] → [a] 型の関数たち
reverse
tail
init
drop 10
take 20
id意図するところは明らかです。二つのリストを組み合わせたいのですが、組み合わせる操作は両者に何らかの変換を施した後に行いたい、という状況です。一言で言えば
f を複数回使用する
zip (f somelist) (f otherlist)という操作を適切な f について行い、かつ括弧と f の繰り返しを排除したい (f はそれ自身が長大な式になっている場合があることを思い出しましょう) ということです。
次のように書くための関数 fzip が必要であるように思われます。
fzip によるパターンの抽象化
fzip f somelist otherlistこれを可能にする実装として、思い浮かぶのは以下のようなものでしょう。
試しに
fzip を実装してみるfzip f [] [] = []
fzip f xs ys = zip (f xs) (f ys)さて、何か簡単になったでしょうか？
しかしちょっと待ってください！ REPL に fzip の型を問い合わせると、こんな答えが返ってきます。
fzip に対して推論される型
∀a b.([a]->[b]) -> [a] -> [a] -> [(b,b)]何らかの理由により、二つのリストの要素の型は同じであることが強制されています！
しかし、書き直そうとしている二つの式には、この制限はありません。そもそも、ここでリストを加工するために使おうとしている関数たちは要素の型を限定しておらず、任意のリストに対して動作するものです。
ともあれ現状では、一つ目のリストと二つ目のリストが同じ型を持たない場合に上で述べたような書き直しを行おうとすると、常に型エラーが発生してしまいます。例えば文字のリストと真偽値のリストを fzip することはできないのです。
では、fzip のどこがおかしいのでしょうか？
この場合について理解するため、インスタンス化についてどのように述べられていたかを思い出す必要があります。以下のような式において、
うまく動かない例
fzip reverse ['a', 'b', 'c'] [false, true]
-- type error in expression [false,true]
-- type is : [Bool]
-- expected: [Char]reverse はどんな型でインスタンス化されるべきでしょう？ 仮にその型として
[Char] → [Char]を選んだとしたら、真偽値のリストを反転させることができないでしょう。そして
[Bool] → [Bool]を選んだとしたら文字列のリストを反転させることができません。
上記の例では、コンパイラは文字列のリストが引数になっていることから reverse を [Char] → [Char] でインスタンス化することを選択し、それゆえ残った引数も同じ型を持つことを期待します。結局のところ、これが fzip の型に要求される条件であり、エラーメッセージの原因です。
しかし、一体なぜここでインスタンス化することが必要になるのでしょう？ これはヒンドリー・ミルナー型システムにおける型推論の制限によるものであり、ヒンドリー・ミルナー型システムは ML、Haskell、F# および Frege のような言語の型システムの基盤となっています。この制限によれば、 束縛されたラムダ式の値 (いわゆる「関数引数」) は 単相的 であることが仮定されています。したがってインスタンス化が必要であり、さもなくば型推論は 決定不能 になってしまいます。
型を階層付ける
言い方を変えれば、ヒンドリー・ミルナー流の (以下 HM と略す) 型推論で扱うことができるのは、ランク 1 の多相性だけです。また別の言い方をするならランク 1 の型は、HM アルゴリズムが推論できる多相型とちょうど一致します。これは実質的に、厳密に HM に沿った言語においては、高階関数は単相的もしくは単相的になるようにインスタンス化された関数しか引数に取れないということを意味します。残念なことに、fzip は ML や F# では書くことができないのです！
高階型の使い方
幸運なことに、高階型に対して 型推論 は決定不能ですが 型検査 はそうではありません。すなわち、コンピュータは式につく高階型を追加情報なしで見つけることはできませんが、与えられた型と式に対して、その式がその型になりうるかどうかは判定することができます。
GHC (言語拡張 RankNTypes を指定した場合) や Frege の型検査器では、この事実を用いて多相関数を引数として与えられるようにしています。
この仕組みがうまく機能するためには、多相型の引数を取る関数、もしくは少なくとも多相型である引数自身に型注釈がついている必要があり、型推論が残りのギャップを埋めてくれます。
このような型注釈が存在する場合には型検査器は、関数引数がインスタンス化されるべき型を探す代わりに、単に引数の型が注釈された型 以上に一般的 であるかどうかを検査します。
したがって今回の問題は、単に関数引数 f が多相的であることを明示すれば解決することができます。これは以下のような注釈を fzip につけることで可能です。
fzip を高階多相型に対応させる
fzip ∷ (∀ a.[a] → [a]) → [x] → [y] → [(x,y)]
-- --------------- universally quantified
-- polymorphic type of f
fzip f xs ys = zip (f xs) (f ys)fzip のコードはそのままです！ しかし型を見ると、f は 任意の 型に対して、リストを取って同じ型のリストを返す関数であることがわかります。さらに今回の型宣言では、f が作用するリストの型は、実際の引数として現れるリストの型と完全に切り離されています。しかしだからこそ f が任意の型のリストに対して作用することができ、両方の引数に安全に適用できるのです。
ポイントとなるのは、関数引数が全称量化された多相型になっている点です。何を入れるべきかよくわからないときは、REPL を使用すればこのような関数に対して型が確認できます。
REPL の助けを借りる
:type reverse
[α] -> [α]量化された型を指定するためには、キーワード forall (∀ と書くことも可能) をつけて型の中に現れる型変数をすべて並べて書きます。もし型変数名が気に入らない場合は、単純に名前を付け替えることも可能です。例えば、コンパイラは以下に挙げた型を区別することができません。
様々な型宣言
forall a.[a] → [a]
forall b.[b] → [b]
∀ quetzalcoatl.[quetzalcoatl] → [quetzalcoatl]一方、型宣言をすべて与えるのではなく、f の型宣言のみを行内に書くことで fzip を定義することもできます。
f のみに注釈をつける
fzip (f ∷ ∀a.[a] → [a]) xs ys = zip (f xs) (f ys)しかしこれはかなり読みづらいように思います。
さて、これで fzip を様々な関数と組み合わせて使うことができます。しかしそれらの関数の型は、f に注釈として付けられた型 以上に一般的 である必要があります。例えば fzip を [Int] → [Int] のような制限された型の関数に対して使用することは、たとえ両方のリストが整数のリストだったとしても不可能です。
いくつか例を挙げます。f の型をコメントとして付けておきます。
関数 f の実例
fzip id [1..10] ['a'..'z'] -- ∀a. a → a
fzip (drop 3) [1..10] ['a'..'z'] -- ∀a.[a] → [a]
fzip reverse [1..10] ['a'..'z'] -- ∀a.[a] → [a]
fzip (map id) [1..10] ['a'..'z'] -- ∀a.[a] → [a]
fzip tail [1..10] ['a'..'z'] -- ∀a.[a] → [a]
fzip (const []) [1..10] ['a'..'z'] -- ∀a b.a → [b]以上が高階型の概要です。高階型の欠点や改良方法については、また別の記事で再度、触れることになるでしょう。
今回の内容に心惹かれた人のために、次回記事までの宿題を出しておきます。
-
fの型を、もっと一般的な∀a b.[a] → [b]としないのは何故か？ (最後に挙げた例がヒントになっています) -
(真の Java の達人向け) キャストや
@SuppressWarningsを使用せずに、Java でfzipを実装して、警告なしでコンパイルできるか？ (実は可能なのです)
| Java solution |