Skip to content

Instantly share code, notes, and snippets.

@xuwei-k
Created August 9, 2012 02:09
Show Gist options
  • Save xuwei-k/3300312 to your computer and use it in GitHub Desktop.
Save xuwei-k/3300312 to your computer and use it in GitHub Desktop.
Higher-Rank Polymorphism in Scala

原文: http://apocalisp.wordpress.com/2010/07/02/higher-rank-polymorphism-in-scala/ 訳者は英語得意ではなく、訳が怪しいところがあるとおもうので、間違いやつっこみがあれば、ここのコメント欄に記入なりなんなり指摘お待ちしてます。

Scalaでの高ランクポリモーフィズム (Higher-Rank Polymorphism in Scala)

Tim Carstens のポスト Haskell features he’d like to see in other languages をよんで、そのなかの一つにrank-2 typesというものがありました。 Tim は、これ(rank-2 type)を使ったキラーアプリケーションとして、型システムを利用して、リソースへのアクセスの安全性を確保するといいます。

要するに、この機能は、我々が特定の型の値を持っている場合、システムリソースに対して安全にアクセスすることができ、すでに閉じられたもしくは開いていないリソースにアクセスしようとするとコンパイル時に型エラーにすることが可能となります。

型システムによってこれらの保証が得られるのは本当に魅力的です。

最初に、ランク2多相の簡単な説明をしましょう。Scalaでは、通常の多相関数(ランク1多相)は以下のようになります。

def apply[A](f: A => A, a: A): A = f(a)

これはある任意の型の値と関数について適用でき、そして、関数の引数と戻り値は、それに適用される値の型と同じです。上記の関数はある一つの任意の型について適用できます。 しかし、もし関数fがすべての型に対して適用したいとしたらどうでしょうか?

例えば、リストにある要素を加える関数で、それは入力と出力の方が一致する限りすべての型に対して適用できるとします。たとえば以下のようになります。

def singletonList[A](a: A): List[A] = List(a)

この関数を別の関数の引数にしたいとします。ランク1多相では、これは不可能です

def apply[A,B](f: A => List[A], b: B, s: String): (List[B], List[String]) =
  (f(b), f(s))

BとStringはAではないので、これは型エラーになります。つまり、型Aは[A,B]のBに固定されてしまいます。 私達が本当に欲しいのは、引数に対して多相的な関数です。もし仮にScalaにランクNタイプがあるとすれば以下のようになるでしょう

def apply[B](f: (A => List[A]) forAll { A }, b: B, s: String): (List[B], List[String]) =
  (f(b), f(s))

これは有効なScalaコードではありません。この問題を解決できる方法を見ていきましょう。 メソッドはその引数に対して多相になることができますが、一方Function1、Function2といった値は多相にはなれません。

ランク2多相な関数をあらわすために、applyメソッドに型引数をとる新しいtraitをつくります。

trait ~>[F[_],G[_]] {
  def apply[A](a: F[A]): G[A]
}

このtraitはFunction1よりもより一般的です。すなわち、functor F から functor G への自然変換(natural transformation)です。

applyメソッドが実際に呼ばれるまでは、型Aがどこにもないことに注意してください。

identity functor から List functor の自然変換(natural transformation)によって、(最初に例に出した)リストにある要素を加える関数をあらわすことができるようになりました。

type Id[A] = A

val singletonList = new (Id ~> List) {
  def apply[A](a: A): List[A] = List(a)
}

そして、引数としてそのような関数を取ることができます

def apply[B](f: Id ~> List, b: B, s: String): (List[B], List[String]) =
  (f(b), f(s))

これを使えば、Lightweight Monadic Regions で説明されている SIO monad のような、静的に保証された安全なリソースへのアクセスができるのでしょうか。

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment