Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

List.foldRight throws StackOverflowError #2818

Closed
scabug opened this issue Dec 19, 2009 · 14 comments
Closed

List.foldRight throws StackOverflowError #2818

scabug opened this issue Dec 19, 2009 · 14 comments
Milestone

Comments

@scabug
Copy link

scabug commented Dec 19, 2009

List.foldRight is not tail recursive, so it throws StackOverflowError when called on a large list.

Example:

scala> (List.range(1, 1000000) :\ 0) (_ + _)
java.lang.StackOverflowError
        at scala.List.foldRight(List.scala:1079)
        at scala.List.foldRight(List.scala:1081)
        at scala.List.foldRight(List.scala:1081)
        at scala.List.foldRight(List.scala:1081)
        at scala.List.foldRight(List.scala:1081)
        at scala.List.foldRight(List.scala:1081)
        at scala.List.foldRight(List.scala:1081)
        at scala.List.foldRight(List.scala:1081)
        at scala.List.foldRig...
scala>

In fact, 10000 is enough on my system.

@scabug
Copy link
Author

scabug commented Dec 19, 2009

Imported From: https://issues.scala-lang.org/browse/SI-2818?orig=1
Reporter: NagMacFeegle (nagmacfeegle)
Assignee: @JamesIry

@scabug
Copy link
Author

scabug commented Dec 21, 2009

@hubertp said:
In r20248 I get something similar:

scala> (List.range(1, 1000000) :\ 0) (_ + _)
java.lang.StackOverflowError
	at scala.collection.LinearSeqLike$$class.foldRight(LinearSeqLike.scala:167)
	at scala.collection.immutable.List.foldRight(List.scala:46)
	at scala.collection.LinearSeqLike$$class.foldRight(LinearSeqLike.scala:168)
	at scala.collection.immutable.List.foldRight(List.scala:46)
	at scala.collection.LinearSeqLike$$class.foldRight(LinearSeqLike.scala:168)
	at scala.collection.immutable.List.foldRight(List.scala:46)
	at scala.collection.LinearSeqLike$$class.foldRight(LinearSeqLike.scala:168)
	at scala.collection.immutable.List.foldRight(List.scala:46)
	at scala.collection.LinearSeqLike$$class.foldRight(LinearSeqLike.scala:168)
	at scala.collection.immutable.List.foldRight(List.scala:46)
	at scala.collection.LinearSeqLike$$class.foldRight(LinearSeqLike.scala:168)
	at scala.collection.immutable.List.foldRight(List.scala:46)
	at scala.collection.LinearSeqLike$$class.foldRight(LinearSeqLike.scala:168)

@scabug
Copy link
Author

scabug commented Dec 21, 2009

@hubertp said:
This might be related to #1437

@scabug
Copy link
Author

scabug commented Dec 22, 2009

@lrytz said:
there is no straight-forward tail-recursive implementation.

@scabug
Copy link
Author

scabug commented Dec 31, 2009

johnconnor said:
May I suggest the following implementation: We perform the usual stack unrolling up to a point and if we reach a certain stack depth (STACK_DEPTH_LIMIT), we reverse the list (whatever is left of it) and appeal to the tail recursive foldLeft for assistance -- the stack is then unrolled and we have our answer.

def foldRight[B](z: B)(f: (A, B) => B): B = {
    val STACK_DEPTH_LIMIT = 100

    def revArgs[A1, A2, C](f: (A1, A2) => C): ((A2, A1) => C) =
      (x: A2, y: A1) => f (y, x)

    def aux(iterCnt: Int, ls: Lst[A]): B = ls match {
      case Nil => z
      case x :: xs => {
        if (iterCnt < STACK_DEPTH_LIMIT) {
          f(x, aux(iterCnt + 1, xs))
        }
        else {
          val revRest = ls reverse
          val g = revArgs(f)

          revRest.foldLeft(z)(g)
        }
      }
    }

    aux(0, this)
  }

@scabug
Copy link
Author

scabug commented Jan 2, 2010

NagMacFeegle (nagmacfeegle) said:
It really does not look very elegantly but I have not found a better solution.

The STACK_DEPTH_LIMIT should not be too big, because you never know where you are in the stack, but 100 seems reasonable.

Since List#reverse is linear in list size, as is foldLeft, it would probably make the implementation more elegant if "reverse" would always be used and the "small list" case would not be considered, without making it unreasonably slower.

@scabug
Copy link
Author

scabug commented Jan 5, 2010

@odersky said:
I think it would overcomplicate things too much. Let's leave it as it is.

@scabug
Copy link
Author

scabug commented Jan 8, 2013

Sean Parsons (seanparsons) said:
Following on from the discussion that has occurred here: https://groups.google.com/forum/#!topic/scala-internals/RrmfYQpTTfc/discussion

It seems sensible that List.foldRight can be implemented simply at virtually no penalty to performance (caliper based benchmarks linked in the discussion above) in the smaller cases if implemented as follows:

  override def foldRight[B](z: B)(op: (A, B) => B): B = {
    if (lengthCompare(10) < 0)  // MAX_DEPTH=10
      super.foldRight(z)(op)
    else
      reverse.foldLeft(z)((right, left) => op(left, right))
  }

This mitigates the case where a callee unwittingly does a foldRight on a type with the signature of Seq[User] for example which is actually a List.

@scabug
Copy link
Author

scabug commented Jan 8, 2013

Sean Parsons (seanparsons) said:
The above implementation is an adapted version of foldAlternative4 from the scala-internals discussion, with the adapted version tested minimally against the 2.10.x branch with a 20,000 item List.

@scabug
Copy link
Author

scabug commented Jan 23, 2013

@Blaisorblade said:
Sean, I've marked this ticket as due for 2.10.1-RC1 to hopefully get new attention to it. But I'd recommend to submit a pull request, it seems this time it's going to be accepted. But you (somebody) needs to:

  • add some test case (you have a minimal one, if that fails now that's good)
  • possibly, check other variations of the same bug (like reduceRight). And what about LinearSeqOptimized.fold/reduceRight? I see your point on not touching Stream, but LinearSeqOptimized is implemented by other classes, so it should also be addressed.
    If some broken use cases are left, please comment on foldRight should be documented to be unusable on long lists (if it's not fixed) #6922 so that they're documented.

@scabug
Copy link
Author

scabug commented Jan 29, 2013

@adriaanm said:
without further activity on this ticket this week, I'm afraid it'll have to slip to 2.10.2

@scabug
Copy link
Author

scabug commented Jan 31, 2013

@JamesIry said:
scala/scala#2026

@scabug scabug closed this as completed Feb 1, 2013
@scabug
Copy link
Author

scabug commented Aug 26, 2013

@SethTisue said:
there is further discussion in #3295

@scabug
Copy link
Author

scabug commented Aug 26, 2013

@Blaisorblade said:
I just marked #3295 as duplicate :-).

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant