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