2012年6月29日金曜日

Scala Tips / Monoid - 新規作成

モノイドは関数型プログラミングで非常に有効な性質です。この性質をプログラムの機能として使えるようにしたものがScalazの型クラスMonoidです。

Scalazが定義する様々なMonoidを活用するのはもちろんですが、アプリケーションのドメインで有用な新たなMonoidを定義して追加していくのもScalaプログラミングの重要な構成要素です。

今回は平均値を示すクラスAverageをMonoid化してみましょう。

Average

まず平均値を示すクラスAverageを定義します。

case class Average(total: Int, count: Int) {
  def +:(a: Int) = Average(total + a, count + 1)
  def :+(a: Int) = Average(total + a, count + 1)
  def +(a: Average) = Average(total + a.total, count + a.count)
  def value: Float = if (count == 0) 0 else total.toFloat / count
}

Averageの動きは以下のとおりです。

scala> val a = Average(0, 0) :+ 3
a: Average = Average(3,1)

scala> a.value
res35: Float = 3.0

scala> val b = a :+ 1
b: Average = Average(4,2)

scala> b.value
res36: Float = 2.0

scala> val c = a + b
c: Average = Average(7,3)

scala> c.value
res37: Float = 2.3333333

Monoid

Scalazの型クラス」のMonoidの項を見ると、型クラスMonoidは型クラスZeroと型クラスSemigroupを継承しています。これは「モノイド」にある"モノイドは単位元をもつ半群(単位的半群)である"という説明と符合するので面白いですね。

ScalazでクラスをMonoid化するには、対象となるクラスに対応する型クラスZeroの型クラスインスタンスと型クラスSemigroupの型クラスインスタンスを定義します。

Scalazの場合は、以下のように型クラスZeroのインスタンスを返す暗黙変換関数と型クラスSemigroupのインスタンスを返す暗黙変換関数を定義します。さらに、暗黙変換をアプリケーションに取り込むためのメカニズムとして、トレイトとオブジェクトの両方を用意します。

case class Average(total: Int, count: Int) {
  def +:(a: Int) = Average(total + a, count + 1)
  def :+(a: Int) = Average(total + a, count + 1)
  def +(a: Average) = Average(total + a.total, count + a.count)
  def value: Float = if (count == 0) 0 else total.toFloat / count
}

trait Averages {
  implicit def AverageZero: Zero[Average] = zero(Average(0, 0))
  implicit def AverageSemigroup: Semigroup[Average] = semigroup((a, b) => a + b)
}

object Averages extends Averages
型クラスMonoid

Monoidを定義する際に、型クラスZeroと型クラスSemigroupのインスタンスを返す暗黙変換関数を定義する方法とは別に、型クラスMonoidのインスタンスを返す暗黙変換関数を定義する方法もあります。その場合は以下のようになります。

case class Average(total: Int, count: Int) {
  def +:(a: Int) = Average(total + a, count + 1)
  def :+(a: Int) = Average(total + a, count + 1)
  def +(a: Average) = Average(total + a.total, count + a.count)
  def value: Float = if (count == 0) 0 else total.toFloat / count
}

trait Averages {
  implicit def AverageMonoid: Monoid[Average] = new Monoid[Average] {
    val zero = Average(0, 0)
    def append(x: Average, y: => Average) = x + y
  }
}

object Averages extends Averages

利用方法

まずimport文でAverageの型クラスインスタンスを有効にします。

scala> import Averages._
import Averages._

mzero関数で単位元を取得することができます。

scala> mzero[Average]
res29: Average = Average(0,0)

演算子|+|で、加算的なモノイド演算を行うことができます。

scala> val a = Average(10, 1) |+| Average(20, 2)
a: Average = Average(30,3)

scala> a.value
res32: Float = 10.0

AverageはMonoidになったので、Monoidに対する便利機能を使うことができます。たとえばListのsumrメソッドを使って、Averageの集約を行うことができます。

scala> val b = List(Average(10, 1), Average(20, 2), Average(30, 3)).sumr
b: Average = Average(60,6)

scala> b.value
res34: Float = 10.0

ノート

Scalazのバージョンは安定版のScalaz 6と新バージョンで開発中のScalaz 7があります。本ブログではボクが開発に使用しているScalaz 6を題材にしていますが、基本的にはScalaz 7でもそれほど影響がなさそうな基本的な項目を中心に調査を進めています。

ただ、今回のテーマである型クラスの新規作成は、Scalaz 6とScalaz 7で仕組みが変わりそうなところなので注意が必要です。Scalaz 7を開発に使うようになったら、Scalaz 7版の定義方法をまとめる予定です。

諸元

  • Scala 2.9.2
  • Scalaz 6.0.4

2012年6月28日木曜日

Scala Tips / Reducer (4) - 自前Reducer

Reducerは、「あるクラス」と「あるクラス」に対する別モノイド演算を定義した「別のクラス」を結びつける演算を行うオブジェクトです。元のクラスである「あるクラス」をC、「追加のモノイド演算」と「あるクラス」を結びつける「別のクラス」をMと表記することにします。

前回では、Cを自作クラスでMonoidでないオブジェクトPerson、MをList[Person]として、ListProducerを使いました。ListProducerは可換モノイドではないモノイドとして有効なので使用してみましたが、実用性という意味では面白い例題ではありません。

今回はもう少し実用的な例として、自前Reducerを使ってモノイド演算を行う方法について説明します。

課題

Personの集まりから平均年齢を計算します。ケースクラスPersonは以下のものとします。前回の例からは属性ageが追加されています。

scala> case class Person(name: String, age: Int)
defined class Person

PersonとPersonの集まりを以下の通り定義します。

scala> val taro = new Person("Taro", 35)
taro: Person = Person(Taro,35)

scala> val hanako = new Person("Hanako", 28)
hanako: Person = Person(Hanako,28)

scala> val saburo = new Person("Saburo", 43)
saburo: Person = Person(Saburo,43)

scala> val persons = List(taro, hanako, saburo)
persons: List[Person] = List(Person(Taro,35), Person(Hanako,28), Person(Saburo,43))

自前Reducerを作る

操作対象のモノイドが決まっていれば自前Reducerを作るのは非常に簡単です。Reducer関数の引数に、CをMに変換する関数を定義すればOKです。

課題の場合、CはPersonになります。MにはIntを使うことにします。Personのageを取り出してIntにマップする関数を使ってReducerを定義すると以下になります。

ala> val s = Reducer((a: Person) => a.age)
s: scalaz.Reducer[Person,Int] = scalaz.Reducers$$anon$3@4fed0b75

ListのfoleReduceメソッドを使って、Reducerに対する畳込みを行って見ましょう。結果は以下の通りです。

scala> persons.foldReduce(implicitly[Foldable[List]], s)
res16: Int = 106

平均を計算

平均を計算する関数avgとして以下のものを作成しました。平均の場合は小数点の値となるのでMとしてFloatを使用します。

def avg[T](a: Seq[T], r: Reducer[T, Float]): Float = {
  a.foldReduce(implicitly[Foldable[Seq]], r) / a.length
}

このavg関数を使った平均年齢の計算は以下になります。PersonのageをFloat値に変換する関数を設定したReducerを作ってavg関数に渡します。

scala> avg(persons, Reducer((a: Person) => a.age.toFloat))
res20: Float = 35.333332

ノート

今回の課題は、以下のようにコーディングするのが普通です。この式を使ってavg関数を作るのも難しい話ではありません。

scala> xs.map(_.age.toFloat).sum / xs.length
res24: Float = 35.333332

そういう意味で、今回解説したReducerを使った実装の直接の利用シーンはなかなか思いつきません。ただ、Reducerを使ってavg関数のような共通処理を記述できることは確かなので、もう一段なにか新しい要因が加われば、便利なメカニズムとして使えそうな感触はあります。

Reducerをターゲットにした関数、IntProductReducerやListReducerなどの各種Reducerが部品として整備されてくれば、Reducerを使う必然性のあるユースケースが見つかるかもしれません。

諸元

  • Scala 2.9.2
  • Scalaz 6.0.4

2012年6月27日水曜日

Scala Tips / Reducer (3) - モノイド化

前前回はIntとIntMultiplicationを結びつけるIntProductRecuder、前回は任意の型TとList[T]を結びつけるListReducerについて説明しました。

Reducerは、「あるクラス」と「あるクラス」に対する別モノイド演算を定義した「別のクラス」を結びつける演算を行うオブジェクトです。元のクラスである「あるクラス」をC、「追加のモノイド演算」と「あるクラス」を結びつける「別のクラス」をMと表記することにします。

IntProductReducerの場合CはInt、MはIntMultiplicationです。またListReducerの場合はCは任意の型T、MはListです。

ここで着目したいのはMはMonoidでなければなりませんが、Cは任意の型でよいという点です。つまりReducerはモノイド演算を持たない任意のクラスに対してモノイド演算を行うためのツールとして使うことができるということです。

例を使って考えてみましょう。

ケースクラスPersonを定義します。

scala> case class Person(name: String)
defined class Person

Monoidにするための設定はしていないので当然Monoidではありません。モノイド演算の演算子|+|はMonoidの親型クラスSemigroupで定義しているので、PersonはSemigroupでない、というエラーになります。

scala> Person("Taro") |+| Person("Hanako")
<console>:16: error: could not find implicit value for parameter s: scalaz.Semigroup[Person]
              Person("Taro") |+| Person("Hanako")
                             ^

Personに対してListによるモノイド演算を行うためにListRecuderを取得します。

scala> val r = ListReducer[Person]
r: scalaz.Reducer[Person,List[Person]] = scalaz.Reducers$$anon$1@62bb8ae8

ListReducerのunitメソッドを使ってPersonをList[Person]にします。

scala> r.unit(Person("Taro"))
res7: List[Person] = List(Person(Taro))

consメソッドを使って、2をList(3)の左側からモノイド演算すると以下になります。

scala> r.cons(Person("Hanako"), r.unit(Person("Taro")))
res8: List[Person] = List(Person(Hanako), Person(Taro))

snocメソッドを使って、2をList(3)の右側からモノイド演算すると以下になります。

scala> r.snoc(r.unit(Person("Taro")), Person("Hanako"))
res9: List[Person] = List(Person(Taro), Person(Hanako))

List

