型クラスペディア
(The Typeclassopedia)

John Kodumal, LaunchDarkly

john@launchdarkly.com

 

翻訳: 大村伸吾

everpeace@gmail.com

ページ移動は「←」「→」キーを使ってください。

型クラスは、Javaのインターフェースに似ていますが、より柔軟です。

Scalaではtraitを使って宣言します:

trait Show[A] {
	def shows(a: A): String
}

"インターフェース"をmix-inするスタイルとは微妙に違うことに注意してください:

trait Show {
	def shows(): String
}	

型クラスに型を追加するにはこうします:

implicit val IntShow = new Show[Int] {
	def shows(a: Int) = a.toString
}

Scalaのimplicitを使います:

def shows[A](a : A)(implicit shower: Show[A]) = shower.shows(a)

もしくはコンテキストバウンドを使います:

def shows[A : Show](a : A) = implicitly[Show[A]].shows(a)

(implicitly は predef で定義されています: def implicitly[A](implicit a : A) = a)

Scalaz は典型的な型クラスをpimpしてくれているので、こうするだけで出来ます:

3.shows // スコープ中に"Show[Int]"インスタンスが必要です。さもなくば型チェックに失敗します。

ファンクタとは、単に「写像できる何か」のことで、次の一個のメソッドで定義されます:

trait Functor[F[_]] {
	def map[A,B](fa: F[A])(f: A => B) : F[B]
}

Option型に対するのファンクタのインスタンスは次のように定義されます:

implicit val OptionFunctor = new Functor[Option] {
	def map[A, B](fa: Option[A])(f: A => B) : Option[B] = 
		fa match {
			case Some(a) => Some(f(a))
			case None => None
		}
}

Haskellでは、引数が逆になります:

class Functor f where  
    fmap :: (a -> b) -> f a -> f b	

Haskell版を見ると、f がファンクタのコンテキストに持ち上げられている(lifted)のがわかります。

自明でない例を見てみましょう: 関数です!

implicit def FunctionFunctor[R] = new Functor[({type l[a] = R=>a})#l] {
	def map[A, B](fa: R => A)(f: A => B) : R => B = (x => f(fa(x)))
}

もう一度、Haskell版のfmapを見てみましょう:

	fmap :: (a -> b) -> f a -> f b

この f a を r -> a 置き換えてみてください。

	fmap :: (a -> b) -> (r -> a) -> (r -> b)

*訳注:FunctionFunctor[R]はRを定義域とする関数を表していて、ここで定義されたmapはR=>aとa=>bからR=>bという関数を返す、つまり関数の合成の概念を表している。

余談: ここが"ボックス"のアナロジーが壊れ始めるところです。そして、「計算のコンテキスト」という曖昧な言葉を使い始めることになるのです。

*訳注:日本では"ボックス"ではなく"コンテナ"というアナロジーが使われることが多い。

def fun[A](a : A) : A = ...

funって何?

val x : List[Int] = ...
def foo[F[_] : Functor](fs : F[Int]): F[Int] = ...

foo(x).lengthって何?

次の例を考えましょう:

def parse(s : String) : Option[Int] = ...

2つのパースされた整数をmapを使って足してみましょう:

parse("3").map((x: Int) => (y: Int) =>  x + y) // ???

これだとOption[Int => Int]という型が返ってきてしまいます。どうすればよいでしょう?

さぁFunctorに能力を追加しましょう:

trait Applicative[F[_]] extends Functor {
	def <*>[A, B](fa: F[A])(f : F[A => B]) : F[B]
	// ... Applicativeにはまだ必要なものがありますが, 後で紹介します
}

これを使うと前の例はこんな風に出来るようになります:

(parse("3")).<*>(parse("Nope").map(x => (y : Int) => x + y))

(オェッ)

少し一般化してみましょう。このような純粋な関数があるとします:

f x y z

この関数を"effectful"な引数を渡して呼ぶにはこのようにします：

f <$> x <*> y <*> z

ScalazのApplicativeBuilder を使うといくらかは改善できます:

(parse("3") |@| parse("Nope"))(_ + _)

もしOptionでない引数があったらどうする?

	(parse("3") |@| 4 /* だめだめ、マコーレーにはカルキンじゃなきゃ */) (_ + _)

そこで、小さな変更を加えましょう:

trait Applicative[F[_]] extends Functor {
	def <*>[A, B](fa: F[A])(f : F[A => B]) : F[B]
	def point[A](a : A): F[A]
}

