Scala Tips / Validation (25) - fold monoid

モノイドは代数的構造の一つですが、プログラミング的には以下の性質を持つオブジェクトということになります。

• 加算(的な)演算を持っている。同じ型同士のオブジェクトを加算(的な演算を)して同じ型のオブジェクトが得られる。
• 加算(的な演算の)結果が変わらない初期値的なオブジェクトを持っている。

演算子「+」で加算できるInt型やString型は代表的なモノイドです。初期値的なオブジェクトはそれぞれ「0」、「""」となります。

JavaやScalaではモノイドの性質は暗黙的に使われていたものの、言語機能によるサポートがなかったので、ケースバイケースのアドホックな利用になっていました。

Scalazでは型クラスMonoidで、このモノイドを直接プログラミングの基本機能として使用できるようにしています。

Monoidとfold

型クラスMonoidの存在が重要なのは、Monoidに対する共通処理を記述することができるからです。その典型例が型クラスFoldableです。FoldableではMonoidに対する機能を多数提供しており、IntやStringに限らず、アプリケーションの定義するオブジェクトも含めてMonoidであれば等しくこれらの共通処理を使用することができます。

畳込みを行うfold関数は以下の理由によりモノイドとの相性が大変よくなっています。

• 畳込みの初期値をモノイドの定義から取得できるので関数のパラメタとして与えなくてよい。
• 畳込み関数として加算的な演算を使う場合は畳込み演算そのものをパラメタとして与えなくてよい。

つまり、処理対象をMonoidに限定できれば、fold関数の2つの引数(1)初期値と(2)畳込み関数の両方を省略したり、デフォルトの設定として使用したりすることができるわけです。

その典型例がFoldableが提供するsumrメソッドです。sumrメソッドは(1)初期値と(2)畳込み関数の指定なしにMonoidの集りを加算畳込みします。

まず、ScalaのListが提供するsumメソッドの動きを見てみましょう。IntのListについては以下のように動作します。

scala> List(1, 2, 3).sum
res13: Int = 6

しかしStringのListの場合は以下のようにエラーになってしまいます。ListのsumメソッドはNumeric型しか受け付けないのですね。

scala> List("1", "2", "3").sum
<console>:14: error: could not find implicit value for parameter num: Numeric[java.lang.String]
              List("1", "2", "3").sum
                                  ^

次はMonoidを対象にしたScalazのsumrメソッドです。Int型は当然動作します。

scala> List(1, 2, 3).sumr
res10: Int = 6

さらにString型も文字列の加算の畳込みとしてきちんと動作しました。

scala> List("1", "2", "3").sumr
res11: java.lang.String = 123

sumrメソッドの内部では、String型の初期値「""」とString型の加法演算子「+」が自動的に使用されており、プログラマが外部からパラメタとして与えなくても良いようになっています。

課題

Monoid型の値を格納したValidationのリスト上で、Monoid型の値をモノイドの加法演算で畳込んで結果の値を格納したValidationを生成します。

具体的には、以下の関数を作ります。

