【Scala】foldとfoldLeftの違いを知る

はじめに

こんばんは！
突然ですが、 Scala における fold と foldLeft はほとんど同じものだ！と思っていませんか？
また、Scala の Option#fold メソッドを使って、何か不自然に思ったことはありませんか？

先に結論を述べますと、 fold メソッドと foldLeft メソッドは異なります（もちろん foldRight とも違いますよ！）。
「ちょっとだけ挙動に差が…」的な違いではなく、根本的に違います。

たまたま、 List#fold と List#foldLeft が（例外的に）似たような定義で、かつ（例外的に）似たような挙動をするため、誤った通説（全てのfold≒foldLeft）があったりなかったりするようです。少なくとも僕は、Scala を書くようになってからある一定の期間、全ての fold と foldLeft は同じものだと考えていました。

では、冒頭に上げた Option#fold を最初の例にとり、 fold の謎に迫っていきましょう。

いろいろな fold

Option#fold の定義は次のとおりです。

Option#fold

def fold[B](ifEmpty: ⇒ B)(f: (A) ⇒ B): B

Usage

val maybeMoney: Option[Int] = Some(1000)
val message = maybeMoney.fold("お金もってないよ！") { money =>
  s"お金${money}円あるよ！"
}

カリー化されていますね。値が Some か None かによって、別々の値に変換することができます。
パターンマッチや getOrElse と並んで使用頻度が高いメソッドですね。

さて、定義を見てみます。まず、第一引数の ifEmpty: => B は良いでしょう。 fold を foldLeft のエイリアスだと捉えても、Empty (None) ならば走査する対象がありませんからアキュームレータの初期値が返される、というのは予想通りの定義です。

では、第二引数の f: (A) => B はどうでしょうか？
もしあなたが fold を foldLeft のエイリアスだと考えているならば、不自然に感じるはずです（僕がそう感じたように！）。

このメソッドが foldLeft と等価ならば、そこにあるべきはずのアキュームレータがないのです。

Option#foldLeft (TraversableOnce#foldLeft)

def foldLeft[B](z: B)(op: (B, A) ⇒ B): B

これが、 Option#foldLeft の定義です。

もし、 Option#fold が、 Optionをリストのように走査して畳み込む ことを目的に用意されたメソッドならば、 foldLeft のように、第二引数に二項演算を取る必要があります。そうでなければ、一般的な畳み込みとは呼べません。

ではひょっとして Option#fold が特別なのでしょうか？
うーん、ひょっとしたらそうかも。じゃあ、今度は Either#fold も確認してみましょう。

Either#fold

def fold[X](fa: (A) ⇒ X, fb: (B) ⇒ X): X

Usage

val result: Either[Exception, Value] = possiblyFailingOperation()
val message = result.fold(
  ex => "Operation failed with " + ex,
  v => "Operation produced value: " + v
)

ナニソレ！意味ワカンナイ！
もはや foldLeft の面影すらない定義が出てきました。
第一引数は Either が左値 (Left) だった場合のマッピング関数、第二引数は右値 (Right) だった場合のマッピング関数のようですね。

さらに面白いことに、 Either には foldLeft や foldRight といったメソッドは用意されていません！
どうやら、 Scala における fold メソッドは、 foldLeft (foldl) や foldRight (foldr) とあまり関係ないみたいですね。

では、 Scala で定義されている fold メソッドたちは、一体なぜこのような定義になっているのでしょうか？

fold は Catamorphism

Catamorphism?

結論から書きますと、 Scala に用意されているいろいろな fold メソッドは、各種代数的データ型における Catamorphism です。
はて、そうすると当然 Catamorphism とは何かという話になりますね。
Catamorphism は圏論の概念であり、対応する日本語も（Wikipedia を見る限りでは）ないような単語です。
残念ながら僕は、圏論における Catamorphism について正確な説明をすることができません。
また、このような圏論のリテラシー（始対象、同型射、etc…）を持つ方は、Scalaのユーザ数に比べごく少数かと思います。
そこで、今回は Catamorphism がどのように Scala の fold として実装されているのか のみに焦点をあてて、 Scala の fold とは何かを探っていきましょう！

では早速ですが、Scala における fold メソッドの定義 がどのようなものなのか、見ていきましょう！

対象となるのは「代数的データ型」

Scala において fold が実装される可能性があるのは、代数的データ型 です。 Option や Either 、もちろん List (Cons リスト) も代数的データ型ですね。

※ 代数的データ型について詳しく説明をすると、それだけでブログ1本の文量になってしまうため、代数的データ型を知りたい！という方はぜひ有用な文献たちを参照ください！

一応、Option の定義を確認しておきますと。

Option

sealed abstract class Option[+A]
case final class Some[+A](val x : A) extends Option[A]
case object None extends Option[Nothing]

のような感じですね。
しかし、他の代数的データ型を紹介するたびに毎回この量のコードを貼るのは目に優しくないため、以降、上記のようなデータ型については次のように記述します。

Option[A] = None | Some(A)

Option を書くとこんな感じ。
Either についても確認しておきましょう！

Either[A,B] = Left(A) | Right(B)

こんな感じですね！

さて、Scala において fold を持っているのは代数的データ型、ということはわかりました。では、データ型と fold の定義の間には、どのような関係があるのでしょうか？