演習: Option型に対するApplicativeファンクタのインスタンスを定義してください

上の例はpointを使うとこんな風に書けるようになります:

	(parse("3") |@| 4.point[Option]) (_ + _)

再びparseの例を考えます:

def parse(s : String) : Option[Int] = ...

入力されるStringがクエリパラメータだったらどうでしょうか?

val x : Option[String] = params.get("x")

今、Option[String]型の値とString => Option[Int]という型の関数があります。

このときmapしかなかったらどうなるでしょうか。

x.map(parse) // Option[Option[Int]] ??

さぁApplicativeに能力を追加しましょう:

trait Monad[F[_]] extends Applicative {
	def >>=[A, B](fa: F[A])(f : A => F[B]) : F[B]
}

これはバインド(bind)と発音します。

これで、先の例はこんな風に出来るようになります:

params.get("x") >>= parse // Option[Int]

もっとweb-basedな計算機らしい例にしてみましょう:

params.get("x") >>= parse >>= (x => (params.get("y") >>= parse) map (_ + x) )

(オェッ)

最後の例から、こんな典型的なパターンが考えられます:

monadicX >>= (x => monadicY >>= (y => monadicZ map (z => x+y+z))) 

最後のmapまでbindが入れ子になっています

少しリフォーマットしてみるとこうなります:

monadicX >>= (x => 
monadicY >>= (y => 
monadicZ map (z => 
   x+y+z
))) 

Scalaではfor-comprehensionを使ってこう書けます:

for {
	x <- monadicX
	y <- monadicY
	z <- monadicZ
} yield x + y + z

(大分良くなった!)

Option よりも先の例に進みましょう。 関数(function)にもファンクターのインスタンスがあることを思い出してください。

def map[A, B](fa: R => A)(f: A => B) : R => B = (x => f(fa(x)))
	

関数ファンクタに対するモナドインスタンスはどうなるでしょう?

implicit def FunctionMonad[R] = new Monad[({type l[a] = R=>a})#l] {
	def >>=[A, B](fa: R => A)(f: A => R => B) : R => B = (x => f(fa(x))(x))
	...
}
		

これはReaderモナドとして良く知られるものです. 少し不可思議に見えますが、どういう場面で便利に使えるのかを見てみましょう。

Webアプリの絶対URLを構築しなければならないとしましょう。アプリはベースURLを持っているとします。

def makeAbs(base: AbsURL, url: URL): AbsURL = AbsURL(base + url)

しかし、これだと繰り返しが多くなってしまいます:

val links = Map("self" -> makeAbs(baseURL, "/widgets/523"),
                "parent" -> makeAbs(baseURL, "/widgets") )

そこで、makeAbs を Reader として定義しましょう:

def makeAbs(url: URL): Reader[AbsURL, AbsURL] =
	Reader(base => AbsURL(base + url))

これまで行ったのは全部構文のトリックで、こんな風に書けるようになります:

(for {
	self   <- makeAbs("/widgets/523")
	parent <- makeAbs("/widgets")
} yield Map("self" -> self, "parent" -> parent))(baseURL)

Reader を、最終的な結果を生み出すためのリードオンリーな環境(引数)を伴う計算、と考えてみてください。

ここに、モナドのアイデアを理解するための武器があります。これを考えてみてください:

for {
	x <- monadicX
	y <- monadicY
} yield x + y

Q: このコードはどう動くでしょうか?

A: モナドの種類によります。

モナドを使ったfor-comprehensionは、モナドによってセマンティクスを定義される埋込みプログラミング言語と見なせます:

では、なぜ入れ子になったモナドが醜いかを見てみましょう。計算機にリードオンリーな環境を追加してみましょう:

type Env = Map[String, Int]
def lookup(s: String): Reader[Env, Option[Int]] =
	Reader(env => env.get(s) orElse parse(s))

すると、Readerを使うことで、envを繰り返し書かずに、２つの数を足し合わせることが出来ます:

for {
xOpt <- lookup("3")
yOpt <- lookup("y")
} yield (for {
				x <- xOpt
				y <- yOpt
			} yield x + y)

(オエッ)

ファンクターだとうまくできる:

implicit val ComposedFunctor[M: Functor, N: Functor] = new Functor[...] {
	def map[A, B](fa: M[N[A]])(f: A => B) : M[N[B]] = fa.map(_.map(f(_)))
}