参考のために以上の処理をListを直接使って書くと以下になります。

scala> List(Person("Taro"))
res10: List[Person] = List(Person(Taro))

scala> Person("Hanako") :: List(Person("Taro"))
res11: List[Person] = List(Person(Hanako), Person(Taro))

scala> List(Person("Taro")) :+ Person("Hanako")
res12: List[Person] = List(Person(Taro), Person(Hanako))

諸元

  • Scala 2.9.2
  • Scalaz 6.0.4

2012年6月26日火曜日

Scala Tips / Reducer (2) - List

前回はIntとIntMultiplicationを例にReducerを基本的な使い方について説明しました。

次は可換でないモノイド演算の例として任意の型TとList[T]を結びつけるListReducerを使ってみましょう。TにはIntを使うことにします。

まずListReducerの取得ですが以下のようにListに格納する型を指定して取得します。

scala> val r = ListReducer[Int]
r: scalaz.Reducer[Int,List[Int]] = scalaz.Reducers$$anon$1@719bc401

ListReducerのunitメソッドを使ってIntをList[Int]にします。

scala> r.unit(3)
res9: List[Int] = List(3)

consメソッドを使って、2をList(3)の左側からモノイド演算すると以下になります。

scala> r.cons(2, r.unit(3))
res10: List[Int] = List(2, 3)

snocメソッドを使って、2をList(3)の右側からモノイド演算すると以下になります。

scala> r.snoc(r.unit(3), 2)
res11: List[Int] = List(3, 2)

Listの場合は、左側からモノイド演算した場合と、右側からモノイド演算した場合で結果が変わってきます。前回説明したIntやIntMultiplicationの場合は結果が変わらないので、これは重要な性質の違いになります。結果が変わらないモノイドは可換モノイドと呼びます。今のところScalazで、単なるモノイドと可換モノイドを区別する手段はありません。

List

参考のために以上の処理をListを直接使って書くと以下になります。

scala> List(3)
res0: List[Int] = List(3)

scala> 2 :: List(3)
res1: List[Int] = List(2, 3)

scala> List(3) :+ 2
res2: List[Int] = List(3, 2)

ノート

アルゴリズムを記述する場合、一般的には普通にList(あるいはSeq)を使えば簡単でよいわけですが、アルゴリズムの操作対象をReducerにすることで、List以外の任意のデータ構造に対してアルゴリズムを適用することができるようになります。

この場合の条件は、操作対象がモノイドであるということです。モノイドを操作するアルゴリズムはReducerを対象にすることで、モノイドの性質を持つ任意のオブジェクトを操作対象にすることができるようになります。

モノイドを操作するアルゴリズムでは、ReducerではなくMonoidを操作対象にする選択肢もあります。このあたりの得失は別途考えてみたいと思います。

諸元

  • Scala 2.9.2
  • Scalaz 6.0.4

2012年6月25日月曜日

Scala Tips / Reducer

ScalazではIntなどの整数値のモノイド演算は加算として定義しています。数値に対するモノイド演算で最も利用されそうなのが加算なので妥当な選択ですが、場合によっては乗算などの演算を数値のモノイド演算として使用したい場合もあります。

そこでScalazでは、乗算をモノイド演算として定義したMultiplicationというオブジェクトを提供しています。Multiplicationは以下の7種類が用意されています。

数値Multiplication
ByteByteMultiplication
CharCharMultiplication
ShortShortMultiplication
IntIntMultiplication
LongLongMultiplication
BigIntBigIntMultiplication
BigIntegerBigIntegerMultiplication

このように、あるクラスに対するモノイド演算が複数存在する場合には、「追加のモノイド演算」と「あるクラス」を結びつける「別のクラス」を作成し、この「別のクラス」に「追加のモノイド演算」を定義します。具体的には「別のクラス」と「追加のモノイド演算」を定義した型クラスMonoidインスタンスを定義します。

このように「あるクラス」に対する別モノイド演算を定義した「別のクラス」が併存するシーンでのプログラミングの共通処理を担うためのツールとして利用できそうなのがReducerです。Reducerは、「あるクラス」と「あるクラス」に対する別モノイド演算を定義した「別のクラス」を結びつける演算を行うオブジェクトです。今回は、このReducerについてみていきます。

以下では、元のクラスである「あるクラス」をC、「追加のモノイド演算」と「あるクラス」を結びつける「別のクラス」をMと表記することにします。

動作確認

まず、IntとIntMultiplicationを結びつけるIntProductReducerです。前述の表記法による場合は、IntがC、IntProductReducerがMです。

IntProductReducerは「Scalaz._」で取り込まれているので以下のように取り出して使用することができます。

scala> val r = IntProductReducer
r: scalaz.Reducer[Int,scalaz.IntMultiplication] = scalaz.Reducers$$anon$1@8dbe4e5

Reducerは以下の3つのメソッドを持っています。

unit
CからMを生成。
cons
CをMの左側から連結したMを返す。
snoc
CをMの右側から連結したMを返す。

モノイド演算では、2つの要素AとBを、ABの順で演算するのか、BAの演算するのかで演算結果が異なる可能性があります。(演算結果が異ならないものは特別に可換モノイドと呼びます。)

そこで、Reducerでは元のオブジェクトMに対して新しいオブジェクトCを左側からモノイド演算、すなわち「C+M」するためのメソッドとしてconsを提供しています。メソッド名consの由来は言うまでもなくLispのcons関数です。

また、元のオブジェクトMに対して新しいオブジェクトCを右側からモノイド演算、すなわち「M+C」するためのメソッドとしてsnocを提供しています。メソッド名snocは言うまでもなく「cons」を逆にしたものですね。

IntReducerのメソッドはそれぞれ以下の動きになります。

unit
IntからIntMultiplicationを生成。
cons
IntをIntMultipilcationの左側から連結したMを返す。
snoc
IntをIntMultiplicationの右側から連結したMを返す。

それぞれの動きは以下になります。

scala> r.unit(3)
res5: scalaz.IntMultiplication = 3

scala> r.cons(2, r.unit(3))
res2: scalaz.IntMultiplication = 6

scala> r.snoc(r.unit(3), 2)
res4: scalaz.IntMultiplication = 6

IntMultiplicationは可換モノイドなので、左側から足しても右側から足しても結果は変わりません。このため、consメソッドの場合も、snocメソッドの場合も結果は「10」になります。

IntMultiplicationを直接使う

上記の処理をIntMultiplicationを直接使って記述すると以下になります。

scala> multiplication(3)
res6: scalaz.IntMultiplication = 3

scala> multiplication(2) |+| multiplication(3)
res7: scalaz.IntMultiplication = 6

scala> multiplication(3) |+| multiplication(2)
res8: scalaz.IntMultiplication = 6

ノート

関数型プログラミングは、どうも「モノイド」が重要概念の一つで、プログラミングテクニックとしてあちこちに登場してきます。

Scalazでは、型クラス「Monoid」を提供しておりモノイド演算を行う演算子「|@|」を導入しています。演算子「|@|」を使って処理を記述することで、任意のモノイドに対する共通関数が記述できることをブログ内でも度々取り上げてきました。

問題は一つのクラスに対して複数のモノイド演算を定義する場合です。Intに対するIntMultiplicationといったように複数のクラスでモノイド演算を行う場合に、共通処理を記述するためのメカニズムの一つとしてReducerが導入されていると考えられます。

実際に所Reducerを使うシーンは少なそうですが、モノイドを操作するテクニックを引き出しに入れておくと色々応用が効きそうです。そういう意味でReducerは面白い素材なのでもう少し見ていく予定です。

諸元

  • Scala 2.9.2
  • Scalaz 6.0.4

2012年6月22日金曜日

Scala Tips / multiplication

モノイド演算は加算に限るわけではなく、条件を満たす任意の演算が対象となります。

ScalazではIntなどの整数値のモノイド演算は加算として定義しています。数値に対するモノイド演算で最も利用されそうなのが加算なので妥当な選択ですが、場合によっては乗算などの演算を数値のモノイド演算として使用したい場合もあります。

そこでScalazでは、乗算をモノイド演算として定義したMultiplicationというオブジェクトを提供しています。Multiplicationは以下の7種類が用意されています。

数値Multiplication
ByteByteMutiplication
CharCharMutiplication
ShortShortMutiplication
IntIntMutiplication
LongLongMutiplication
BigIntBigIntMutiplication
BigIntegerBigIntegerMutiplication

以下ではIntのMultiplicationであるIntMultiplicationを例にMultiplicationの使い方について説明していきます。

Intのモノイド演算

まずIntのモノイド演算を確認します。

scala> 3 |+| 5
res71: Int = 8

結果は「3+5」で8になりました。ScalazにおけるIntは加算を二項演算子とするモノイドであることが確認できました。

IntMultiplication

Scalazはモノイド演算を乗算にしたIntとしてIntMultiplicationオブジェクトを提供しています。

IntMultiplicationの生成方法は2つです。

1つはmultiplication関数を使う方法です。

scala> val a = multiplication(3)
a: scalaz.IntMultiplication = 3

もう一つはIntの∏メソッドを使う方法です。「∏」は「N-ARY PRODUCT」を示すUnicode文字です。

scala> val b = 5 ∏
b: scalaz.IntMultiplication = 5

モノイド演算

先ほど生成した2つのIntMultiplicatinオブジェクトを演算子「|+|」でモノイド演算してみます。

scala> val c = a |+| b
c: scalaz.IntMultiplication = 15

結果は「3×5」で15になりました。IntMultiplicatinは、乗算を二項演算子とするモノイドであることが確認できました。

Intに戻す

IntMultiplicatinをIntに戻すには属性valueを使用します。

scala> a.value
res73: Int = 3

scala> b.value
res74: Int = 5

scala> c.value
res75: Int = 15

モノイド畳込み

モノイドの重要なユースケースが畳込みです。モノイドを畳込み対象にすることで色々な指定を省略することができます。(Validation (25) - fold monoid)

IntのListに対してモノイドの畳込みをすると総和が得られます。foldメソッドなどを使った通常の畳込みと比べると初期値と畳込み演算の両方を省略することができます。

scala> List(1, 2, 3, 4, 5).sumr
res63: Int = 15

IntのListに対して乗算で畳込みを普通に書くと以下になります。