• f[T: Monoid](a: List[ValidationNEL[Throwable, T]): ValidationNEL[Throwable, T]

foldLeft

foldLeftメソッドを使った実装です。

Monoidの加算演算は演算子「|+|」を使用します。また、Monoid Tの初期値は「mzero[T]」で取得することができます。mzero関数は零元を通知する関数で、Monoidの場合は単位元すなわち「加算(的な演算の)結果が変わらない初期値的なオブジェクト」を返します。Int型の場合は「0」、String型の場合は「""」が返ります。

successNel版は以下になります。

def f[T: Monoid](a: List[ValidationNEL[Throwable, T]]): ValidationNEL[Throwable, T] = {
  a.foldLeft(mzero[T].successNel[Throwable]) {
    (a, x) => (a |@| x)(_ |+| _)
  }
}

pure版は以下になります。

def f[T: Monoid](a: List[ValidationNEL[Throwable, T]]): ValidationNEL[Throwable, T] = {
  type VNT[A] = ValidationNEL[Throwable, A]
  a.foldLeft(mzero[T].pure[VNT]) {
    (a, x) => (a |@| x)(_ |+| _)
  }
}

foldRightを使っても同じように実装できます。foldlメソッド、foldrメソッドも同様ですね。

sequence

Validationの集りを畳み込む場合には、Validationに対して直接fold系メソッドを適用するより、sequenceメソッドを使って得られた要素の集りに対してfold系メソッドを適用した方が便利であることを前回紹介しました。

sequenceメソッドで、List[T]の形にする方法を採用すると、Monoidに対してFoldableのsumメソッドとsumrメソッドが使えます。

sumメソッドは左から右の方向に加算の畳込み、sumrメソッドは右から左の方向に加算の畳込みを行います。

まずsumrメソッドは以下になります。

def f[T: Monoid](a: List[ValidationNEL[Throwable, T]]): ValidationNEL[Throwable, T] = {
  type VNT[A] = ValidationNEL[Throwable, A]
  a.sequence[VNT, T].map(_.sumr)
}

sumメソッドは、Listのsumメソッドと名前がバッティングするのでそのまま指定すると前述したように文法エラーになってしまいます。asMAメソッドを使って、ScalazのMAオブジェクトを表に出した上でsumメソッドを使います。

def f[T: Monoid](a: List[ValidationNEL[Throwable, T]]): ValidationNEL[Throwable, T] = {
  type VNT[A] = ValidationNEL[Throwable, A]
  a.sequence[VNT, T].map(_.asMA.sum)
}

foldMapとfoldMapDefault

Monoidに対するfold処理のためのメソッドとしてfoldMapメソッドとfoldMapDefaultメソッドが提供されています。

foldMapメソッドとfoldMapDefaultメソッドは、同じ動きをするメソッドですが、適用対象が違っていて、前者がFoldable、後者がTraverseになります。

foldMap/foldMapDefaultメソッドは「Foldable/Traverse上のMonoidでない要素の集りをMonoidへ変換後、Monoidの加算演算で畳込み」を行います。ひとことで言うと以下の処理です。

• (FoldableまたはTraverse).map(Monoidへ変換).sumr

課題をfoldMapで実装すると以下になります。もともとMonoidなのでidentity関数を用います。このような場合は本来はfoldMapメソッドではなく前述のsum/sumrメソッドを使います。

def f[T: Monoid](a: List[ValidationNEL[Throwable, T]]): ValidationNEL[Throwable, T] = {
  type VNT[A] = ValidationNEL[Throwable, A]
  a.sequence[VNT, T].map(_.foldMap(identity))
}

課題をfoldMapDefaultで実装すると以下になります。

def f[T: Monoid](a: List[ValidationNEL[Throwable, T]]): ValidationNEL[Throwable, T] = {
  type VNT[A] = ValidationNEL[Throwable, A]
  a.sequence[VNT, T].map(_.foldMapDefault(identity))
}

Traverseの場合は、Foldableのsum/sumrに相当するメソッドとしてcollapseを提供しています。collapseメソッドを使うと以下になります。

def f[T: Monoid](a: List[ValidationNEL[Throwable, T]]): ValidationNEL[Throwable, T] = {
  type VNT[A] = ValidationNEL[Throwable, A]
  a.sequence[VNT, T].map(_.collapse)
}

ノート

ListやOptionなど、コンテナ系のオブジェクトはだいたいFoldableとTraverseの両方の対象になっているので、fold系メソッドの利用はFoldableが提供するメソッドを主体に考えていけばよいでしょう。つまりfoldMapDefaultcollapseよりfoldMapsumr/sum、ということですね。foldMapsumrsumが使えないときに、foldMapDefault/collapseを試してみるというアプローチでよいと思います。

諸元

• Scala 2.9.2
• Scalaz 6.0.4