データ型によって実装される fold が変わる！

また結論から書きますと、 fold のメソッド定義はデータ型によって決定します。
実際に比べて見るのが一番早いので、まず Option#fold について見ていきましょー。

Option#fold

def fold[B](ifEmpty: ⇒ B)(f: (A) ⇒ B): B

この定義、登場２回目ですね！
では、Option のデータ型が Option[A] = None | Some(A) であることを前提に定義を確認してみます。

第一引数 (ifEmpty: => B) は、 None に対応する関数です。
レシーバの Option が None であるならば、この関数が適用され、B型の値が返されます。
None は値を持たないため、この関数には引数がありません（ここでは、Scala ではより一般的な "名前渡しパラメータ" として定義されていますね）。

第二引数 (f: (A) => B) は、 Some(A) に対応する関数です。
レシーバの Option が Some(A) ならば、この関数が適用され、B型の値が返されます。
Some(A) はA型の値を一つ持っています。なので、この関数は引数としてA型の値を一つ取ります。

つまり、型に定義されているデータ構築子の分だけ、それぞれに適用すべき関数をとり、その適用結果を返すのが Option#fold の定義です。

もう、パターンが見えてきたんじゃないでしょうか。次は Either を確認しましょう！

Either#fold

def fold[X](fa: (A) ⇒ X, fb: (B) ⇒ X): X

さて、先ほどは「イミワカンナイ！」だった Either#fold ですが… Either[A,B] = Left(A) | Right(B) というデータ型であることを念頭に置くと、その意味がわかってきます。

第一引数 (fa: (A) => X) は、 Left(A) に対応する関数です。
レシーバの Either が Left(A) であるならば、この関数が適用され、X型の値が返されます。
Left(A) はA型の値を一つ持っています。なので、この関数は引数としてA型の値を一つ取ります。

第二引数 (fb: (B) => X) は、 Right(B) に対応する関数です。
レシーバの Either が Right(B) ならば、この関数が適用され、X型の値が返されます。
Right(B) はB型の値を一つ持っています。なので、この関数は引数としてB型の値を一つ取ります。

イエス！もう見えてきたのではないでしょうか。
Scala の fold は、代数的データ型の各データ構築子に対し、それぞれ適用可能な関数を１つずつ引数に取り、実際の値 (SomeやNone, RightやLeftなど) によって適用する関数を振り分ける メソッドです！

簡単な対比表にしてみるとこんな感じです。

型名	データ構築子	foldの引数
Option[A]	None, Some(A)	(f: => X) ※2, (g: A => X)
Either[A, B]	Left(A), Right(B)	(fa: A => X), (fb: B => X)
コンスリスト List[A] ※1	Nil, Cons(A, List[A])	(f: => X) ※2, (g: A => (X => X))

※1 後述しますが、実際のScalaのListの実装は厳密な Catamorphism ではないため、この表の定義とは少々異なります。
※2 引数を取らず型Xの値を返す関数は、型Xの定数として置き換えて定義することも可能です。

では最後に PlayFramework の API で用意されている代数的データ型の JsResult について見てみましょう！

JsResult#fold

def fold[X](invalid: (Seq[(JsPath, Seq[ValidationError])]) ⇒ X, valid: (A) ⇒ X): X

JsResultのデータ型は次のとおりです。 JsResult[A] = JsError(Seq[(JsPath, Seq[ValidationError])]) | JsSuccess(A)

※ JsSuccessにはオプションでJsPathを持たせることもできます

予想通りですね！ 第一引数には JsError が、第二引数には JsSuccess が対応し、全てのデータ構築子に対する関数が用意されています。

例外: List#fold について

List#fold の定義は以下のとおりです。

List#fold

def fold[A1 >: A](z: A1)(op: (A1, A1) ⇒ A1): A1

List#fold については、今までの説明からすると例外的なメソッドと言えます。

まず List#fold は実のところ、より上位の TraversableOnce#fold で定義されています。つまり、List型の特有のメソッドではありません。
次に、Cons リストに Catamorphism を自然な形で適用すると foldRight 相当の関数が得られます。 一方、広く知られている通り、 List#fold は foldLeft と非常に近い働きをします。つまり List#fold は Cons リストに対する厳密な Catamorphism ではないことがわかります。(参考)
また、List#fold と List#foldLeftは、それぞれ走査対象が結合律を満たすかどうかでの使い分けが想定されているようです。（参考）

まとめ

• Scala における fold は foldLeft の単純な別名(エイリアス)ではありません。
• 一部の例外を除き、基本的に代数的データ型に対する Catamorphism です。
  • と、書いてしまうと難しく感じられますが、単純に、あるデータ型の各データ構築子に１対１に対応する関数を引数にとり、レシーバの実際の値に応じて処理をするものです。
  • たいていの代数的データ型においては、パターンマッチのように使えるから便利！
  • コンスリストのように、再帰的な構造を持つ代数的データ型にも定義できる！

Scala における fold メソッドが意味することがわかりました。またひとつ大人になった気がします。ではまた！

参考

• In what way is Scala's Option fold a catamorphism? - StackOverflow
• Catamorphism in Scala - Togetter
• Catamorphism - Wikipedia
• Fold (higher-order function) - Wikipedia
• 代数的データ型について - Speaker Deck