scala> List(1, 2, 3, 4, 5).foldRight(1)((x, a) => a * x)
res66: Int = 120

これをIntMultiplicationを用いて、乗算を二項演算子とするモノイド演算として実装すると以下になります。

IntのListをIntMultiplicationのListに変換後、モノイド演算による畳込みをしていますが、IntMultiplicationのモノイド演算が乗算なので、List内のIntをすべて掛けた結果の120が返ってきています。

scala> List(1, 2, 3, 4, 5).map(multiplication).sumr
res64: scalaz.IntMultiplication = 120

上の演算結果はIntMultiplicationなので、さらにIntに戻すには以下のように最後にvalueをアクセスすればOKです。

scala> List(1, 2, 3, 4, 5).map(multiplication).sumr.value
res77: Int = 120
モノイドの零元

モノイドが畳込みと相性が良い理由の一つが、モノイドの零元を畳込みの初期値に使えることがあります。

Intの零元は以下のように0になります。

scala> mzero[Int]
res68: Int = 0

一方IntMultiplicationの零元は以下のように1になります。

scala> mzero[IntMultiplication]
res67: scalaz.IntMultiplication = 1

加算による畳込みの場合の初期値として0、乗算による畳込みの場合の初期値として1を使うのは当たり前といえば当たり前なので、この指定を自動的に行なってくれるのはプログラミング的にとてもありがたいことです。

foldMap

ScalazはMonoidに対する畳込みを行うメソッドとしてfoldMapメソッドを用意しています。foldMapメソッドは元の値をMonoidに変換する関数を引数に取り、変換後のMonoidに対して畳み込みを行います。

IntのListに対して乗算による畳込みを行う場合は以下のようになります。基本的には前述したmapメソッドでMonoidに変換後sumrメソッドでモノイド畳込みを行うのと同じになります。

scala> List(1, 2, 3, 4, 5).foldMap(multiplication)
res69: scalaz.IntMultiplication = 120

計算結果のIntMultiplicationからIntを取り出すには属性valueをアクセスします。

scala> List(1, 2, 3, 4, 5).foldMap(multiplication).value
res70: Int = 120

ノート

「∏」(220F)はN-ARY PRODUCTという名前のUnicode文字です。直積を表すUnicode文字のようです。

直積はパイ(π)の大文字である「Π」(03A0)でも表現できると思いますが、数学記号の直積として使う場合は「∏」(220F)を使うのがUnicodeの流儀ということのようです。

「∏」(220F)の分かりやすい説明は以下のページにもありました。

諸元

  • Scala 2.9.2
  • Scalaz 6.0.4

2012年6月21日木曜日

Scala Tips / Validation (33) - reduce

fold系メソッドのバリエーションとしてreduce系のメソッドがあります。

fold系メソッドは、畳込みの初期値を指定するので元のオブジェクトの集りを全く異なったオブジェクトに変換することができます。

一方、reduce系メソッドは畳込みの初期値を指定しません。引数の数が減るというメリットがありますが、その代償として、変換先が元のオブジェクトまたはその親クラスのオブジェクトに限定されます。

初期値の設定が不要なので少し使い方が簡単になっている面があります。このため「変換先が元のオブジェクトまたはその親クラスのオブジェクトに限定」されてもよいケースでは有力な選択肢です。たとえばIntの集りをIntに畳み込む場合は初期値はなくても構わないのでreduce系メソッドでも十分なわけです。

今回はValidationに対してreduce系メソッドを適用するイディオムについて見ていきます。

課題

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

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

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

この課題は「Validation (23) - fold」と同じものです。

reduce, reduceLeft, reduceRight

foldメソッド、foldLeftメソッド、foldRightメソッドに対応するのがreduceメソッド、reduceLeftメソッド、reduceRightメソッドです。Applicativeを使った実装は、それぞれ以下のようになります。

def f(a: List[ValidationNEL[Throwable, Int]]): ValidationNEL[Throwable, Int] = {
  if (a.isEmpty) 0.success
  else a.reduce((a, b) => (a |@| b)(_ + _))
}
def f(a: List[ValidationNEL[Throwable, Int]]): ValidationNEL[Throwable, Int] = {
  if (a.isEmpty) 0.success
  else a.reduceLeft((a, x) => (a |@| x)(_ + _))
}
def f(a: List[ValidationNEL[Throwable, Int]]): ValidationNEL[Throwable, Int] = {
  if (a.isEmpty) 0.success
  else a.reduceRight((x, a) => (a |@| x)(_ + _))
}

reduceメソッド、reduceLeftメソッド、reduceRightメソッドの選択基準はfoldの場合と同じで、右畳込みであるreduceRightを軸にするとよいでしょう。

reduceメソッド、reduceLeftメソッド、reduceRightメソッドの使用上の問題点は、ListがNilだった時に例外が発生する点です。このため使用する前にListが空の場合にはデフォルトの値を使うようにするなどの対応が必要になります。

reduceOption, reduceLeftOption, reduceRightOption

空の場合の扱いを考えるとListが空か否かをOptionで扱うのが常道です。このためreduceのOption版であるreduceOptionメソッド、reduceLeftOptionメソッド、reduceRightOptionメソッドが用意されています。reduceOptionメソッド、reduceLeftOptionメソッド、reduceRightOptionメソッドを使った実装はそれぞれ以下になります。

def f(a: List[ValidationNEL[Throwable, Int]]): ValidationNEL[Throwable, Int] = {
  a.reduceOption((a, b) => (a |@| b)(_ + _)) | 0.success
}
def f(a: List[ValidationNEL[Throwable, Int]]): ValidationNEL[Throwable, Int] = {
  a.reduceLeftOption((a, x) => (a |@| x)(_ + _)) | 0.success
}
def f(a: List[ValidationNEL[Throwable, Int]]): ValidationNEL[Throwable, Int] = {
  a.reduceRightOption((x, a) => (a |@| x)(_ + _)) | 0.success
}

Optionからデータを取り出し、Noneの場合にはデフォルト値を補う処理が必要になります。

sequence

ValidationのListを扱う場合はsequenceメソッドを使うのがイディオムになっています。sequenceメソッドを使った実装は以下になります。

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

reduce系の場合もこのアプローチが当てはまります。

monoid

fold系の場合と同様に、Validationが保持する値をIntのような具象オブジェクトではなく、Monoidを対象にすると汎用性が高まります。この実装は以下になります。

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

ノート

reduce系のメソッドは初期値を指定しなくて良いので一見便利そうなのですが、Listが空だった時の判定を行わないといけないので案外使いづらいようです。プログラミング戦略としては、reduce系のメソッドのことはあまり考えず、fold系一本で考えてよいと思います。

reduce系のメソッドは、対象をMonoid(あるいは型クラスZero)に限定することで、初期値の省略時にはクラスごとのデフォルトの初期値を使うようになっていると便利そうです。そういう意味では、Scalazのsum/sumrメソッド、foldMapメソッドがまさにそういった便利メソッドなので、これらのメソッドが重要な選択肢になってきます。

Validationのreduce的な処理が必要なときは、sequenceで加工した後に:

  • sum/sumrメソッド
  • foldMapメソッド
  • fold系メソッド

の順に使用するfold由来メソッドを検討していけばよいでしょう。

諸元

  • Scala 2.9.2
  • Scalaz 6.0.4

2012年6月20日水曜日

Scala Tips / Validation (32) - Function0

ここまでで以下のValidationをサポートするScalazの機能を見てきました。

今回はFunction0[T]のthrowsメソッドです。

throwsメソッド

Scalazは「Function0[T]」(「() => T」)つまり引数なしの関数にthrowsメソッドを追加します。throwsメソッドは、関数の実行結果をValidation[Throwable, T]として返します。関数を実行した結果、例外が発生した場合はThrowableをFailure包んでValidation化します。このため例外のキャッチ処理を書かなくてよくなります。

throwsの動き

例としてStringのparseIntメソッドに相当する関数を自前で書くことを考えてみましょう。

parseIntメソッドの動きは以下になります。

scala> "100".parseInt
res15: scalaz.Validation[NumberFormatException,Int] = Success(100)

scala> "a".parseInt
res16: scalaz.Validation[NumberFormatException,Int] = Failure(java.lang.NumberFormatException: For input string: "a")

StringのtoIntメソッドを使うと以下になります。文字列の値がおかしい場合に例外が発生します。

scala> "100".toInt
res17: Int = 100

scala> "a".toInt
java.lang.NumberFormatException: For input string: "a"
 at java.lang.NumberFormatException.forInputString(NumberFormatException.java:48)
 at java.lang.Integer.parseInt(Integer.java:449)
 at java.lang.Integer.parseInt(Integer.java:499)
(以下略)

Function0のthrowsメソッドを使うと以下になります。例外のハンドリングは自動的に行なってくれるので随分楽ですね。

scala> (() => "100".toInt).throws
res19: scalaz.Validation[Throwable,Int] = Success(100)

scala> (() => "a".toInt).throws
res20: scalaz.Validation[Throwable,Int] = Failure(java.lang.NumberFormatException: For input string: "a")

本ブログで標準にしているValidationNEL[Throwable, T]にするためには、補正にliftFailNelメソッドを用います。

scala> (() => "100".toInt).throws.liftFailNel
res22: scalaz.Validation[scalaz.NonEmptyList[Throwable],Int] = Success(100)

scala> (() => "a".toInt).throws.liftFailNel
res23: scalaz.Validation[scalaz.NonEmptyList[Throwable],Int] = Failure(NonEmptyList(java.lang.NumberFormatException: For input string: "a"))

使い方

Validation (6) - Exception」で使った課題をthrowsを使って書いてみます。Validationの文脈で例外を扱います。

課題

ValidationNEL[Throwable, String]からValidationNEL[Throwable, Int]への変換を例に考えます。Validationに入っているStringがIntに変換できる場合は有効となり、Success[NonEmptyList[Throwable], Int]が処理結果となります。一方、変換できない場合は無効となりFailure[NonEmptyList[Throwable], Int]が処理結果となります。

