【Scala】foldLeftとfoldRightのしくみ

はじめに

こんにちは！
Scala における強力な高階関数の foldLeft と foldRight は、 Traversable (走査可能なもの) をそれぞれ左右から走査して畳み込む機能を有しています。最もよく知られた高階関数の一つですね。
とても便利な foldLeft と foldRight ですが、普段つかっている時には「なぜ左から右へ走査できるのか」「なぜ右から左へ走査できるのか」などはあまり考えませんよね。今回はそのあたりをすこし掘り下げてみたいと思います。

※ 今回は、foldLeft と foldRight について詳しく説明します。 fold と foldLeft/foldRight の違い について知りたい方はこちらの記事をご参照ください。

foldLeft と foldRight の概要

畳み込み関数の foldLeft, foldRight にはそれぞれ次のような特徴があります。

利用方法はとても簡単で、カリー化された第一引数にアキュームレータの初期値を渡し、第二引数に関数を渡します。

List(1, 2, 3, 4).foldLeft(0) { (acc, x) => acc + x } // -> 10
"abcd".foldRight(Nil : List[Int]) { (x, acc) => x :: acc } // -> List(97, 98, 99, 100)

コレクションAPIに定義されているほとんどのメソッドは、 foldLeft か foldRight を用いて実装することができます。上記の foldLeft のコード例などは、 sum (総和) 関数そのものですね。

さて、それぞれの特徴を比較すると真っ先に目につくのが、foldLeft はスタックセーフな高階関数で、foldRight はそうではない、という点だと思います。それじゃあ、 foldRight って何のためにあるのでしょうか。

*1 見かけ上の走査方向
*2 解説を簡潔にするため、本稿ではこのように扱います。例外についてはまとめの項をご参照ください。
*3 リストの ++ 演算には線形時間が必要なためです。対して、 :: 演算は定数時間で終了します。
*4 要素数に比例してコールスタックを消費するためです。標準的な設定のJVMでは約７万スタックほどが限界と言われています。

foldRight

foldRight さんは、右から来たものを左へ受け流すタイプの高階関数です。
Leftさんと違ってスタックセーフではなく、スタックオーバーフローを起こしてしまうこともあります。

あれ、でも末尾再帰関数なら、@tailrec による最適化でスタックセーフにできるはずでは？
ということは、高階関数 foldRight は末尾再帰ではないのでしょうか？

// LinearSeqOptimized.scala 

// List[A]
def foldRight[B](zero: B)(f: (A, B) => B): B =
  if (this.isEmpty) zero
  else f(head, tail.foldRight(zero)(f))

どうやら末尾再帰ではないみたいですね。foldRight は

1. 自身が空の場合 → zero (アキュームレータの初期値) を返す
2. 自身が要素を持っている場合 → 関数 f の適用結果を返す

という関数です。 foldRight は関数 f の適用結果、または zero を返します。
f は f(先頭要素, 残りの要素.foldRight(zero)(f)) という形で呼び出されます。

引数値に foldRight が出てきましたね。先ほどお話した通り、 foldRight は関数 f の適用結果または zero を返します。とはいえ、 zero が返されるのはリストの終端にたどり着いた場合だけなので、要素が続くかぎりは関数 f の適用結果が帰ります。

つまり、次のように関数 f を適用しようとすると…

f(head, tail.foldRight(zero)(f))

引数に渡す tail.foldRight(zero)(f) が未評価なので、これを評価しようとします。
foldRight が呼びだされた結果、（tail の要素のが空でない限りは）関数 f の適用結果が帰ります。

これは展開すると次のようになりますね。

f(head, f(tail.head, tail.tail.foldRight(zero)(f)))

さて、入れ子になった2つめの f の中にも foldRight の呼び出しがあります。
そしてリストが続く限り、前例と同じように、 foldRight は f の適用で置き換えられます。

f(..., f(..., f(..., f(..., f(..., f(..., tail.foldRight(zero)(f)))))))

そして、リストの終端にたどり着いた時、foldRight は zero で置き換えられます。

f(..., f(..., f(..., f(..., f(..., f(..., zero))))))

さて、これで式全体を評価するために必要な要素が全てそろいました。
一番外側の f を評価するためには、一つ内側の f の結果が必要です。その結果が引数に渡す値になっていますからね。
そして一つ内側の f の評価にはさらに内側の f が、さらに内側の f にはさらにさらに内側の… となり、結果的には一番内側の f から順番に評価していくことになります。

先ほどの例が、 List(1,2,3,4,5,6).foldRight(zero)(f) の展開結果だったとしましょうか。

