Scala Tips / Validation (24) - fold scalaz

Scalaでは、scala.collection.GenTraversableOnceに定義されているfoldメソッド、foldLeftメソッド、foldRightメソッドが、ListやStream、Mapなど、すべてのコレクションクラスで提供されている基本メソッドとなっています。

一方、Scalazでは型クラスFoldableがfold系のメソッドを提供しています。

前回はScala本体のfold系メソッドについて説明しました。今回はScalazのfold系メソッドについてみていきます。

課題

Int型の値を格納したValidationのリスト上で、Int型の値を加算で畳込んで結果の値を格納したValidationを生成します。

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

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

基本形

foldLeftメソッドに対応するのがfoldlメソッドです。foldlメソッドは基本的にはfoldLeftと同じ動作します。

畳込みの計算方法は「Validation (23) - fold」でも説明したとおりApplicativeを使うのがScalazでの常道となります。場合によってfor式やflatMapメソッドを直接使ったスクラッチでの記述を併用します。

初期値にsuccessNelを使う場合は以下になります。

def f(a: List[ValidationNEL[Throwable, Int]]): ValidationNEL[Throwable, Int] = {
  a.foldl(0.successNel[Throwable]) {
    (a, x) => (a |@| x)(_ + _)
  }
}

初期値にpureを使う場合は以下になります。

def f(a: List[ValidationNEL[Throwable, Int]]): ValidationNEL[Throwable, Int] = {
  type VNT[A] = ValidationNEL[Throwable, A]
  a.foldl(0.pure[VNT]) {
    (a, x) => (a |@| x)(_ + _)
  }
}

以下では初期値にpureを使うのを基本にします。

foldLeftとfoldlの違い

foldLeftメソッドとfoldlメソッドの違いは適用対象のコンテナです。foldLeftメソッドはListやStreamなどscala.collection.GenTraversableOnceのサブクラスが対象になります。一方foldlメソッドは型クラスFoldableの対象となる(型クラスインスタンスを持っている)オブジェクトが対象になります。

ListやStreamといったコレクションクラスは通常Foldableでもあるので、一般的にはfoldLeftメソッドとfoldlメソッドのどちらも使用することができます。どちらを選択してもよいのですが、foldLeftメソッドの方が基本機能なので、foldLeftメソッドが使える場合はfoldLeftメソッド、そうでない場合はfoldlメソッドを使うようにするのも一案です。

foldr

foldRightメソッドに対応するのがfoldrメソッドです。使い方に違いはありません。

def f(a: List[ValidationNEL[Throwable, Int]]): ValidationNEL[Throwable, Int] = {
  type VNT[A] = ValidationNEL[Throwable, A]
  a.foldr(0.pure[VNT]) {
    (x, a) => (a |@| x)(_ + _)
  }
}

foldl1

Scalazでは、ScalaのfoldLeftメソッド、foldRightメソッドに対応するfoldlメソッド、foldrメソッドに加えて、いくつかのfold系のメソッドが提供されています。

foldl1メソッドは、初期値を外部から指定せずFoldable内の要素のみを畳込みます。Foldableの先頭要素が初期値となるfoldlと考えることができます。このことによって以下の2つの制約が出てきます。

• 空リストの場合畳込みができない。このことを表現するために返却値の型がOptionになっている。
• 畳込みの結果の型が要素の型と同じになる。

つまり、M[A]→Option[A]の変換(MはFoldable)をするメソッドということになります。foldLeftやfoldlはM[A]→Bの変換、つまり元の「コンテナ+要素の集り」を全く別物に変換するのに対して、foldl1は要素に対するモノイド的(演算結果の型が閉じている)な畳込み演算＋空要素判定をするので、見かけは似ていますがユースケースはかなり変わってきそうです。

今回の課題で使ってみましょう。

初期値にsuccessNelを使う場合は以下になります。

def f(a: List[ValidationNEL[Throwable, Int]]): ValidationNEL[Throwable, Int] = {
  a.foldl1 {
    (a, x) => (a |@| x)(_ + _)
  } | 0.successNel
}

初期値にpureを使う場合は以下になります。

def f(a: List[ValidationNEL[Throwable, Int]]): ValidationNEL[Throwable, Int] = {
  type VNT[A] = ValidationNEL[Throwable, A]
  a.foldl1 {
    (a, x) => (a |@| x)(_ + _)
  } | 0.pure[VNT]
}

Foldable(この場合はList)が空の場合には処理を行うことができないことを表すためにOptionを返すしますが、このことによってSomeとNoneで初期値を切り分け、Noneの場合にはデフォルト値を返す処理が必要になります。このため今回のケースではfoldl1は思ったほど便利ではありません。