ここで、StringからIntへの変換ができない事の判定に例外を使用します。(String#toIntメソッドがNumberFormatExceptionをスロー。)

以前の解

Validation (6) - Exception」では、scala.util.control.ExceptionのallCatchを使うのが最終型でした。実装は以下になります。

import scala.util.control.Exception._  
  
def f(a: ValidationNEL[Throwable, String]): ValidationNEL[Throwable, Int] = {  
  a flatMap { b =>
    allCatch either {  
      b.toInt  
    } fold (_.failNel, _.success)  
  }  
}

scala.util.control.Exceptionは、例外をOptionやEitherに変換してくれる処理は持っているのですが、ScalazのオブジェクトであるValidationは当然スコープ外になります。このため、EitherからValidationへの変換処理を利用者側で書く必要があります。

throwsを使った解

throwsを使った解は以下になります。例外を直接Validation化してくれるのですっきりしますね。

def f(a: ValidationNEL[Throwable, String]): ValidationNEL[Throwable, Int] = {  
  a.flatMap(b => (() => b.toInt).throws.liftFailNel)
}

throwsはValidation[Throwable, T]を返すため、本ブログで標準にしているValidationNEL[Throwable, T]と若干型がずれます。この補正にliftFailNelメソッドを用いています。

ノート

Validation (6) - Exception」を書いた時点では、scala.util.control.ExceptionのallCatchを使うのがベストだと思っていたのですが、Function0のthrowsを使うとより簡潔に書くことができることが分かりました。例外処理はthrowsを使うのをイディオムとして整備したいと思います。

例外を細かくキャッチし分けたい場合は、引き続きscala.util.control.Exceptionのcatchingが有効です。

諸元

  • Scala 2.9.2
  • Scalaz 6.0.4

2012年6月19日火曜日

Scala Tips / Validation (31) - Function1

エラーが発生する処理を書く場合、Option、Either、Validationのいずれかを使って「成功または失敗の文脈」の中でエラー情報を引き継いでいくことになります。この中でValidationはScalazのオブジェクト/モナドということもあって、Scalazの機能の中で色々なサポートが行われています。

ここまでで以下の2つを紹介しました。

今回はtoValidationメソッドの紹介のし直しです。

Validation (13) - toValidation」は、「Validation (14) - オブジェクトの生成」による応用のための部品を準備するという趣旨の記事だったため、Function1[T, Boolean]のtoValidationメソッドの使い方のカタログという観点にはなっていませんでした。今回は「Validation (13) - toValidation」の記事の前段階ぐらいの内容にあたる基本的な使い方を整理します。

toValidationメソッド

「Function1[T, Boolean]」(「T => Boolean」)がある場合に、これからValidationを生成する関数を作り出すのがtoValidationメソッドです。たとえば以下のisValidAge関数はInt値を判定して真偽をBooleanで返す関数ですが、こういった関数から真偽をValidationで返す関数を作ります。

def isValidAge(age: Int): Boolean = {
  0 <= age && age <= 150
}

これを関数オブジェクト化するとtoValidationメソッドが使えるようになります。

scala> val b = isValidAge _
b: Int => Boolean = <function1>

関数オブジェクトのtoValidationメソッドで新しい関数オブジェクトを生成します。toValidationメソッドでは、真偽の判定が偽になった場合に生成するFailureの値を指定します。Failureには自動的にNonEmptyListが使用されるようになっています。

scala> val v = b.toValidation(new IllegalArgumentException("bad age"))
v: Int => scalaz.Validation[scalaz.NonEmptyList[java.lang.IllegalArgumentException],Int] = <function1>

toValidationメソッドで生成したValidation化された判定関数の動作は以下となります。

scala> v(10)
res0: scalaz.Validation[scalaz.NonEmptyList[java.lang.IllegalArgumentException],Int] = Success(10)

scala> v(-1)
res1: scalaz.Validation[scalaz.NonEmptyList[java.lang.IllegalArgumentException],Int] = Failure(NonEmptyList(java.lang.IllegalArgumentException: bad age))

scala> v(200)
res2: scalaz.Validation[scalaz.NonEmptyList[java.lang.IllegalArgumentException],Int] = Failure(NonEmptyList(java.lang.IllegalArgumentException: bad age))

使い勝手

toValidationメソッドの使い勝手について考えてみます。

toValidationメソッドを使わないで普通に書くと以下のようになります。

def validateAge(age: Int): ValidationNEL[Throwable, Int] = {
  if (isValidAge(age)) age.success
  else new IllegalArgumentException("bad age = " + age).failNel
}

toValidationメソッドを使うと、以下のように新しい関数オブジェクトを変数に設定することで、新しい関数を定義するようなことが簡単にできます。

val validateAge = (isValidAge _).toValidation(new IllegalArgumentException("bad age"))

ただし、一つ問題があってエラー情報の中にオリジナルの値の情報を入れることができません。「new IllegalArgumentException("bad age")」はできても、「new IllegalArgumentException("bad age = " + age)」はできないということですね。

これをやるためには以下のようにメソッド化します。toValidationを使わない場合とコーディング量はあまり変わらなくなってしまいます。

def validateAge(age: Int): ValidationNEL[Throwable, Int] = {
  val f = (isValidAge _).toValidation(new IllegalArgumentException("bad age = " + age))
  f(age)
}

ということで、toValidationメソッドは万能というわけではないですが、Function1[T, Boolean]からFunction1[T, ValidationNEL[Throwable, T]]という部品を作りたいケースは割とよくあるので、条件が合えば便利に利用できそうです。

続き

この記事の後、応用編として「Validation (13) - toValidation」が続きます。

諸元

  • Scala 2.9.2
  • Scalaz 6.0.4

2012年6月18日月曜日

MindmapModeling「小林製薬はなぜアイデア新商品を生み出せるのか」

6月18日(土)に横浜モデリング勉強会(facebook group)を行いました。また、会場には(株)アットウェア様の会議室をお借りしました。参加された皆さん、アットウェア様、どうもありがとうございました。

この勉強会で、浅海が作成したモデルを紹介します。モデルはMindmapModelingの手法で作成しました。(勉強会で使用したチュートリアル)

ここ数回、勉強会の進め方を模索していますが、今回は勉強会の進め方を以下のようにすることにしました。

モデル駆動による実装を指向するのは変わりませんが、時間的にプログラミングの所まではいけません。そこで「記事」と「プログラミング」を「モデル駆動」でつなぐあいだにある中継地点を探しているわけですが、今回は以下のようにしてみました。

  • 雑誌記事から情報システムの企画書、提案書、RFPの元ネタとなるモデルを作成する。

その上で、「要求仕様確認、実装可能性確認、開発のベースとなるプログラムを自動生成するモデルを目指」します。詳細は「ワークショップの進め方 (2012-06-16)」になります。

今回試してみてちょうど良い感じだったので、次回以降もこの方法で進めていこうと思います。

テーマ

モデリングの対象は、日経ビジネス誌の記事「小林製薬はなぜアイデア新商品を生み出せるのか」です。

「製品開発のアイデアを管理するシステム」という切り口で、企画書、提案書、RFPのネタとしてぴったりの内容です。

用語の収集と整理

まず用語の収集と整理します。

MindmapModelingに慣れてくると、用語がだいたいどこの枝に収まるのかわかるようになるので、用語を拾いながら、ラフなモデルを作っていきます。




今回の記事、モデルで特徴的なのは「規則(rule)」が明確になっているということです。ここでは以下の規則を抽出しています。

  • 新製品は発売初年の製品
  • 準新製品は発売4年以内の製品 (準新製品の用語はモデリングのために導入)
  • 売上高に占める新製品比率の目標は10%
  • 売上高に占める準新製品比率の目標は35%
  • 小林式ノーム式

ビジネスシステムの軸としてビジネス・ルールを定め、各ビジネス・プロセスのパフォーマンスをこれらのルールで計測した結果を元にフィードバックをかけている事が分かります。

いわゆるPDCAサイクルがうまくまわっているのが、「小林製薬はなぜアイデア新商品を生み出せるのか」の理由ということのアタリがつくので、これを支援するための情報システムの企画というのが落とし所になりそうです。

物語

次の作業は「物語」です。

モデルは中心軸がないと単なる「用語」の集りなのでまとまりがでてきません。何らかの目的を実現するための構造を抽出したいわけですが、この「目的」と「目的を実現するための構造」を掬いとるためのツールとして有効なのが「物語」です。オブジェクト・モデリングの概念ではビジネス・ユースケースということになります。

「物語」を中心軸と定め、「物語」のスコープで用語を取捨選択、組織化し、足りない用語を補っていきます。

その手順は:

  1. 物語の名前をつける。目的(goal)が明確になる名前がよい。
  2. 物語の主人公、相手役、脇役などの登場人物を定める。
  3. 物語で使用する道具を定める。
  4. 出来事または脚本の列として脚本を記述する。

となります。2の登場人物と3の道具は最初から完全なものはできないので暫定的なものを定め、4の脚本の作業を通して洗練させていきます。




今回の作業では、最初の物語を「アイデアを製品というカタチにしていく」と定めました。そして、脚本を作る作業を先に進めました。

脚本を書く中で、重要な道具が「提案」と「製品」であることが分かってきたので、この構造の整理を同時に行なっています。構造の整理を進めると、区分(powertype)と役割(role)が明確になってきます。区分(powertype)と役割(role)がどの程度整備されてきているのかがモデリングの充実度の目安になります。

また、規則の候補として「製品のグロスプロフィット率」が抽出できました。(規則の枝にはマージができていませんが)

最終型

前述の方針でさらに洗練を進めたモデルが以下になります。



製品開発のPDCA全体を回すシステムを目指したいわけですが、記事の情報からモデルの内容はP(Plan)の部分が厚くなっています。脚本の「提案を収集する」、「提案を仕分けする」のあたりですね。

時間切れでモデルはここまでとなりました。

この後の伸ばし方としては、PDCAサイクルの各フェーズに対応するサブ物語を定め、各サブ物語の脚本を詳細化していくなかで、システムの全体像を洗い出すことを目指します。その後:

  • ロバストネス分析をかけてビジネス・システム全体のアーキテクチャモデルの作成
  • システムユースケースからロバストネス分析をかけて情報システムの作成

といった手順を踏んでいくことになります。

クラス図

SimpleModelerでクラス図化したものが以下になります。



クラス図をみると、MindmapModelingのモデル上でまだうまくつながっていないところがあるのが分かります。まだ整備が必要ですが、情報システムを考える上での元ネタとなるモデルには仕上がってきていると思います。

さらに作業を続けるとすると、このクラス図の結果から修正すべきポイントをMindmapModelingモデルに反映してさらに洗練を進めていき、キリのいいところでScala DSLを生成してプロトタイプ開発に入っていく流れになります。

ワークショップでの作業時間は2時から6時までの4時間なので、だいたいこのあたりのモデルになるのが目処になります。

次回

次回は7月21日(土)です。

今回と同じく「ワークショップの進め方 (2012-06-16)」の手順で、「雑誌記事から情報システムの企画書、提案書、RFPの元ネタとなるモデルを作成する」を行う予定です。

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

2012年6月14日木曜日

Scala Tips / Validation (29) - Foldable

Scalazの型クラスFoldableは、Foldableの型クラスインスタンスを定義しているオブジェクトに適用されます。このオブジェクトをFoldableオブジェクトと呼ぶことにしましょう。「Validation (24) - fold scalaz」で説明したとおり、Foldableオブジェクトには、多数のFoldable関連のメソッドが自動的に追加されます。この中でfold系メソッドと呼べるものは以下のものです。

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

これらのメソッドを除いた、Foldableの機能を間接的に使っているメソッドは以下のものです。

  • listl
  • sum
  • count
  • maximum
  • minimum
  • longDigits
  • digits
  • sumr
  • listr
  • stream
  • asStream
  • foldIndex
  • any
  • all
  • empty
  • element
  • splitWith
  • selectSplit
  • bktree

今回は、これらの機能をValidationに適用するケースについて考えます。

課題

Monoidを格納したValidationのListを畳み込んでMonoidの合算値を格納したValidationにします。

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

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

sequence

結論から言うと、今回テーマにしている機能を使う場合、sequenceメソッドを使用するのがイディオムになります。(「Validation (24) - fold scalaz」、「Validation (25) - fold monoid」)Validation操作で必須スキルの型パラメータの扱いは「Validation (21) - traverse」が詳しいです。

Monoidの合算値はsumメソッドまたはsumrメソッドが使えますが(「Validation (25) - fold monoid」)、右畳込みのsumrメソッドの方が有利です。(「foldの選択」)

以上の選択から結果は以下となります。

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

イディオム

結論として、Validationの集りにFoldableの以下の形が一つのイディオムです。「XXX」の所が、sumrメソッドなどのFoldable系のメソッドになります。

type VNT[A] = ValidationNEL[Throwable, A]
  a.sequence[VNT, T].map(_.XXX)

typeによる型定義を使わず一行で済ませる場合は以下となります。好みの方を使うとよいでしょう。

a.sequence[({type λ[α] = ValidationNEL[Throwable, α]})#λ, T].map(_.XXX)
使用例

指定された値が入っているのかを調べるanyメソッドの使用例は以下になります。Successにanyメソッドの結果(この場合はtrue)が格納されたものが返ってきます。

scala> List(1.success, 2.success, 3.success).sequence[VNT, Int].map(_.any(_ == 2))
res88: scalaz.Validation[scalaz.NonEmptyList[Throwable],Boolean] = Success(true)

maximumメソッドの場合は以下になります。maximumメソッドの場合は、Listが空だった場合を考慮して結果がOptionで返ってくるので注意が必要です。

scala> List(1.success, 2.success, 3.success).sequence[VNT, Int].map(_.maximum)
res86: scalaz.Validation[scalaz.NonEmptyList[Throwable],Option[Int]] = Success(Some(3))

Listが空だった場合は-1にしたいというケースでは以下のようにすればよいでしょう。(「Option」)

scala> List(1.success, 2.success, 3.success).sequence[VNT, Int].map(_.maximum | -1)
res90: scalaz.Validation[scalaz.NonEmptyList[Throwable],Int] = Success(3)

もう一点注意が必要なのはFoldableのメソッドとListのメソッドで名前の重複がある場合です。countメソッドがこれにあたります。この場合はasMAメソッドでScalazの機能を使うことを明示した上でcountメソッドを使えば大丈夫です。(「Validation (25) - fold monoid」)

scala> List(1.success, 2.success, 3.success).sequence[VNT, Int].map(_.asMA.count)
res85: scalaz.Validation[scalaz.NonEmptyList[Throwable],Int] = Success(3)

foldRight

sequenceメソッドを使えるのは、Monad/Applicativeが提供する計算文脈ジョインの自動処理が処理目的とあっている場合です。そうでない場合は、foldRightメソッドなどのfold系メソッドとmatch式を組合わせてロジックを組む必要があります。詳しくは、以下を参照してください。

ノート

Validation (24) - fold scalaz」で取り上げた以下のメソッドはTraverseなので、この記事では対象外にしました。

  • foldMapDefault
  • collapse

諸元

  • Scala 2.9.2
  • Scalaz 6.0.4

2012年6月13日水曜日

Scala Tips / foldの選択

前回、Listを生成する畳込みについて考えました。Listの場合は、右畳込み(foldRight、foldr、sumr)の方を基本として、必要に応じて左畳込み(foldLeft, foldl, sum)を使っていくのが得策です。

Listの場合は右畳込みがよいとして、SeqやMonoidといったより汎用的なコンテナを生成する場合も右畳込みを基本にして問題がないのであれば、プログラミングの基本戦略としてfold系処理は右畳込みに統一することができます。

Listは、SeqやMonoidとして使われることも多いので、SeqやMonoidに対する処理もSeqやMonoidの実体がListだった場合を柱の一つとしてアルゴリズムを選択していく必要があります。Listは関数型プログラミングの中軸となるデータ構造であり、使用頻度が圧倒的に多いからです。

その一方で、SeqやMonoidとして使用されることがあるオブジェクトで、右畳込みを行うと重大なペナルティが発生する場合は、何らかの対策が必要になります。

今回は、この点について考えてみます。

Seq

Scala Tips / 多重度の表現」で説明したように、Scalaの代表的なSeqは、List、Stream、Vectorの3つです。

最前段への挿入と最後尾への追加に関して以下の性能特性があります。






最前段への挿入最後尾への追加
List高速低速
Vector普通普通
Stream高速低速

使用比率は恐らく:

  • List:Stream:Vector:その他 = 95.0:4.8:0.1:0.1

ぐらいなので「最前段への挿入」派(List+Stream)の99.8%をメインターゲットにしておくのが得策です。

さらにVectorは「最前段への挿入」と「最後尾への追加」のどちらも無難にこなすという特性を持つので、「最前段への挿入」をしても大きなペナルティがあるわけではありません。(最後尾への追加のほうが若干有利ではないかと推測します。)

以上の点からSeqへの畳込みは「最前段への挿入」を軸に考えるのが得策です。つまり、左畳込みのfoldLeftやfoldl、sumではなく、右畳込みのfoldRightやfoldr、sumrをメインの選択とするのがよいということになります。

Monoid

Monoidに対する畳込みは型クラスFoldableのsumメソッドやsumrメソッドで行うことができます。foldLeftfoldRight, foldlfoldrを使うよりもずいぶん楽になります。

Monoidは結合律によって左側から畳み込んでも右側から畳み込んでも同じ結果が得られます。このため、左側から畳み込むのか、右側から畳み込むのかは性能特性で決めておくのが得策です。

Seq
SeqはMonoidの一種ですが、前述したように右からの畳込みが有利です。
NonEmptyList
ScalazのNonEmptyListも構造上、性能特性はListに準じます。
数値
Intなどの数値も典型的なMonoidですが、これは左からの畳込みも右からの畳込みも性能特性上は全く同じとなります。
String
ScalaのStringの実体はJavaのStringですが、これも左からの畳込みも右からの畳込みも性能特性上は全く同じとなります。

Monoidのインスタンスとしては他にも候補はあるでしょうが、実運用的には上記のものでおおむねカバーできていると思います。これらのMonoidの特性をまとめると、Monoidの場合も右からの畳込みが有利といえます。

畳込みの選択基準

List、Seq、Monoidに対する畳込みについて検討してきました。結論は、いずれの場合も「右畳込み」が有利で、気になるような大きなペナルティもない、ということです。

今回、色々と調査して情報を整理したので、安心して右畳込みを軸にプログラミングできるようになったのが収穫です。

なお、右畳込みを採用する際の注意事項として、畳込み処理が純粋な関数であること、つまり副作用を伴わないこと、という条件があります。副作用が発生する場合は、副作用の発生順序が重要になるので左畳込みを使用せざるを得ません。

そういう意味でも、副作用をできるだけ排除していくのが、Scalaプログラミングの基本戦略になります。(参考: オブジェクトと関数の連携, オブジェクトと関数の連携 (2),楽々Scalaプログラミング)

いずれにしても「List&副作用のない関数&右畳込み」が関数型プログラミングの基本の型といえるので、これを軸にプログラミングしていくのがよいでしょう。

諸元

  • Scala 2.9.2
  • Scalaz 6.0.4

2012年6月12日火曜日

Scala Tips / Validation (28) - fold List

今回はListに対する畳込みについて考えます。

具体的には、Scalaではscala.collection.GenTraversableOnceのサブクラス、Scalazでは型クラスFoldableの対象に格納されている要素の集りを順序を維持したままListに畳み込む処理です。

Listの性能特性

いうまでもなくListは関数型プログラミングで中心的に使われるデータ構造で、いわゆる永続データ構造となっています。データ構造の仕組み上、最前段への挿入は速く、最後尾への追加は遅いという性能上の特性があります。

要素数が小さいうちはあまり関係はありませんが、要素数が増えてくると性能に大きく響いてくるので、プログラミングのイディオムとしては「Listへの畳込みは最前段への挿入」になる方向に寄せていくのが得策です。普段使いするイディオムは特に意識しなくても、「Listへの畳込み」が発生する場合は「最前段への挿入」となるとよいということですね。

畳込み

畳込みで直感的に分かりやすいのは左からの畳込みです。scala.collection.GenTraversableOnceのfoldLeftメソッド、型クラスFoldableのfoldlメソッド、sumメソッドですね。

しかし、ListからListに対する畳込みを行う際に、性能特性と相性のよいListの最前段への挿入を使用すると困ったことが起きます。以下のように、生成されたList内の要素が逆順になってしまうのです。

scala> List(1, 2, 3).foldLeft(nil[Int])((a, x) => x :: a)
res14: List[Int] = List(3, 2, 1)

この問題を回避するのに有効なのが右畳込みです。scala.collection.GenTraversableOnceのfoldRightメソッド、型クラスFoldableのfoldrメソッド、sumrメソッドですね。

以下のように右畳込みとListの最前段への挿入を併用すると、高速な「最前段への挿入」を使いつつList内の要素の順序が保証されます。

scala> List(1, 2, 3).foldRight(nil[Int])((x, a) => x :: a)
res16: List[Int] = List(1, 2, 3)

課題

Intを格納したValidationのListを畳み込んでIntのListを格納したValidationにします。

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

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

foldLeft

foldLeftメソッドを使うと以下になります。Validation内の要素を連結する処理なのでApplicativeを用いています。

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

foldLeftメソッドによる左畳込みの場合は、Listの最後尾に要素を追加するので「:+」メソッドを使っています。前述したように、Listの最後尾に要素を追加するのは性能的に得策ではありません。そういう意味で「:+」メソッドが出てきたらバッドスメルということができます。

foldRight

foldRightメソッドを使うと以下になります。Applicative演算の中で、「::」メソッドを使っています。

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

Listに対する「::」メソッドは、Listの最前段に要素を挿入するメソッドですが、Lisp由来の伝統的な関数です。そういう意味で「::」メソッドを使っている処理は安心できます。

なお「::」メソッドの代わりに「+:」メソッドを使うこともできます。「::」メソッドはList専用、「+:」メソッドはscala.collection.GenSeqLikeで定義されているSeq系コレクションの汎用メソッドです。

sequence

Validation (24) - fold scalaz」で説明したとおり、List[Validation[A]]→Validation[List[A]]にする処理はsequenceメソッドが定番です。

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

sequenceメソッドやそのベースとなっているtraverseメソッドの右畳込みの内部実装は、Traverse(この場合はList)をreverseしたものに対してfoldLeftしているので、問題はなさそうです。

ノート

Javaでこの手の処理を書くときは、ArrayListを使うことになりますが、ArrayListは最後尾の追加の性能がよく、最前段への挿入の性能がよくありません。そういう意味でも、Javaでのコーディングでは左からの畳込み的なロジックを多用してきたはずで、右畳込みを多用する関数型プログラミングでは意識改革が必要です。

とはいえ、左畳込みでないといけないケースもあるので、常に右畳込みを採用すればよいというわけにはいきません。また、格納順に処理を適用していく左畳込みの方がロジック的には安全です。

以上の点から、左畳込みと右畳込みの使い分けがScalaプログラミングのコツの一つとなっています。プログラミング中に毎回考えていては大変な上に間違いも起きやすいので、ユースケースに対するイディオムとして整備しておき、条件反射で使えるようにしておくのがよいでしょう。

Listの走査と右畳込み

Listは、最前段のへの挿入の方が最後尾への追加より高速でしたが、走査も先頭からの順走査の方が最後尾からの逆順走査よりも高速です。

右畳込みを使うと出力側のListへの挿入/追加は高速になりますが、入力側のListの走査は低速側を使うことになります。

また、右畳込みは再帰処理になるためこのオーバヘッドとスタック消費量の問題も考えないといけません。

この問題に対してはどのように考えていけばよいでしょうか。

一般的に更新処理の方が重たいので、更新側を高速、参照側を低速の組合せの方が高速な動作が期待できます。

さらに、ScalaとScalazは以下の対処を行っているようです。

Scala
@tailrcを使って末尾再帰であることを保証している。
Scalaz
mutableなArrayStackを使って要素を順方向に整えた後、順方向に操作を行なう処理になっている。

このため、入力側がListの場合でも、性能的なことはあまり気にせず右畳込みを行うことができるようになっています。

前述のTraverseのsequenceメソッド、traverseメソッドもそうでしたが、Scala/Scalazのクラスライブラリは右畳込みを前提に色々と工夫しているのが面白いですね。

諸元

  • Scala 2.9.2
  • Scalaz 6.0.4

2012年6月11日月曜日

Scala Tips / Validation (27) - fold or

Validationの集りに対して畳込みを行う場合、Failureの扱いには以下の2つの選択肢があります。

  • Failureが一つでもあれば畳込み全体をFailureにする。
  • Failureは飛ばしてSuccessのみを畳込む。

前回は、「Failureは飛ばしてSuccessのみを畳込む」の処理について、Validationが格納する要素がMonoidで、畳込み演算がMonoidの加算処理という条件で実装を行いました。このケースでは、foldメソッドは使う必要はあるものの、畳込み演算そのものはValidationの「>>*<<」メソッドを使って簡潔に記述することができました。

今回は「格納する要素がMonoidで、畳み込み演算がMonoidの加算処理」という条件を外して、より汎用的な処理方法について考えます。

課題

Stringを格納したValidationのリスト上で、StringをIntに変換後のIntを加算で畳み込んだ結果の値を格納したValidationを生成します。ただし、ValidationがFailureがあった場合には、Failureは飛ばしてSuccessのものだけを畳み込み結果をSuccessにします。

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

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

実装

課題の実装は以下になります。

def f(a: List[ValidationNEL[Throwable, String]]): ValidationNEL[Throwable, Int] = {
  type VNT[A] = ValidationNEL[Throwable, A]
  a.foldLeft(0.pure[VNT]) {
    (a, x) => x.flatMap(_.parseInt) match {
      case Success(s) => a.map(_ + s)
      case Failure(e) => a
    }
  }
}

かなりカスタムな処理になるので、foldLeftを使って地道にロジックを記述します。

初期値は「0.pure[VNT]」です。

畳込み演算のポイントは2つあります。一つはValidationの入れ子の捌き方です。Validation上のStringにparseIntメソッドを適用するとValidationが生成されるため、Validationの入れ子の中にStringが入ることになります。このValidationの入れ子を一つのValidationにまとめる必要があります。つまりValidation[String]→Validation[Validation[Int]]→Validation[Int]の変換を行うわけですが、これはString→Validation[Int]のmap演算とValidation[Validation[Int]]→Validation[Int]のjoin演算を連続実行したものです。さらにmap演算とjoin演算を合成したものがモナドのbind演算なので、このbind演算を行えばよいわけです。Scalaのbind演算はflatMapメソッドですから、flatMapメソッドでString→Validation[Int]を行うStringのparseIntメソッドを指定します。

もう一つは、flatMapメソッドの実行結果として得られるvalidation[Int]を、実際に畳込み込んでいく処理です。この処理が今回のテーマである「Failureは飛ばしてSuccessのみを畳込む」になります。ValidationのApplicative処理とは異なった処理をすることになるので、地道にmatch式で条件判定して以下の処理を記述します。

  • Successなら、積算値のValidationに値を足し込む。(mapメソッドを使用)
  • Failureなら、積算値をそのまま使う。(Failureの情報は捨てる)

入力がStringのListの場合

参考に、入力がStringを格納したValidationのListではなく、StringのListの場合を考えます。この場合は、前述のようにflatMapは使う必要はなく、parseIntメソッドの結果を直接match式で条件判定してケースごとの処理を記述します。

def f(a: List[String]): ValidationNEL[Throwable, Int] = {
  type VNT[A] = ValidationNEL[Throwable, A]
  a.foldLeft(0.pure[VNT]) {
    (a, x) => x.parseInt match {
      case Success(s) => a.map(_ + s)
      case Failure(e) => a
    }
  }
}

諸元

  • Scala 2.9.2
  • Scalaz 6.0.4

2012年6月8日金曜日

Scala Tips / Validation (26) - fold monoid or

Validationの集りに対して畳込みを行う場合、Failureの扱いには以下の2つの選択肢があります。

  • Failureが一つでもあれば畳込み全体をFailureにする。
  • Failureは飛ばしてSuccessのみを畳込む。

前者はValidationのScalaモナド、Scalaz Applicative演算の基本動作なので普通にモナド演算やApplicative演算を行うと自動的に処理が行われます。

問題は後者で、これはモナドやApplicative側で自動的に処理してくれないので、スクラッチでロジックを書く必要があります。

ここでは、Validationの格納要素をMonoidに限定し、畳込みをMonoidの加算演算の場合の実装方法について考えます。

前者の場合はsequenceメソッドとsumrメソッドの組合せを使えば、fold系メソッドを使わずにシンプルに実装する手段もあったわけですが、後者の場合はfold系メソッドを使って地道に実装する必要があります。ただしValidationの場合は、こういった用途に使える「>>*<<」メソッドを提供しているので、これを活用することにします。

課題

Monoid型の値を格納したValidationのリスト上で、Monoid型の値をモノイドの加法演算で畳込んで結果の値を格納したValidationを生成します。ただし、ValidationがFailureがあった場合には、Failureは飛ばしてSuccessのものだけを畳み込み結果をSuccessにします。

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

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

「>>*<<」メソッド

まず、Validationの「>>*<<」メソッドの動作確認をしておきましょう。

まず、Successを2つ、Failureを1つ用意します。

scala> val s1 = "1".parseInt.liftFailNel
s1: scalaz.Validation[scalaz.NonEmptyList[NumberFormatException],Int] = Success(1)

scala> val s2 = "2".parseInt.liftFailNel
s2: scalaz.Validation[scalaz.NonEmptyList[NumberFormatException],Int] = Success(2)

scala> val f = "x".parseInt.liftFailNel
f: scalaz.Validation[scalaz.NonEmptyList[NumberFormatException],Int] = Failure(NonEmptyList(java.lang.NumberFormatException: For input string: "x"))

前回の処理を行うと要素の一つがFailureであるため畳込み全体がFailureになります。これはsequenceメソッドによるValidationのApplicative演算で、Validationが一つでもFailureであると自動的に演算全体がFailureになるためですね。

scala> type VNT[A] = ValidationNEL[Throwable, A]
defined type alias VNT

scala> List(s1, f, s2).sequence[VNT, Int].map(_.sumr)
res41: scalaz.Validation[scalaz.NonEmptyList[Throwable],Int] = Failure(NonEmptyList(java.lang.NumberFormatException: For input string: "x"))

それでは「>>*<<」メソッドの動きを試してみましょう。

2つのSuccessを「>>*<<」すると、Success上に格納されているMonoid値が加算されます。「>>*<<」メソッドはある意味Monoidの「|+|」メソッドと同じような動きをイメージするとよいでしょう。Monoidの加算は「|+|」、Monoidを格納したValidationの加算は「>>*<<」、ですね。

scala> s1 >>*<< s2
res28: scalaz.Validation[scalaz.NonEmptyList[NumberFormatException],Int] = Success(3)

「>>*<<」メソッドは単に加算するだけでなく、Failureは読み飛ばすという機能を持っています。以下では、片方にFailureを指定していますが、これを読み飛ばしもう片方のSuccessが結果として返っています。

scala> s1 >>*<< f
res29: scalaz.Validation[scalaz.NonEmptyList[NumberFormatException],Int] = Success(1)

scala> f >>*<< s2
res30: scalaz.Validation[scalaz.NonEmptyList[NumberFormatException],Int] = Success(2)

「>>*<<」メソッドは以下のように複数連結することができます。この場合には、Failureは読み飛ばし、Successの集りを加算します。

scala> s1 >>*<< s2 >>*<< f
res31: scalaz.Validation[scalaz.NonEmptyList[NumberFormatException],Int] = Success(3)

scala> s1 >>*<< f >>*<< s2
res32: scalaz.Validation[scalaz.NonEmptyList[NumberFormatException],Int] = Success(3)

参考情報ですが、上の処理に対応するApplicativeの演算は以下になります。Applicativeの場合は一つでもFailureがあれば、演算全体がFailureになります。

scala> (s1 |@| f |@| s2)(_ |+| _ |+| _)
res34: scalaz.Validation[scalaz.NonEmptyList[NumberFormatException],Int] = Failure(NonEmptyList(java.lang.NumberFormatException: For input string: "x"))

実装

Validationの「>>*<<」メソッドを使った実装は以下になります。

あらかじめValidationの要素数が決まっている場合は、前述のように「>>*<<」メソッドをつないでいけばよいのですが、任意個数の場合にはfold系メソッドを使って畳込みを行う必要があります。

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
  }
}

