Scala Tips / Validation (23) - fold

関数型プログラミングといえば、今も昔もfold関数による畳込みがひとつの鍵になります。Scalaでは、scala.collection.GenTraversableOnceにfoldメソッド、foldLeftメソッド、foldRightメソッドが定義されており、ListやStream、Mapなど、すべてのコレクションクラスで提供されている基本メソッドとなっています。また、Scalazでは型クラスFoldableがfold系のメソッドを提供しています。

今回はValidationに対してfold系メソッドを適用するイディオムについて見ていきます。つまり、複数のValidationを格納したListなどのコレクション上で、Validationを畳み込む方法ですね。

fold系の関数も用途別に色々なバリエーションがあります。今回はScala本体が提供しているfold系メソッドです。

課題

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

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

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

今回は、Scala本体が提供するfold系のメソッドであるfoldLeftメソッド、foldRightメソッド、foldメソッドを使用します。なお、fold系メソッド以外は必要に応じてScalazの機能を用います。

基本形

ListのfoldLeftメソッドを使うと以下のようになります。

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

ポイントは以下の2つです。

• 初期値の指定方法
• 計算方法

初期値

fold系関数を使う場合のポイントの一つは初期値の指定方法です。

ここでは「0.successNel[Throwable]」としました。

以下のように「Success(0)[NonEmptyList[Throwable]]」とする方法もありますが、かなり冗長になるので、専用メソッドsuccessNelを使うのがイディオムです。

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

計算方法

Scalazでは、モナドの集りに対して演算を適用する場合にはApplicativeの機能を使うのが常道です。

ここでは、以下のようにApplicativeを用いて、引数aとxに束縛された2つのValidationの内容を加算しています。

• (a |@| x)(＿ + ＿)

アプリケーションロジックである「2つのIntの加算」のみを記述しておけば、ValidationがFailureだった場合の処理を含むValidationの合成はApplicative演算側で自動的に行ってくれます。

foldLeftメソッドでApplicativeを用いて「2つのIntの加算」を畳み込んでいくことで、List上のすべてのValidationの値を畳み込んで一つのValidation上に集約します。

Scalazを使わない場合

それでは、Scala本体にのみで処理を行う場合についてはどうなるでしょうか。

Validation自体がScalazのオブジェクトなので、完全にScalazを排除したコードではありませんが、Scala本体でモナドに対してfoldLeftを行う時は以下のようになります。

まず分かりやすいのがfor式を使う方法です。複数のモナドを同時に扱う場合は、大体for式を使っておくと間違いがありません。

def f(a: List[ValidationNEL[Throwable, Int]]): ValidationNEL[Throwable, Int] = {
  a.foldLeft(0.successNel[Throwable]) {
    (a, x) => for (a0 <- a; x0 <- x) yield a0 + x0
  }
}

構文糖衣であるfor式を使わずスクラッチで書くと以下のようになります。

def f(a: List[ValidationNEL[Throwable, Int]]): ValidationNEL[Throwable, Int] = {
  a.foldLeft(0.successNel[Throwable]) {
    (a, x) => a.flatMap {
      a0 => x.map {
        x0 => a0 + x0
      }
    }
  }
}

記述が煩雑になるのに加えて、ロジックを書くときに若干ではありますが頭を使うのでその分本来やりたいことのロジックに集中できないというデメリットもあります。

for式を使うと、定形の文法にロジックを流しこむだけなので、そういった負担が大幅に軽減されます。そういった意味で、一般的には「複数のモナドを同時に扱う場合はfor式」という戦略で望むとよいでしょう。

もちろん、Scalazの場合には「複数のモナドを同時に扱う場合はApplicative」という戦略も加わります。この場合は、Applicativeを主にして、Applicativeで簡単にいかない場合にはfor式を使う、という戦略がよいと思います。

pureを使う

foldLeftの初期値に「0.successNel[Throwable]」を使いましたが、これも若干冗長な感じがします。

Scalazでは、モナドを生成する演算であるunit演算を実現するための型クラスPureを用意しています。この型クラスPureを用いてみましょう。

その前準備として以下の型VNTを定義します。これは、型クラスPureが型パラメータ数1のオブジェクトを演算対象にしているので、型パラメータ数を合わせるためです。

• type VNT[A] = Validation[NonEmptyList[Throwable], A]

型VNTと型クラスPureを使って初期値を設定すると以下のようになります。

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

「0.pure[VNT]」とすると、0をVNTの成功側であるSuccess[NonEmptyList[Throwable], Int]に格納したオブジェクト、すなわち「Success(0)[NonEmptyList[Throwable]]」が返されます。

型クラスPureを用いてモナドを生成する方法は、汎用的でもあり使い方も簡単で記述もシンプルなので、積極的に使っていくようにするとよいでしょう。

以下では型クラスPureを用いる方法を採用します。

fold3種

ScalaのListが提供するfold系のメソッドは以下の3つです。