Optionを使って空リストを特別にハンドリングしたいケースでは有効なので、そういう場合になにかよいユースケースはあるかもしれません。

foldr1

foldr1メソッドはfoldl1メソッドのfoldRight版です。

def f(a: List[ValidationNEL[Throwable, Int]]): ValidationNEL[Throwable, Int] = {
  type VNT[A] = ValidationNEL[Throwable, A]
  a.foldr1 {
    (x, a) => (a |@| x)(_ + _)
  } | 0.pure[VNT]
}

foldLeftM/foldRightM

Scalazのfoldlメソッド、foldrメソッドは、Scala本体のfoldLeftメソッド、foldRightメソッドと基本的に同じものなので、これだけだと、特に便利になったというわけではありません。Scalaのコレクションクラス以外の任意のオブジェクトに対して、型クラスFoldableを適用(型クラスFoldableの型クラスインスタンスを定義)して、foldl/foldrメソッドを追加できるというのが直接のメリットですが、これはかなりレアなユースケースです。

そこで重要になってくるのが、foldl/foldrメソッド以外のfold系メソッドです。前述のfoldl1/foldr1メソッドはそれほど便利ではありませんでしたが、Monadを対象にしたfoldLeftM/foldRightMはかなり便利そうです。

動作確認

foldLeftMメソッドは:

def foldLeftM[N[_], B](b: B)(f: (B, A) => N[B])(implicit fr: Foldable[M], m: Monad[N]): N[B]

のシグメチャを持ちますが、要するに「M[A]→N[B]」の畳込みを行います。通常のfoldLeftは「M[A]→B」の畳込みを行うので、通常のfoldLeftをした後モナドNに持ち上げるという処理を行ったのと同じ結果になります。ただし、以下の特徴を持ちます。

• 持ち上げる対象のモナドNは、畳込み関数「(B, A) => N[B]」で指定する。
• 畳込みの中でモナドNのジョイン演算が自動的に行われる。

このあたりの処理はmapメソッドとtraverseメソッドの関係に似ています。

ListとSomeを使って具体的な振舞いを確認してみましょう。

scala> List(1, 2, 3).foldLeftM(0)((a, x) => (a + x).some)
res28: Option[Int] = Some(6)

Listは畳込みの結果なくなり、畳込み関数「(a, x) => (a + x).some」で指定したOptionが畳込み結果のIntを包む形になっています。

この形で注目したいのは初期値が「0」とできる点です。foldLeftでモナドを畳込む場合、初期値は「0.some」や「Some(0)」、「0.successNel[Throwable]」や「0.pure[VNT]」といった形になるのでなかなか大変でした。foldLeftMを使う事によって、この問題を回避できるのは大きなアドバンテージです。

文脈を変える

畳込み関数がモナドを返すようになっているということは、モナドの計算文脈を変えることができると言うことを意味します。この計算文脈の変更は、畳込み関数から返されたモナドと元の計算文脈のモナドをジョイン演算でまとめる処理の中で自動的に行われます。

それでは試してみましょう。要素が0以上ならSome、0未満ならNoneを返す畳込み関数「(a, x) => (x >= 0).option(a + x)」を指定すると以下のようになります。

scala> List(1, 2, 3).foldLeftM(0)((a, x) => (x >= 0).option(a + x))
res29: Option[Int] = Some(6)

入力の要素の一つを負の値にすると以下のようになります。

scala> List(1, -1, 3).foldLeftM(0)((a, x) => (x >= 0).option(a + x))
res30: Option[Int] = None

畳込み演算の中で、「-1」に対して畳込み関数がNoneを返すわけですが、この結果計算文脈が失敗の計算文脈に代わり最終結果がNoneになるわけです。このような計算文脈の変更を自動的に行なってくれるのはモナドの威力ですが、モナドを対象とした畳込みメソッドfoldLeftMは、期待通りの処理を行ってくれます。

foldLeftM

課題をfoldLeftMで実現すると以下になります。

def f(a: List[ValidationNEL[Throwable, Int]]): ValidationNEL[Throwable, Int] = {
  import Validation.Monad._
  type VNT[A] = ValidationNEL[Throwable, A]
  a.foldLeftM[VNT, Int](0) {
    (a, x) => x.map(_ + a)
  }
}

初期値を「0.successNel[Throwable]」や「0.pure[VNT]」ではなく「0」にできるのはプログラミング的にかなり便利です。

ただし、ValidationはScalaz Monadではないという問題があります。この問題を回避するために「import Validation.Monad._」としてValidationをScalaz Monad化しています。