Validationに格納されたMonoidの加算は「>>*<<」メソッド内で行ってくれるので「>>*<<」メソッドを「|+|」メソッド的な感覚で畳込みに使えばOKです。

畳込みの初期値にはMonoidの零元(mzero関数)をValidation化(pure関数)したものを使います。初期値がSuccessなので、仮に要素がすべてFailureであっても「>>*<<」メソッドによる畳込みは必ずSuucessになります。

動作確認

まず、テスト用のデータを用意します。sは全部Success、fsは一つだけSuccessとFailureが混在、ffは全部Failureです。

scala> val s = List(1.success, 2.success, 3.success)
s: List[scalaz.Validation[Nothing,Int]] = List(Success(1), Success(2), Success(3))

scala> val fs = List(1.success, new IllegalArgumentException("bad").failNel, 3.success)
fs: List[scalaz.Validation[scalaz.NonEmptyList[java.lang.IllegalArgumentException],Int]] = List(Success(1), Failure(NonEmptyList(java.lang.IllegalArgumentException: bad)), Success(3))

scala> val ff = List(new IllegalArgumentException("bad").failNel[Int], new IllegalArgumentException("bad").failNel[Int], new IllegalArgumentException("bad").failNel[Int])
ff: List[scalaz.Scalaz.ValidationNEL[java.lang.IllegalArgumentException,Int]] = List(Failure(NonEmptyList(java.lang.IllegalArgumentException: bad)), Failure(NonEmptyList(java.lang.IllegalArgumentException: bad)), Failure(NonEmptyList(java.lang.IllegalArgumentException: bad)))

