HaskellのdoとScalaのfor式とEitherとMonadPlus

標題の通り、色々書きたいことあって長くなってわかりにくくなりそうですが、頑張って書いてみます。なお、(2.8や2.9でもほぼ同じだと思いますが)Scalaのversionは2.10.1です。Haskellはghc7.4.2です。


「for文は7つしか使っていません(ドヤッ」という謎の主張を含んだスライドが最近流行っていましたが、まずScalaのfor式はMonadのための構文というのはお馴染みですよね!!!
Monadそのものから説明していたらとても長くなってしまうので、そのあたりの説明は飛ばします。Scalaのfor式は、コンパイル時に内部的に以下のメソッドの組み合わせに変換されます

  • map
  • foreach
  • flatMap
  • filter
  • withFilter

なので、上記の5つのメソッド名は、予約語ではないですが、for式に変換されるという点において特別です。
for式を「Monadのための構文」として捉えた場合、関係あるのはflatMapとmapですね。
foreachは、「yieldを使わず値を返さない場合」なので、多重ループといった感じです。これ以降foreachについては触れません。

で、残った2つのメソッドである「for式におけるfilterとwithFilterとは、そもそもなんなのか?」というのを深く掘り下げて、勝手に解釈してみるのがこの記事のテーマです。

ところで、withFilterのほうは、*1本質的にfilterと同じなので、これ以降はwithFilterとfilterの違いは考えないことにします。*2


Scalaのfor式でfilterが使われるのは、以下の2通りあります

  1. for式内でパターマッチをしたとき
  2. for式内で、ifを使った場合

for式内でパターンマッチとは、たとえば以下のようなコードです

for{
  Some(a) <- List(Some(1), None)
} yield a

これは、だいたい以下のように展開されます*3

List(Some(1), None).withFilter{
  case Some(a) => true
  case _ => false
}.map{
  case Some(a) => a
}

2の「ifを使った場合」というのは、以下のようなコードが

for{
  a <- List(Some(1), None)
  if a.isDefined
}yield a

こんな感じに変換されます

List(Some(1), None).withFilter(_.isDefined).map(a => a)

さて、ここで結論から先に言うと、filterはMonadとは関係ないという話です。たとえば、filterもwithFilterも定義されていない、MyOptionやMyListのデータ型を適当に作って、それをMonad則を満たすように定義することは可能です。


そしてfilterは、Monadではなく、MonadPlusに対応します!*4



この後、まだまだ言いたいことがたくさんあって、どこから説明すればいいのか悩むのですが、一旦Haskellのdoを見てみましょう。

Scalaのfor式内でのif」に対応するものが、Haskellでは「guardという関数」です。たとえば、先程の例をHaskellに訳すと以下のようになります

import Control.Monad
import Data.Maybe 

do
  a <- [Just 1, Nothing]
  guard(isJust a)
  return a

まず「Haskellのguard」と「Scalaのfor式内のif」で重要な違いがあります。Haskellの場合

  • guardは「doの中で使える特殊な構文ではなく*5単なる関数である」
  • guardを使うには「MonadPlusのインスタンスであることを要求する」

一方Scala

  • 「for式内のifは特別な構文である」
  • 「for式内のif」を使うためには、filterが実装されていることが必須

となっています。Haskellのguardについては、以下のページとか見てください
guard の動作原理を考える


なぜ「for式内のif」が特別な構文として実装されたのか?は、odersky先生に聞くか、調べてみないとわかりません。勝手な予想としては、型推論などの関係から、「構文として実装」してしまったほうが、使いやすくなって都合がよかったのだろうと思います。

たとえば、以下のように(明らかに使いづらいですが)、ifをguard関数として実装するのは不可能ではないです

型クラスでHaskellのguardを定義してみる(未完)



続いて、「for式内でのパターンマッチ」が、Haskellの場合どうなるのか見てみます。
Haskellでは、

  • どんなものでもdoの中でパターンマッチできるが、パターンマッチに失敗した場合にMonadのfail関数*6が呼ばれる

という仕様になっています。


一方Scalaの場合は

  • filterを実装していないと、forでパターンマッチができない(やろうとしても、そもそもコンパイルエラーになる)

という仕様です。
Monadのfail関数を実装しない場合はデフォルトでは例外を投げるので、この点においてはある意味Scalaのほうが型安全といえるかもしれまん。
ただし、適切にfailを定義できればHaskellにおいても安全でしょうけれども。



そして、その「適切にfailを定義」が重要なポイントです。
(あまり多く調べたわけではないので自信がないのですが)
Monadのfail関数を適切に定義」とは
「もしもMonadPlusならば、failでmzeroを返すように定義するべきではないか?」
ということです。たとえば実際に、ListのMonadのfailではNilを返しているし、MaybeではNothingを返しています。
このあたり、(Haskellの一般的な慣習として?)failをどのように定義するのか、Haskell詳しい人教えてくれるとありがたいです。もしくは、「そもそもdoでのパターンマッチは失敗する可能性あって安全じゃないからあまり使わないよ!」とか


やっとMonadPlusの話に戻ってこれて、
"MonadPlusと「Scalaのfor式内でのif」と「for式内でのパターンマッチ」がなんとなく関連する"
ことがわかってきました。*7


ここでまた話が飛びますが、たとえばScalazにおいて、filterがMonadPlusの関数として定義されています。*8

https://github.com/scalaz/scalaz/blob/v7.0.0/core/src/main/scala/scalaz/MonadPlus.scala#L16

Scalazのfilterの定義をみてもらうとわかるとおもいますが、filterを定義するには、bindとmzero両方が必要なので、MonadではなくMonadPlusでなければいけまん。



ここからやっと確信というか、本当に言いたいことに迫ってきますが、
「では、MonadPlusにならない場合に、filterをどうするか?」
ということです。
例えば、通常EitherはMonadPlusにはなりません!
*9

だがそれにも関わらず、Scala標準のEither*10には、以下のようなfilterが定義されています
https://github.com/scala/scala/blob/v2.10.1/src/library/scala/util/Either.scala#L391

def filter[Y](p: A => Boolean): Option[Either[A, Y]]

このfilterが使いづらいと思ったことはありませんか?
まず、シグネチャがおかしいですよね?Option[A]をfilterした場合には、Option[A]型が再び返ってきますが、Either*11をfilterすると、Option[ Either[A, Y] ]と、Optionに包まれて返ってきます。*12

随分長い間
Scala標準のEitherのfilter使いづらいなー。(特にfor式でパターンマッチやifを使う場合) でも、じゃあどのように定義するのが適切なのだろう」
という疑問がありました。それで


「filter関数をfor式内で使うためのものとして捉えた場合に、filterはMonadPlusと関連しているので、MonadPlusのlawを満たすように定義するべき」
という立場にたつと
「EitherはMonadPlusになること自体が不可能なので、適切な使いやすいfilterを定義することもそもそも不可能」
という結論に達しました。*13



ただ、これで終わりではなくて、まだ話が続きます。本当に
「filterはMonadPlusと関連しているので、MonadPlusのlawを満たすように定義するべき」
という点が、必ずしも絶対的な条件ではなく、議論が分かれるところだからです。
たとえば、scala標準のscala.util.Tryや、ScalazのValidationなども、MonadPlusの条件は満たしませんが、filterメソッドが存在しています。*14
そして、ScalazのEitherのfilterもMonadPlusの条件を満たさないのですが、以下のように面白い定義になっていて、for式内で(少なくともScala標準のEitherのfilterよりは)ある意味便利に使えるようになっています。*15

https://github.com/scalaz/scalaz/blob/v7.0.0/core/src/main/scala/scalaz/Either.scala#L122

def filter[AA >: A](p: B => Boolean)(implicit M: Monoid[AA]): (AA \/ B)

Scalazの場合、Scala標準のものとは違い、filterした後の型がOptionに包まれているのではなく、(ほぼ)同じ型を返すようになっています。



MonadPlusを満たさなくても*16、for式で便利に使えるので、これを許容するのかどうかが、意見が分かれるところだと思います。


そして、ScalazのMLで、EitherではなくEitherTですが、filterとwithFilterの定義について議論になっていました


EitherT.filter and filterWith are evil, stupid, and wrong.


個人的には、EitherTのfilterはこのまま存在してもいい気もしますが、果たしてどうなるんでしょうか。



というわけで、だいぶ長くなりましたが、「HaskellのdoとScalaのfor式とEitherとMonadPlus」の関係について説明してみました。

*1:主にパフォーマンスの関係から導入されただけで

*2:withFilterに変換される場合も、たんにfilterと言ったりします

*3:-Xprint:typerとかで出力してみると、たぶん細かいところ違いますが、議論の本質に関係ないので省略して書きました。気にしないでください

*4:対応しますと完全に言い切ると語弊があるのですが。そもそもこのあたりが、今回最終的に言いたいところなので

*5:doの中以外でも使える

*6: http://www.haskell.org/ghc/docs/latest/html/libraries/base/Control-Monad.html#t:Monad

*7:微妙に話の流れが強引な気がするが・・・説明難しい・・・

*8:この関数の名前がfilterなのは、for式で使うことを意図しているはずです

*9:ものすごく無理やりな定義をすれば、不可能ではないかもしれませんが、そんな定義をしたとしても、有用な定義になはならなくて使えないでしょう

*10:のRightProjectionもしくはLeftProjection

*11:のRightProjectionもしくはLeftProjection

*12:それに微妙に関連する話として、HaskellMonadのfail関数も、同じ型を返さなければいけないように制限されています

*13:たとえばHaskellのEitherもMonadPlusにはならないので「Monadのfail関数の適切な定義」が意見が分かれる?ので、そもそも定義されていません。Eitherに対してdoの中でパターンマッチに失敗すると例外が発生します

*14:他には、json4s(lift-json)のfilterもたしかそうだったはずです。

*15: Scala2.10.1がバグってるのか、こんな現象が起きますが https://twitter.com/xuwei_k/status/335480823438528513

*16:implicit に Monoidを引数にとったからといって、どちらにしろScalazもMonadPlusのlawは満たさない