また、Validtationの型パラメータ数2問題を回避するために「type VNT[A] = ValidationNEL[Throwable, A]」として型VNTを定義しています。

この2点がValidationをfoldLeftMメソッドで使う場合の注意点になります。

また、畳込み関数は「(a, x) => x.map(_ + a)」となっています。mapメソッドを使ってモナド(この場合はValidation)の文脈上で演算を行うのがこの際のパターンです。

foldRightM

課題をfoldRightMで実現すると以下になります。foldLeftMと同じですね。

def f(a: List[ValidationNEL[Throwable, Int]]): ValidationNEL[Throwable, Int] = {
  import Validation.Monad._
  type VNT[A] = ValidationNEL[Throwable, A]
  a.foldRightM[VNT, Int](0) {
    (x, a) => x.map(a + _)
  }
}

ノート

ScalaのfoldLeft/foldRightメソッドとScalazのfoldl/foldrメソッドを本文では同じ動きをするものとしていますが、実装は異なるので何か微妙な違いはあるかもしれません。この点は留意しておいてください。

またfoldrメソッドに関して言うと、シグネチャが:

• def foldr[B](b: B)(f: (A, => B) => B)(implicit r: Foldable[M]): B

となっており、畳込み関数のシグネチャが「(A, => B) => B」、つまり第2引数がcall-by-nameになっています。

scala.collection.GenTraversableOnceのfoldRightメソッドのシグネチャは:

• def foldRight[B](z: B)(op: (A, B) => B): B

なのでcall-by-nameを使っていません。

foldrメソッドがなぜcall-by-nameを使っているのかボクは理由がわからないのですが、当然何か理由があるものだと思われます。情報頂けるとうれしいです。

sequence

Validationにfold系のメソッドを適用する方法についてScala本体とScalazのそれぞれについて見てきました。

fold系メソッドの使い方の説明としては意義があったと思いますが、実は使っている課題に対してはsequenceメソッドを使う方が簡単に記述できます。

sequenceメソッドで、List[Validation[Throwable, Int]]をValidation[Throwable, List[Int]]に変換した後に、List[Int]に対してfoldLeftメソッドを使って畳込みを行うわけです。Validationの文脈上のList[Int]が対象なのでmapメソッドを用いてValidation上のList[Int]に対する演算を記述します。結果としてValidation[Throwable, Int]が得られます。

def f(a: List[ValidationNEL[Throwable, Int]]): ValidationNEL[Throwable, Int] = {
  type VNT[A] = ValidationNEL[Throwable, A]
  a.sequence[VNT, Int].map(_.foldLeft(0)(_ + _))
}

Intに対する加算の畳込みはsumメソッドを使って直接記述することができます。この場合は次のようにすることができます。

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

sequenceは、単純にM[N[A]]をN[M[A]]にひっくり返すだけですが、ひっくり返すのと同時に値の変換を行いたい場合、つまりM[N[A]]→N[M[B]]をやりたい場合はtraverseメソッドを用います。この後、M[B]に対して畳込みを行うことでN[C]が得られます。

def f(a: List[ValidationNEL[Throwable, Int]]): ValidationNEL[Throwable, Int] = {
  type VNT[A] = ValidationNEL[Throwable, A]
  a.traverse[VNT, Int](_.map(_ + 1)).map(_.sum)
}

Monoid

ScalazのFoldableがらみのメソッドは以下になります。改めてリストアップするとずいぶんありますね。

• listl
• sum
• count
• maximum
• minimum
• longDigits
• digits
• foldl
• foldl1
• foldr
• foldr1
• foldLeftM
• foldRightM
• sumr
• foldMap
• listr
• stream
• asStream
• foldIndex
• any
• all
• empty
• element
• splitWith
• selectSplit
• foldMapDefault
• collapse
• bktree
• foldReduce

この中でfold系メソッドと呼べるのは以下のものです。

• foldl
• foldl1
• foldr
• foldr1
• foldMap
• foldMapDefault
• foldLeftM
• foldRightM
• foldReduce

この中で今回取り上げていないのは以下のものです。

• foldMap
• foldMapDefault
• foldReduce

foldReduceメソッドはValidationでのユースケースが不明なので対象外にしています。

foldMap/foldMapDefaultメソッドは面白そうなのですが、Monoidを対象としているので項を改めることにしました。

畳込みとMonoidは相性が良いのでfoldMap/foldMapDefaultメソッド以外にもFoldable(あるいはTraverse)とMonoidで面白い使い方が色々ありそうです。次回はFoldable＋Monoidをテーマにしたいと思います。

諸元

• Scala 2.9.2
• Scalaz 6.0.4