全部Successはすべての要素が加算されたものがSuccessで返ってきます。

scala> f(s)
res8: scalaz.Scalaz.ValidationNEL[Throwable,Int] = Success(6)

一部Failureがある場合は、successのもののみが加算されたものがSuccessで返ってきます。

scala> f(fs)
res9: scalaz.Scalaz.ValidationNEL[Throwable,Int] = Success(4)

すべてFailureの場合は、Monoidの零元がSuccessで返ってきます。

scala> f(ff)
res25: scalaz.Scalaz.ValidationNEL[Throwable,Int] = Success(0)

エラーにしたい場合

課題では、前要素がFailureの場合には零元の値が返ってきましたが、演算全体をエラーにしたいケースもあると思います。

その場合には、以下のように初期値にFailureを指定します。初期値がFailureなので、要素もすべてFailureの場合「>>*<<」メソッドに対する引数がすべてFailureになるためですね。

def f[T: Monoid](a: List[ValidationNEL[Throwable, T]]): ValidationNEL[Throwable, T] = {
  val i: Throwable = new IllegalArgumentException("all bad")
  a.foldLeft(i.failNel[T]) {
    (a, x) => a >>*<< x
  }
}

初期値に適切な型を設定するのが案外大変です。ここでは、「val i: Throwable = new IllegalArgumentException("all bad")」として、変数iの型をThrowableに指定した上で「i.failNel[T]」として初期値の型の設定をしています。

