なぜfoldRightが美しいのか

エンジニアリンググループの冨岡です。

私は最近関数型プログラミングにハマっていて、社内でFP in Scala (訳書)の輪読会を主催するなどして関数型やScalaが好きな人を増やす活動をしています。

この輪読会ですが、本自体の素晴らしさもあって未だに参加者７人が誰一人脱落することなく読み進めています。現在８章と折返し地点なのですが、これまでの章で十分に訓練された私たち参加者は、（説明の都合上）副作用を起こす処理が教科書に出てこようものなら大ブーイング。教科書の解法を確認しては「美しい！」「エレガントだ！」と盛り上がりながら読み進めるようになりました。

中でもfoldRightは大人気で、登場のたびに場を盛り上げてくれます。この記事では、このfoldRightがなぜ美しいのかを解説します。

foldLeft / foldRight

まずは、似た処理であるfoldLeft / foldRightとはなにか、簡単に説明します。

trait List[+A]について、foldLeftは以下のように初期値としてのBから始まり、Listの左の要素から順に op: (B, A) => Bを再帰的に適用し、最終的なBを返却します。

一方foldRightは、Listの右の要素から順に、op: (A, B) => Bを再帰的に適用し、最終的なBを返却します。

opの引数A, Bの順番が、foldLeftとfoldRightで逆になっていますが、このような図を考えると直感的でわかりやすいですね。

実装の違い

一見この２つのメソッドは、それぞれ単に処理する順番が違うだけ、それ以上でもそれ以下でもないように思えます。本当にそうでしょうか。

それぞれの実装を考えるために、まずは自分でListを定義してみましょう。

sealed trait List[+A]
case class Cons[A](head: A, tail: List[A]) extends List[A]
case object Nil extends List[Nothing]

foldLeftはこんな感じの実装になると想像できます。

sealed trait List[+A] {

  def foldLeft[B](z: B)(op: (B, A) => B): B =
    this match {
      case Nil => z
      case Cons(head, tail) => tail.foldLeft(op(z, head))(op)
    }

}

foldRightはこんな感じでしょうか。

sealed trait List[+A] {

  def foldRight[B](z: B)(op: (A, B) => B): B =
    this match {
      case Nil => z
      case Cons(head, tail) => op(head, tail.foldRight(z)(op))
    }

}

val list = Cons(1, Cons(2, Cons(3, Nil)))
list.foldLeft(0)(_ + _) // 6
list.foldRight(0)(_ + _) // 6

良さそうに見えます。

しかし、この素朴なfoldRightの実装には落とし穴があります。foldLeftは末尾再帰ですが、foldRightはそうでないため、長いListの場合にjava.lang.StackOverflowErrorの原因になります。

@tailrec アノテーションにより foldRight が末尾再帰ではないことが警告されるの図

なお最近のScalaであれば、標準ライブラリのList.foldRightはスタックセーフな実装になっています。

では、このように素朴な実装でスタックオーバーフローを引き起こすfoldRightが、なぜ美しいのでしょうか。

foldLeft を使って他のメソッドを実装する

純粋関数の魅力の一つは、composabilityです。副作用を起こさない関数は他の関数と組み合わせることによって、別の関数を安全・簡潔に定義することができます。(注: 関数とメソッドは厳密には別の概念ですが、ここでは純粋であり合成可能なことが重要なのでこの差を無視します)

では、foldLeftを使って、mapを実装してみましょう。

sealed trait List[+A] {

  def map[B](f: A => B): List[B] =
    foldLeft(Nil: List[B])((acc, a) => ???)

}

この???を埋められるでしょうか。acc :+ f(a)というような、リストの末尾に項目を追加する処理が必要そうです。しかし、immutableなListの末尾に項目を追加するにはリストの長さnに対してO(n)の計算量が必要になります。これがfoldLeftの中で再帰的に行われるとなるとO()の計算量となり非常に効率の悪い処理となってしまいます。(f(a)の計算はnに無関係な定数時間で計算できるとします)

foldLeftで現実的な実装をするとなると以下のような感じでしょうか。

sealed trait List[+A] {

  def map[B](f: A => B): List[B] =
    foldLeft(Nil: List[B])((acc, a) => Cons.apply(f(a), acc)).reverse

  def reverse: List[A] =
    foldLeft(Nil: List[A])((acc, a) => Cons.apply(a, acc))

}

あまり直感的ではありませんね。

foldRightを使って他のメソッドを実装する

今度はfoldRightを使ってmapを実装してみましょう。

sealed trait List[+A] {

  def map[B](f: A => B): List[B] =
    foldRight(Nil: List[B])((a, acc) => Cons(f(a), acc))

}

右の要素から順に、fを適用した結果をheadに追加していく、非常に素直な実装になっています。 Cons(f(a), acc)はO(1)の計算量のため、全体でもリストを走査する分のO(n)の処理となります。美しい上に、効率的です。

同様に、filterや、２つのリストを連結するappendといったメソッドも、foldRightを使ってエレガントに実装することが可能です。

sealed trait List[+A] {

  def filter(f: A => Boolean): List[A] =
    foldRight(Nil: List[A])((a, acc) => if (f(a)) Cons(a, acc) else acc)

  def append[B >: A](that: List[B]): List[B] =
    foldRight(that)(Cons.apply)

}

美しいですね！

これが何を意味するのか

この２つのメソッドの違いはいったい何を意味するのでしょうか。

これを確認するために、データ構造の形に注目してみましょう。 immutableなListは以下のように、長いListが、末尾により短いListを保持する形になっています。

Listを新しく作成するときは、immutableであるために以下のように最も短いリスト(Nil)から順に、長いListを作る必要があります。

これが、foldRightの畳み込み処理の順番なのです。あるListから新しいListを作るmapやfilterといった操作をfoldRightを使うことで素直に書けるのは、foldRightがListの作成時と同じ順番で値を処理するためです。逆に、foldLeftは、最後に追加された要素から順番に処理していきます。QueueとStackの関係に似ているかもしれませんね。

言い換えると、immutableなデータ構造に関して、foldRightの処理順は"右から左"よりも寧ろ、"内側から外側"に処理すると考えられます。これがデータ構造にとてもよくマッチして美しく再利用しやすい処理になるのです。

まとめ

foldLeft / foldRightの対比から、foldRightの美しさについて解説しました。

• foldLeftとfoldRightは似ているようで性質の異なる関数である
• foldRightはimmutableな再帰的データ構造によく馴染む美しい関数である

この記事を見てfoldRightが好きになったという方がいたら是非一緒に畳み込まれましょう！