2012年6月15日金曜日

Scala Tips / Validation (30) - foldまとめ

Validationの集りに対して処理を行うためのイディオムを見てきました。内容が多岐に渡るため、まとめておきます。

ユースケース

多重度の表現」から「Validation (20) - Personの実装」まで、以下のエントリでValidationの具体的なユースケースであるオブジェクト生成時の検証を考えました。

この中で「多重度0または1の部品」はOption[Validation[A]]、「多重度0以上の部品」と「多重度1以上の部品」はList[Validation[A]]やNonEmptyList[Validation[A]]といったValidationの集りの捌き方が重要なテーマとなっています。

型パラメータ問題

Validationの特殊事情としては、型パラメータ数が2になるので、ScalaやScalazが用意している機能に対して適用する場合に不整合を起こすという問題があります。この対処方法は「Validation (21) - traverse」で説明しました。

Validationに限らず、アプリケーションがモナドの文脈にアプリケーションの状態を直接保持しておけるモナド(WriterやLoggerなど)は型パラメータが2つ(以上)になるので、割と普通に出てくる形でもあります。Monadicプログラミングをする以上は必須のテクニックといえます。

捌き方

「多重度0以上の部品」や「多重度1以上の部品」を捌く上で、Validationの集りに対して一括して処理を行う必要性が出てきました。つまり、List[Validation[A]]の形の捌き方ですね。これは、以下の3つの形に還元することができます。

  • GenTraversableOnce[Applicative[A]]
  • Foldable[Applicative[A]]
  • Traverse[Applicative[A]]

GenTraversableOnceはScalaのコレクションクラスでListやStreamなど大元です。TraverseとFoldableはScalazの型クラスです。

GenTraversableOnceではScalaのfold系メソッド、FoldableではScalazのfold系メソッド、Traverseではtraverseメソッドsequenceメソッドを説明しました。

sequenceとtraverse

Validationに限らず、MonadicプログラミングではM[N[A]]→N[M[A]]やM[A]→N[M[B]]の変換処理が頻出するのでsequenceメソッドやtraverseメソッドは必須メソッドといえます。

Validation (29) - Foldable」で説明したように、sequenceメソッドを用いてFoldable[Validation[A]]→Validation[Foldable[A]]の形にした後、Foldable[A]に対してfold系の処理を適用してValidation[B]を得るという捌き方がイディオムとなっています。

ただし「Validation (26) - fold monoid or」や「Validation (27) - fold or」で説明したように、Monad/Applicativeが提供するジョイン演算による計算文脈結合が処理目的とあっていない場合には、foldRightメソッドなどのfold系メソッドとmatch式を組合わせてロジックを組む必要があります。このため、fold系メソッドでValidationを捌く方法も押さえておく必要があります。

左畳込みと右畳込み

使用するデータ構造と畳み込みの方向は性能上の相性があるので注意が必要です。

Scalaの最重要永続データ構造であるListの畳込みに関しては、「Validation (28) - fold List」で考察しました。

また、より汎用的なSeqやMonoidも含めた総合的な検討を「foldの選択」で行いました。基本的にはList、Seq、Monoidのいずれも右畳込みを基本に考えていけばよいというのが結論でした。

Validationの場合、List[Validation[A]]をValidation[List[A]]の形にするユースケースが頻出しますが、これはsequenceメソッドやtraverseメソッドを使うのがよさそうということが分かりました。「foldの選択」では、sequence/traverseメソッドが(reverse+foldLeftで事実上の)右畳込みを行っており、Listに対する畳込みを高速に実行できることも確認しました。

Monoid

fold系メソッドによる畳込みとMonoidの相性が良いことを説明しました。畳込み処理は何かの集りを足しこんでいく処理なので、何かの集りと何かと何かの足し込み演算を抽象化したMonoidを使えば、事前に定義されたパラメタを用いて自動的に処理できる部分が増えるからです。

Validation (25) - fold monoid」のsumrメソッドや「Validation (26) - fold monoid or」の「>>*<<」メソッドなどがよい例ですね。「Validation (29) - Foldable」で紹介したFoldable系のメソッドも多くはMonoidが対象になっています。

Monoidは畳込みに限らず色々なところに登場する鍵となる型クラスです。

諸元

  • Scala 2.9.2
  • Scalaz 6.0.4

0 件のコメント:

コメントを投稿