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__を使わずに大きなリストを作成することができるようです。すごい。