動作確認

すべての要素がFailureの場合には、処理全体もFailureとなるようになりました。

scala> f(ff)
res27: scalaz.Scalaz.ValidationNEL[Throwable,Int] = Failure(NonEmptyList(java.lang.IllegalArgumentException: all bad, java.lang.IllegalArgumentException: bad, java.lang.IllegalArgumentException: bad, java.lang.IllegalArgumentException: bad))

諸元

  • Scala 2.9.2
  • Scalaz 6.0.4

2012年6月7日木曜日

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

2012年6月6日水曜日

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

2012年6月5日火曜日

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

2012年6月4日月曜日

Scala Tips / Validation (22) - sequence

Validationを操作する場合には、List[A]をList[ValidationNEL[Throwable, B]]を経由してValidationNEL[Throwable, List[B]]に変換する処理が頻出します。

前回は、traverseメソッドを用いてList[A]を直接ValidationNEL[Throwable, List[B]]に変換する処理について説明しました。

Validation (16) - 多重度1の実装」で説明したとおり、Validationを使う場合には「A→ValidationNEL[Throwable,B]」の関数を部品として用意するのが、Scalaプログラミングのコツ、Scalaプログラミング戦略のパターンです。(より汎用的には「A→M[B]」(Mはモナド)です。)

「A→ValidationNEL[Throwable,B]」の関数をList[A]に適用すると、List[ValidationNEL[Throwable, B]]になるので、このList[ValidationNEL[Throwable, B]]はValidationを使うプログラムでは自然に登場してくるデータ構造ということができます。

今回は、このList[ValidationNEL[Throwable, B]]をValidationNEL[Throwable, List[B]]に変換する方法について考えます。

課題

この関数を用いて、以下の関数を作ります。

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

動作確認

Validationに入る前に、ListとOptionを使って「M[N[A]]→N[M[A]]」の変換方法について説明します。

まず、traverseメソッドを使う場合には以下のように「x => x」と要素の変換をしない関数を設定すると、と自然にList[Option[Int]]がOption[List[Int]](「M[N[A]]→N[M[A]]」)に変換されます。

scala> List(1.some, 2.some, 3.some).traverse(x => x)
res38: Option[List[Int]] = Some(List(1, 2, 3))

クロージャ「x => x」の代わりにidentity関数を用いることもできます。

scala> List(1.some, 2.some, 3.some).traverse(identity)
res45: Option[List[Int]] = Some(List(1, 2, 3))
sequence

traverseメソッドを使うと「x => x」のクロージャやidentity関数を設定するのが若干冗長です。「M[N[A]]→N[M[A]]」の単純な変換は頻出なので、これを行う専用のメソッドが提供されています。これがsequenceメソッドです。

scala> List(1.some, 2.some, 3.some).sequence
res19: Option[List[Int]] = Some(List(1, 2, 3))

Option要素の中にNoneがある場合には、処理全体を自動的にNoneにしてくれます。こういったMonadicな処理を自動的にしてくれます。

scala> List(1.some, none, 3.some).sequence
res20: Option[List[Int]] = None

validationに適用

前節では、Optionを例にListのsequenceメソッドの一般的な使い方について説明しました。

Validationの場合も、基本的にはOptionの場合と同じなのですが、型パラメータ数が2になる点が異なります。sequenceメソッドは型パラメータ数1のApplicativeを前提としているので型パラメータ数の調整が必要になるわけです。この対処のためには色々な方法がありますが、ここでは新しい型VNTを定義する方法を採用します。

scala> type VNT[A] = ValidationNEL[Throwable, A]
defined type alias VNT

以下のようにList("1", "2", "3")に対して前回使用したvalidate関数をmapメソッドで適用すると「List(Success(1), Success(2), Success(3))」が得られます。考えるのは、この状態のデータをいかにしてSuccess(List(1, 2, 3))に変換するのかという問題です。

scala> List("1", "2", "3").map(validate)
res82: List[scalaz.Scalaz.ValidationNEL[Throwable,Int]] = List(Success(1), Success(2), Success(3))

traverseメソッドを使って変換すると以下のようになります。型パラメータでVNTとIntを指定する点が、Optionの場合と異なります。これはValidationの型パラメータ数が2なのに対して、traverseメソッドは型パラメータ数1を想定しているためで、その調整のために型パラメータを指定する必要があります。

scala> List(Success(1), Success(2), Success(3)).traverse[VNT, Int](x => x)
res46: VNT[List[Int]] = Success(List(1, 2, 3))

identity関数を使うと以下のようになります。

scala> List(Success(1), Success(2), Success(3)).traverse[VNT, Int](identity)
res47: VNT[List[Int]] = Success(List(1, 2, 3))
sequence

sequenceメソッドを使うと以下のようになります。型パラメータの指定は必要ですが、クロージャ「x -> x」やidentity関数の指定は必要ありません。

scala> List(Success(1), Success(2), Success(3)).sequence[VNT, Int]
res48: VNT[List[Int]] = Success(List(1, 2, 3))

要素にFailureが入っている場合は、自動的に変換結果はFailureになります。

scala> List(Success(1), new IllegalArgumentException("bad").failNel, Success(3)).sequence[VNT, Int]
res51: VNT[List[Int]] = Failure(NonEmptyList(java.lang.IllegalArgumentException: bad))

結果

以上の結果を課題の関数にまとめたものが以下になります。

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