f(1, f(2, f(3, f(4, f(5, f(6, zero))))))

そうすると、こんなかんじです。当然ながら、一番内側の f から順番に評価されていきます。

ここで、もし f が f(x, acc) = x + acc で、zero が 0 なのだとすれば…

// f(x, acc) = x + acc
f(1, f(2, f(3, f(4, f(5, f(6, 0))))))
f(1, f(2, f(3, f(4, f(5, 6)))))
f(1, f(2, f(3, f(4, 11))))
f(1, f(2, f(3, 15)))
f(1, f(2, 18))
f(1, 20)
21

こうですね。右から順番に足し算の f が評価されて和が求まりました。

うーん、なんか、いまいちピンとこないですよね。わざわざ右から足していく意味もよくわからんし。
では f(x, acc) = (x * 1.5) :: acc で、 zero が Nil : List[Double] ならどうでしょうか。

// f(x, acc) = (x * 1.5) :: acc
f(1, f(2, f(3, f(4, f(5, f(6, Nil))))))
f(1, f(2, f(3, f(4, f(5, List(9.0))))))
f(1, f(2, f(3, f(4, List(7.5, 9.0)))))
f(1, f(2, f(3, List(6.0, 7.5, 9.0))))
f(1, f(2, List(4.5, 6.0, 7.5, 9.0)))
f(1, List(3.0, 4.5, 6.0, 7.5, 9.0))
List(1.5, 3.0, 4.5, 6.0, 7.5, 9.0)

おお、先頭要素への追加が連続してますね。これなら全体でO(n)ですみそうです。
ところで今回は (x * 1.5) という計算でしたが、これを g(x) としておけば…

List(g(1), g(2), g(3), g(4), g(5), g(6))

ですよね。そしてふと思ったんですが、これって map ですよね。

List(1,2,3,4,5,6).map(g) // -> List(g(1), g(2), g(3), g(4), g(5), g(6))

map は、リスト(対象)を別のリスト(対象)に変換し、結果値として別のリストを返すメソッドでした。
このように、foldRight は 結果値としてリストを生成したい場合 に使うのが適しています。

その具体的な理由は、ちょっと突っ込んだ話になりますが、foldRight が展開された f の再帰呼び出しの式が連結リストの生成式と全く同じ形を持っているためです。

// zero = Nil
// f(x, acc) = Cons(x, acc) /* Scala API では :: */
f(1, f(2, f(3, f(4, f(5, f(6, Nil))))))
Cons(1, Cons(2, Cons(3, Cons(4, Cons(5, Cons(6, Nil)))))) 
::(1, ::(2, ::(3, ::(4, ::(5, ::(6, Nil))))))
1 :: 2 :: 3 :: 4 :: 5 :: 6 :: Nil // *5

よくよく見れば、見慣れた形ですね！

*5 ここで実際に呼びだされているのは List#::(head) です。このメソッドは単純に ::(head, tail) をラップしています。

foldLeft

foldLeft は、左から右に走査します。こっちはシンプルな末尾再帰関数なので、foldRight ほど難しくありません。

// List[A]
@tailrec def foldLeft[B](zero: B)(f: (B, A) => B): B =
  if (this.isEmpty) zero
  else tail.foldLeft(f(zero, head))(f)

この定義によれば、 foldLeft は

1. 自身が空の場合 → zero (アキュームレータの初期値) を返す
2. 自身が要素を持っている場合 → foldLeft を再帰的に呼び出す

というような関数ですね。
ぜひ注目して欲しいのは、 foldRight と違って自身を再帰的に呼び出している点、そしてその際に、自身の第一引数 zero を f の適用結果で逐次更新していく点です。foldRight では f(x, acc) の第二引数 acc に次の foldRight 呼び出しの結果値をあてがっていったのに対し、 foldLeft では foldLeft(zero)(f) の第一引数 zero を f の適用結果で逐次更新していくことになります。
このことが大きな違いとして現れるのは、評価順です。関数の構造だけをみると、foldLeft と foldRight はとても似ています。自身が空リストの場合は zero を返す処理などは、全く同じです。しかし、そうでなかった時に再帰的に呼び出す関数 (foldLeft では foldLeft, foldRight では f) の引数として評価される関数 (foldLeft では f , foldRight では foldRight) の性質が異なります。

foldLeft の再起呼び出しのために評価が必要な f(zero, head) は foldLeft の再帰呼び出し時点で評価する (=関数を処理する) ことができます。