メソッド	畳み込み結果の型	評価順序	エイリアス
fold	元のスーパークラス	任意	/:\ |
foldLeft	任意	左から右	/: |
foldRight	任意	右から左	:\

基本的には、評価順序が「任意」、「左から右」、「右から左」の違いになります。

foldメソッドの「任意」というのは、並列プログラミングなどの環境では最適化のために任意の順番で実行した結果を連結したものを結果として返してよいという意味で、入力の並びと出力の並びが一致しない可能性があります。つまり、入力の並びと出力の並びを一致させたい場合には使ってはいけないメソッドということになります。通常の実装ではfoldLeftメソッドを呼び出すだけになっていますが、この実装に依存しては危険です。このため、通常はfoldLeftメソッドまたはfoldRightメソッドを使います。

foldLeftメソッドとfoldRightメソッドの違いは評価順序のみです。プログラマの直感としてはfoldLeftつまり先頭から順に評価して後ろに連結していく方が素直なので、ここではfoldLeftを最初の実装にしています。

foldRightメソッドは、最後尾から順に評価して前に連結していくので、あまり直感的とはいえませんが、いわゆる永続データ構造と相性のよい評価方法で、関数型プログラミングではこちらを使う方が熟(こな)れた使い方といえます。

直感とは違いますが、関数型プログラミング的にはfoldRightを主に考えるのが筋がよいということなので、まずfoldRightで実装できるか考えてみて、foldLeftでないと難しい場合にfoldLeftを採用するというプログラミング戦略がよいと思います。

なお、今回のIntの加算のように、左から評価しても右から評価しても結果が変わらないものはfoldLeftメソッドとfoldRightメソッドのどちらを使ってもかまいません。このケースではfoldメソッドの非決定的な動作も問題がないので、最適化に期待してfoldメソッドを使う選択もあります。

この中でfoldLeftメソッドはすでに使いました。残りはfoldRightメソッドとfoldメソッドです。

foldRightを使うと以下になります。

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

foldを使うと以下になります。

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

エイリアス

foldメソッド、foldLeftメソッド、foldRightメソッドはそれぞれ文法糖衣のエイリアス・メソッド「:\」、「:」、「:\」を持っています。

使い方は以下の通りです。

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

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

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

文法糖衣の割にあまり書きやすく/見やすくなったように感じないのでボクはあまり使いませんが、読めるようになっておく必要はあります。

Scalaz

Scalazはさまざまなfold系メソッドを提供しています。また、型クラスFoldableの導入で、scala.collection.GenTraversableOnceでないオブジェクトにも畳込み演算を適用することができるようになっています。

次回はScalazの用意するfold系メソッドを見ていきます。

ノート

関数型プログラミングの鍵になる最重要関数を3つ挙げるとすると:

• map
• fold
• bind

といっても過言ではないと思います。

Scalaでは、それぞれ以下のメソッドになります。

• map
• fold, foldLeft, foldRight
• flatMap

bind(flatMap)はモナド導入以降の関数ですから、伝統的な関数型プログラミングの時代はmapとfold(fold, foldLeft, foldRight)の2つが最重要関数だったことになります。

Scalaが提供する3種類のfold系メソッドfold, foldLeft, foldRightの中で永続データ構造であるListと相性のよいfoldRightメソッドが、この中では一番重要度が高いと思うので、fold系メソッドの中であえて一つ選ぶとするとfoldRightが最重要メソッドといってもよいでしょう。

MapReduce

reduceはfoldの特殊な形なので、Hadoopの技術的な基盤となったMapReduceが、関数型プログラミングの2大関数mapとfoldの組合せに近しい名前になっているのは、この2つの関数による処理が本質的に重要ということを表していると思えます。

逆になぜfoldではなくreduceだったのかということを考えていくと、分散処理上の最適化の問題に行き当たるかもしれません。

さらに、現代の関数型プログラミングの最重要関数になったbindも、いずれ分散処理基盤上のコアセマンティクスに入ってくるのかも、と考えていくと夢が広がりますね。データフローをKleisliカテゴリの射の合成として記述すると、継続計算や並列計算で色々な技が使えそうなので、実際にそういう方向に進むかもしれません。

そうなってくるとScalaのようなモナドを標準装備した関数型言語でないと、実用上はデータフローの処理を記述するのは難しくなってくるでしょう。

ValidationNEL[Throwable, List[Int]]の場合

本文ではList[ValidationNEL[Throwable, Int]]をValidationNEL[Throwable, Int]に畳み込む方法について説明しました。

それでは、ValidationNEL[Throwable, List[Int]]をValidationNEL[Throwable, Int]に畳み込む場合はどうなるでしょうか。

これは簡単で、ValidationNELの文脈上で、List[Int]をIntに畳み込めばよいわけです。

この場合、普通にmapメソッドでValidationNELの文脈上で畳込みを行う関数を動作させればOKです。

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

Intを加算で畳み込むときはsumメソッドが使えます。sumメソッドを使うと以下になります。

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

諸元

• Scala 2.9.2
• Scalaz 6.0.4