末端の要素になるInt型は、処理自体に処理を与えないので型パラメータTにして汎用化すると以下になります。

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

ノート

前回「Validation (21) - traverse」で取り上げたtraverseメソッドとsequenceメソッドは、Monadicプログラミングで頻出の処理を簡単にさばいてくれるので、Monadicプログラミングをする以上必須のメソッドと思います。

おさらいすると、traverseメソッドは:

  • List[A]をValidationNEL[Throwable, List[B]]に変換
  • より汎用的には、M[A]をN[M[B]]に変換 (NはApplicative, MはTraverse)

します。sequenceメソッドは、List[A]をList[ValidationNEL[Throwable, B]]に変換したものがすでにある場合:

  • List[ValidationNEL[Throwable, B]]をValidationNEL[Throwable, List[B]]に変換
  • より汎用的には、M[N[B]]をN[M[B]]に変換 (NはApplicative, MはTraverse)

します。

fold系のメソッドを使って毎回スクラッチで書くこともできないはありませんが、事前に準備されている汎用部品を使う方が効率がよいのは言うまでもありません。

プログラミング戦略的には、最後にtraverseメソッドやsequenceメソッドがある前提で、ロジックを組み立てることができるのが非常に大きいです。Monadicプログラミングでは、「A→M[B]」の形の関数を軸にロジックを組み立てていきますが、ここからM[N[B]]をN[M[B]]にする処理が頻出することになります。この処理の捌き方が定型的に定まっていることがプログラミングの負担を大幅に軽減します。

Scalazを使用するメリットは多数ありますが、Scala本体に同等品がないということも含めて、実用的な観点でtraverseメソッドとsequenceメソッドの存在も非常に大きいと思います。

諸元

  • Scala 2.9.2
  • Scalaz 6.0.4

2012年6月1日金曜日

Scala Tips / Validation (21) - traverse

Validation (18) - 多重度0以上の部品」や「Validation (19) - 多重度1以上の部品」などで分かるように、Validationを操作する場合には、List[A]をList[ValidationNEL[Throwable, B]]を経由してValidationNEL[Throwable, List[B]]に変換する処理が頻出します。

Listなどのシーケンスに格納されている値をすべて検証後、アプリケーションが操作する型に変換して、すべての値の検証がパスした場合には、検証結果をシーケンスに入れて返してもらうという処理です。

この処理には、型クラスTraverseが提供するtraverseメソッドが非常に便利です。

今回はValidationの操作にtraverseメソッドを使用する方法についてみていきます。

課題

検証&値変換を行うvalidation関数があるとします。

def validate(a: String): ValidationNEL[Throwable, Int] = {
  import scala.util.control.Exception._
  allCatch either {
    a.toInt
  } flatMap {
    x => if (x >= 0) x.right
         else new IllegalArgumentException("less 0: " + x).left
  } fold (_.failNel, _.success)
}

この関数を用いて、以下の関数を作ります。

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

traverseの動作確認

Validationの応用に入る前に、traverseメソッドの基本的な使い方を確認しましょう。

traverseメソッドは、型クラスTraverseに対応するオブジェクト(型クラスTraverseの型クラスインスタンスを定義しているオブジェクト、以下Traverseオブジェクト)に付与されるメソッドで、指定された関数が生成する型クラスApplicativeに対応するオブジェクト(以下Applicativeオブジェクト)の中にTraverseオブジェクトをくるみます。

TraverseオブジェクトをM、ApplicativeオブジェクトをNとすると、M[A]に対してA→N[B]の関数を適用してN[M[B]]に変換する処理を行います。

この処理は以下の2つの処理を同時に行なっています。

  • A→B
  • M[_]→N[M[_]]

前者の「A→B」は普通のmapメソッドと同じです。

後者の「M[_]→N[M[_]]」がtraverseメソッドの肝で、「M[_]→M[N[_]]→N[M[_]]」というように、一度M[N[_]]の入れ子を作り、これを逆転させると考えると分かりやすいと思います。一般的に、TraverseオブジェクトもApplicativeオブジェクトもモナドであることが多いので、分かりやすく単純化した言い方をすると、2つのモナドの入れ子関係を逆転する処理を行います。

まとめるとtraverseメソッドは要素を写像しながら、2つのモナド(コンテナ)の入れ子関係を逆転する処理ということができます。

実際の動作を試してみましょう。

「List(1, 2, 3)」に対して「_.some」すなわち「x => Some(x)」を適用すると以下のように「Some(List(1, 2, 3))」が得られます。この場合、ListがTraverseオブジェクト、OptionがApplicativeオブジェクトです。

scala> List(1, 2, 3).traverse(_.some)
res36: Option[List[Int]] = Some(List(1, 2, 3))

単純にmapしただけだと以下のように「List(Some(1), Some(2), Some(3))」が得られます。traverseメソッドの場合は、同時にこのListとSomeをひっくり返すわけですね。

scala> List(1, 2, 3).map(_.some)
res39: List[Option[Int]] = List(Some(1), Some(2), Some(3))
モナディックな自動処理

traverseメソッドでは、モナドをひっくり返す際にモナディックな処理を行います。以下の例では、traverseメソッドに「0以上ならSome(x)、0未満ならNoneを返す」関数を指定しており、結果としてNoneが得られています。

scala> List(1, -1, 3).traverse(x => (x >= 0).option(x))
res40: Option[List[Int]] = None

この処理は、以下のようにmapメソッドの動作を考えると分かりやすいでしょう。

scala> List(1, -1, 3).map(x => (x >= 0).option(x))
res41: List[Option[Int]] = List(Some(1), None, Some(3))

「0以上ならSome(x)、0未満ならNoneを返す」関数をmapメソッドに適用すると、「List(Some(1), None, Some(3))」が得られます。

traverseメソッドでは、この結果からさらにモナドの入れ子を逆転させるわけですが、List内のOptionが一つでもNoneの場合は、入れ子を逆転させた結果がNoneになるわけです。

このように、一つでもNoneがあった場合は全体結果もNoneになるというのが、Optionのモナディックな振舞いです。この処理が自動的に行われるのが、Monadicプログラミングのキモとなるところです。定型処理はモナドの裏側で自動的に行うことで、やりたい処理のみの記述に専念できるわけですね。

traverseメソッドの処理も、このモナディックな振舞いによって定型的な処理が自動化されており、とても便利に使えます。traverseメソッドでは、適用する関数「A→N[B]」のNがApplicativeオブジェクトであることがモナディックな振舞いを担保しています。

Validationに適用

Validationは型パラメータ数が2であるため、型パラメータ数1の型パラメータを前提としているtraverseメソッドは、そのままの形では使えません。このギャップを解消するために、VNTという新しい型を追加します。

scala> type VNT[A] = ValidationNEL[Throwable, A]
defined type alias VNT

その上で、traverseメソッドに型パラメータとしてVNTとIntを指定して実行してみましょう。

以下のように無事、期待通りの処理が行われました。

scala> List("1", "2", "3").traverse[VNT, Int](validate)
res17: VNT[List[Int]] = Success(List(1, 2, 3))

エラーがあるデータに適用した場合は、Failureとなりエラー情報が記録されています。

scala> List("1", "a", "3").traverse[VNT, Int](validate)
res44: VNT[List[Int]] = Failure(NonEmptyList(java.lang.NumberFormatException: For input string: "a"))

結果

以上の処理を課題の関数にまとめたものが以下になります。

def f(xs: List[String]): ValidationNEL[Throwable, List[Int]] = {
  type VNT[A] = ValidationNEL[Throwable, A]
  xs.traverse[VNT, Int](validate)
}

ノート

Validationを使う場合の型パラメータについての話題です。

Validationは型パラメータ数が2つあるため、traverseメソッドを使う場合には注意が必要です。traverseメソッドは型パラメータ1のApplicativeを生成する関数を指定する必要があります。ValidationはApplicativeですが、型パラメータ数が2つであるために調整が必要になるわけです。

この調整は、Validationの型パラメータ数2のうちの1つを固定して、型パラメータ1の新しい型を定義してこれをtraverseメソッドに指定することで行います。

def f[T](a: List[ValidationNEL[Throwable, T]]): ValidationNEL[Throwable, List[T]] = {
  a.traverse[({type L[A] = ValidationNEL[Throwable, A]})#L, T](x => x)
}

よく使われているのは、LやAといったアルファベットの代わりにλやαといったギリシャ文字を使う方法です。ギリシャ文字を使うと何か難しいそうなことをやっているような感触を受けてしまいますが、この場合は普通のアルファベットを使うのと全く同じです。

def f[T](a: List[ValidationNEL[Throwable, T]]): ValidationNEL[Throwable, List[T]] = {
  a.traverse[({type λ[α] = ValidationNEL[Throwable, α]})#λ, T](x => x)
}

型パラメータの引数名としてTやA, Bは、クラスやメソッドの定義でよく使うので、メソッドの実装などで内部的に型を定義する場合にはλやαといったギリシャ文字を使うようにしておくと、名前の衝突が回避できます。これも一種のイディオムといえると思います。

VNT

「({type λ[α] = ValidationNEL[Throwable, α]})#λ」という型は、便利ですがプログラムの可読性が落ちるので、分りやすさを取る場合は新しい型を定義します。以下ではVNTという名前で型を定義しました。

def f[T](a: List[ValidationNEL[Throwable, T]]): ValidationNEL[Throwable, List[T]] = {
  type VNT[A] = ValidationNEL[Throwable, A]
  a.traverse[VNT, T](x => x)
}

先ほど説明したように、ギリシャ文字を使うことで名前の衝突を回避することができます。その場合には以下のようになります。

def validates[T[_]: Traverse, A, B](a: T[A], b: A => ValidationNEL[Throwable, B]): ValidationNEL[Throwable, T[B]] = {
  type VNT[α] = ValidationNEL[Throwable, α]
  a.traverse[VNT, B](b)
}
PartialApply

Scalazが用意しているPartialApplyを使う手もあります。その場合は以下のようになります。

def f[T](a: List[ValidationNEL[Throwable, T]]): ValidationNEL[Throwable, List[T]] = {
  a.traverse[PartialApply1Of2[ValidationNEL, Throwable]#Apply, T](x => x)
}

諸元

  • Scala 2.9.2
  • Scalaz 6.0.4