皮肉なことに(結婚式の日の雨みたいに)、一般的には、モナドは合成出来ません。挑戦してみてください:

implicit val ComposedMonad[M: Monad, N: Monad] = new Monad[...] {
	def >>=[A, B](fa: M[N[A]])(f: A => M[N[B]]) : M[N[B]] = // ???
}

一つの解決策は モナド変換子 です。 変換子は モナディックな値の "ラッパー" です:

case class OptionT[F[+_], +A](run: F[Option[A]]) {
	// 中身はこの後すぐに出てきます
}

ラップされた値は、入れ子になった内部のモナドのユーティリティ関数を公開します:

OptionT(List(Some(3), None, Some(4))).getOrElse(0) // List(3, 0, 4)

最も大切なのは、この変換子自体がモナドになることです:

case class OptionT[F[+_], +A](run: F[Option[A]]) {
	def >>=[B](f: A => OptionT[F, B])(implicit F: Monad[F]): OptionT[F, B] =
		new OptionT[F, B](
			self.run >>= (a => a.match {
								case None => F.point(None)
								case Some(s) => f(s).run
							}))
	...
}

変換子はどれだけでも深く入れ子に出来ます!

scalaz は主なモナドに対してモナド変換子を定義しています:

• OptionT
• ListT
• EitherT
• ReaderT, aka Kleisli

先の例をReaderTを使って綺麗にしてみましょう。 以前の例はこうです:

for {
 xOpt <- lookup("3")
 yOpt <- lookup("y")
} yield (for {
          x <- xOpt
          y <- yOpt
         } yield x + y)

ReaderT を使うとこうなります:

for {
	x <- Kleisli(lookup("3"))
	y <- Kleisli(lookup("y"))
} yield x + y

(大分良くなった!)

モナド変換子にも型クラスがあります。その型クラスには一つだけliftM という関数が定義されています:

trait MonadTrans[F[_[_], _]] {
  def liftM[G[_] : Monad, A](a: G[A]): F[G, A]
}

liftM はベースとなるモナドの計算を変換されたモナドに"持ち上げる"機能を提供します:

(for {
	x <- OptionT(List(Some(3), None))
	y <- List(1,2).liftM[OptionT]
} yield x + y).run // List(Some(4), None, Some(5), None)

Monadのもう一つの定義方法はモナドの合成問題にある気付きを与えます。 バインド(>>=)の変わりに, join と呼ばれる関数を定義する方法です:

trait Monad[F[_]] extends Applicative {
	def join[A](fa: F[F[A]]): F[A]
}
		

join を使って, M[N[_]] のモナドを作りましょう。 F[_] の変わりに M[N[_]] を使うと, こうなります:

def join[A](fa: M[N[M[N[A]]]]]): M[N[A]]

(ヒャー!)

M と N で定義されている join は役に立ちません。なぜなら、違うモナドに"ブロック"されてしまっているからです。でも、もしモナドを"交換(commute)"できたらどうでしょう？つまり M と N の順番を入れ替えられたら?

def sequence[A](a: M[N[A]]): N[M[A]]

うまくいきます! 与えられた sequence 関数を使って合成されたモナドを定義することが出来ます。

Traverse 型クラスは2つのファンクタを交換する機能だけを提供します:

trait Traverse[M[_]] extends Functor {
	def sequence[N[_]: Applicative, A](mna: M[N[A]]): N[M[A]]
}
	

(scalaz では、traverse: M[A] => (A => N[B]) => N[M[B]] という関数に基づく、別の定義方法を採っています。)

Traverse はそれ自体で非常に便利です。例えば、非同期な計算のリストを、リストを返す非同期な計算に変換してみましょう:

List(future { doCalc1() }, future { doCalc2() }).sequence // Future[List[Int]]

これは、型付きの fantasy land に住む利点の一つです...

もしモナド N が Traverse の条件を満たすならば、 "タダ(free)"で合成モナドを得ることが出来ます:

implicit val ComposedMonad[M: Monad, N: Monad: Traverse] = new Monad[...] {
	def >>=[A, B](fa: M[N[A]])(f: A => M[N[B]]) : M[N[B]] = // ???
}

演習: ComposedMonad の >>= を実装しなさい。

"タダ(free)"の変換子はいつも希望通りのセマンティクスを提供するとは限りませんが、モナド変換子の実装として利用することが出来ます。scalaz では、この"タダ(free)"の定義方法は使っていないことに注意してください。