// f(z, a) = z + a
// List(1,2,3).foldLeft(0)(f)
tail.foldLeft(f(0, 1))(f)           // tail == List(2, 3)
tail.foldLeft(1)(f)                 // 新たな zero として評価結果の 1 を渡す
tail.tail.foldLeft(f(1, 2))(f)      // tail.tail == List(3)
tail.tail.foldLeft(3)(f)            // 新たな zero として 3 を渡す
tail.tail.tail.foldLeft(f(3, 3))(f) // tail.tail.tail == Nil
tail.tail.tail.foldLeft(6)(f)       // 新たな zero として 6 を渡す
6                                   // 自身が空リストの場合の foldLeft は zero を返す

f は逐次評価可能な関数のため、 foldRight の時と違い、再起呼び出しが一つ深くなるごとに逐次的に f を評価しています。

おさらいになりますが、foldRight の呼び出しは、f(head, tail.foldRight(zero)(f)) に置き換えられます。このため、foldRight は事実上 f の再帰呼び出しと考えられます。そして、先ほどお話したとおり、この f を評価するためには、第二引数に渡すための tail.foldRight(zero)(f) の評価を済ませておく必要があります。しかし、この foldRight もさらに f(head, tail.foldRight(zero)(f)) へと置き換えられてしまします。 この置き換えは、最終的に自身が空リストになり、 foldRight が zero を返すその瞬間まで続けられます。

// foldRight
f(..., f(..., f(..., f(..., f(..., f(..., tail.foldRight(zero)(f)))))))

このように、foldRight の場合は f の評価よりも先に式全体が完成します。
一方、foldLeft では再起呼び出しのたび逐次的に f を評価していきます。
このため、foldLeft と foldRight はどちらも先頭要素から順にリストを走査しているにもかかわらず、foldLeft と foldRightでは f の適用順が真逆になっているのです。

foldLeft の実装

閑話休題！（2015/09/26 追記: “閑話休題”の意味をはき違えておりました…「ところで！」のような意味だと思っていました）
上例に上げた foldLeft は @tailrec によって最適化される末尾再帰の高階関数です。末尾再帰関数に @tailrec をつけておくと、コンパイラがコールスタックを消費しないように最適化してくれるため、私たちはスタックオーバーフローに怯えずにすみます。

この foldLeft ですが、実際の Scala ではコンパイラに頼ることなくコードレベルで最適化されています。

// LinearSeqOptimized.scala 

// List[A]
def foldLeft[B](z: B)(f: (B, A) => B): B = {
  var acc = z
  var these = this
  while (!these.isEmpty) {
    acc = f(acc, these.head)
    these = these.tail
  }
  acc
}

イミュータブルな List 型の実装に while や var が出てきて、ちょっとびっくりしたでしょうか？
Scala には、こんな感じで 計算効率がよい手続き型の処理を、関数型パラダイムのインターフェイスで隠蔽 している箇所がいくつもあります。関数型は非常に強力なパラダイムですが、その理念が必ずしも現実的な計算時間に収まるとは限りません。そのような場合には、内部では効率のよい手続き型のロジックを実装し、外部には関数型のインターフェイスを公開することで、言語のパラダイムを破壊することなく問題を解決することができます。
これが、Scala という言語が“手続き型でも処理を記述できる”ことによる本当の強みと言えるかもしれません。

まとめ

• foldLeft は、リストを左から右へ畳み込む高階関数です。
  • スタックセーフです。
  • リストは先頭要素から順に走査されます。
  • foldLeft は自身を再帰呼び出しします。その際に、引数にとった関数 f を逐次的に評価していきます。
  • 結果として 左 → 右 の順に f が適用されていきます。
  • 連結リストなどの再帰的データ構造の生成を行わないのであれば、foldLeft が適している可能性が高いです。
• foldRight は、リストを右から左へ畳み込む高階関数です。
  • 基本的にスタックセーフではありません。(※ reverse.foldLeft で実装されているものを除く）
  • リストは先頭要素から順に走査されます。
  • foldRight は自身を再帰的に呼び出しますが、展開すると f の呼び出しに置き換えられます。
  • そのため、展開していくと最終的に f が再帰的に呼びだされた全体式が得られます。
  • 式が完成してから f の評価が始まります。
  • 結果として 左 ← 右 の方向に f が適用されていきます。
  • 連結リストなどの再帰的データ構造の生成を行う場合には、foldRight が適しています。

foldRight を適切なタイミングで使えるひとってカッコイイと思いますよ！ではまた！

参考

• TraversableOnce - Scala Standard Library
• Higher order functions - LYAHFGG