foldLeftを使ってfoldRightを実装すると大きなリストでもスタックオーバーフローが発生しなくなる

はじめに

『Scala関数型デザイン&プログラミング―Scalazコントリビューターによる関数型徹底ガイド』に表題のような文章を見つけ、少し興味を持ったので確認してみました。

まず、大きなリストを作成して、foldRightでスタックオーバーフローが発生することを確認します。

そして、foldLeftを使ったfoldRightでスタックオーバーフローが発生しないことを確認します。

大きなリストを作成して、foldRightでスタックオーバーフローが発生することを確認

リストの要素数が1000だとスタックオーバーフローが発生しないので、50000で確認しました。

リストの要素数が1000だとスタックオーバーフローになりませんが、

object Main extends App {
  import scala.{List => _, _}

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

  object List {
    def apply[A](as: A*): List[A] =
      if (as.isEmpty) Nil
      else Cons(as.head, apply(as.tail: _*))

    def foldRight[A,B](as: List[A], z: B)(f: (A, B) => B): B =
      as match {
        case Nil => z
        case Cons(x, xs) => f(x, foldRight(xs, z)(f))
      }

    @annotation.tailrec
    def foldLeft[A,B](l: List[A], z: B)(f: (B, A) => B): B = l match {
      case Nil => z
      case Cons(h,t) => foldLeft(t, f(z,h))(f)
    }

    def reverse[A](l: List[A]): List[A] = foldLeft(l, List[A]())((acc,h) => Cons(h,acc))

    def foldRightViaFoldLeft[A,B](l: List[A], z: B)(f: (A,B) => B): B =
      foldLeft(reverse(l), z)((b,a) => f(a,b))
  }

  val xs = List(1 to 1000: _*)
  val result = List.foldRight(xs, 0)(_ + _)
  println(result)
}

リストの要素数が50000だとスタックオーバーフローになってしまいます。

object Main extends App {
  import scala.{List => _, _}

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

  object List {
    def apply[A](as: A*): List[A] =
      if (as.isEmpty) Nil
      else Cons(as.head, apply(as.tail: _*))

    def foldRight[A,B](as: List[A], z: B)(f: (A, B) => B): B =
      as match {
        case Nil => z
        case Cons(x, xs) => f(x, foldRight(xs, z)(f))
      }

    @annotation.tailrec
    def foldLeft[A,B](l: List[A], z: B)(f: (B, A) => B): B = l match {
      case Nil => z
      case Cons(h,t) => foldLeft(t, f(z,h))(f)
    }

    def reverse[A](l: List[A]): List[A] = foldLeft(l, List[A]())((acc,h) => Cons(h,acc))

    def foldRightViaFoldLeft[A,B](l: List[A], z: B)(f: (A,B) => B): B =
      foldLeft(reverse(l), z)((b,a) => f(a,b))
  }

  val xs = List(1 to 50000: _*)
  val result = List.foldRight(xs, 0)(_ + _)
  println(result)
}

Exception in thread "main" java.lang.StackOverflowError
    at scala.collection.AbstractIterable.<init>(Iterable.scala:54)
    at scala.collection.AbstractSeq.<init>(Seq.scala:41)
    at scala.collection.immutable.Range.<init>(Range.scala:62)
    at scala.collection.immutable.Range$Inclusive.<init>(Range.scala:433)
    at scala.collection.immutable.Range$Inclusive.copy(Range.scala:436)
    at scala.collection.immutable.Range.drop(Range.scala:202)
    at scala.collection.immutable.Range.tail(Range.scala:229)
    at scala.collection.immutable.Range.tail(Range.scala:61)
    at Main$List$.apply(Main.scala:13)

そして、このスタックオーバーフローは今回確認したいスタックオーバーフローではありません。

後ろめたさはありますが、背に腹はかえられません、varを使って大きなリストを作成します。

object Main extends App {
  import scala.{List => _, _}

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

  object List {
    def apply[A](as: A*): List[A] =
      if (as.isEmpty) Nil
      else Cons(as.head, apply(as.tail: _*))

    def foldRight[A,B](as: List[A], z: B)(f: (A, B) => B): B =
      as match {
        case Nil => z
        case Cons(x, xs) => f(x, foldRight(xs, z)(f))
      }

    @annotation.tailrec
    def foldLeft[A,B](l: List[A], z: B)(f: (B, A) => B): B = l match {
      case Nil => z
      case Cons(h,t) => foldLeft(t, f(z,h))(f)
    }
  }

  var xs = List[Int]()
  1 to 50000 foreach { i =>
    xs = Cons(1, xs)
  }
  List.foldRight(xs, 0)(_ + _)
}

Exception in thread "main" java.lang.StackOverflowError
    at Main$List$.foldRight(Main.scala:18)

無事、確認できました。

foldLeftを使ったfoldRightでスタックオーバーフローが発生しないことを確認

末尾再帰なのだから当たり前だと言われてしまいそうですが、

object Main extends App {
  import scala.{List => _, _}

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

  object List {
    def apply[A](as: A*): List[A] =
      if (as.isEmpty) Nil
      else Cons(as.head, apply(as.tail: _*))

    def foldRight[A,B](as: List[A], z: B)(f: (A, B) => B): B =
      as match {
        case Nil => z
        case Cons(x, xs) => f(x, foldRight(xs, z)(f))
      }

    @annotation.tailrec
    def foldLeft[A,B](l: List[A], z: B)(f: (B, A) => B): B = l match {
      case Nil => z
      case Cons(h,t) => foldLeft(t, f(z,h))(f)
    }

    def reverse[A](l: List[A]): List[A] = foldLeft(l, List[A]())((acc,h) => Cons(h,acc))

    def foldRightViaFoldLeft[A,B](l: List[A], z: B)(f: (A,B) => B): B =
      foldLeft(reverse(l), z)((b,a) => f(a,b))
  }

  var xs = List[Int]()
  1 to 50000 foreach { i =>
    xs = Cons(1, xs)
  }
  val result = List.foldRightViaFoldLeft(xs, 0)(_ + _)
  println(result)
}

foldLeftを使ったfoldRightではスタックオーバーフローが発生しませんでした。

まとめ

foldLeftを使ったfoldRightでスタックオーバーフローが発生しないことを確認しました。

大きなリストを作成するところが主な内容になります。

参照URL

この記事を書く前に同じような記事がないか確認したところ、

Scala - トランポリン化でStackOverflowの回避 - Qiita

を見つけました。

varを使わずに大きなリストを作成することができるようです。すごい。