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