Details

    • Type: Bug Bug
    • Status: Closed
    • Priority: Major Major
    • Resolution: Duplicate
    • Affects Version/s: None
    • Fix Version/s: None
    • Component/s: Misc Library
    • Labels:
      None

      Description

      Is there a good reason not to implement l.foldRight(z)(f) as l.reverse.foldLeft(z)(flip(f)), or some variation? This would avoid the stack overflow that results when using foldRight with large sequences. As it is implemented, the function is not very useful except for toy examples.

        Issue Links

          Activity

          Hide
          Ben Wing added a comment - - edited

          I'm going to second Paul Chiusano here. I just got bitten by this problem, which turned out to be in a library I was using. Debugging issues like this are difficult in large-scale code because Java cuts off the bottom stack frames, so you can't even see which code triggered the call to foldRight.

          I strongly believe we should either

          (1) preferably, fix this issue as Paul C. proposed;
          (2) deprecate the function and all other non-tail-recursive functions;
          (3) issue a clear warning at compile time about stack overflow problems when the function is encountered;
          (4) provide a "safeFoldRight" function that won't trigger stack overflows, and similarly for other dangerous functions.

          At the very least, clearly document functions that aren't stack-safe, and indicate how to avoid the issue (e.g. through reverse.foldLeft).

          In reality, although Martin may personally have a clear idea which functions are and aren't tail-recursively-safe, the average Scala programmer has little or no idea. As a simple example, I verified experimentally that appending to the end of a very large list does not cause a stack overflow – but how could I possibly know that? My intuition tells me that the most straightforward implementation will be recursive in a non tail-recursive way. In general, programmers should not have to be aware of implementation details like this, and on top of this, currently there's no documentation as to which functions are stack-safe and which ones aren't.

          BTW, I see that others have run into this same issue:

          http://oldfashionedsoftware.com/2009/07/10/scala-code-review-foldleft-and-foldright/

          http://stackoverflow.com/questions/4085118/why-foldright-and-reduceright-are-not-tail-recursive

          http://www.scala-lang.org/node/5947

          Show
          Ben Wing added a comment - - edited I'm going to second Paul Chiusano here. I just got bitten by this problem, which turned out to be in a library I was using. Debugging issues like this are difficult in large-scale code because Java cuts off the bottom stack frames, so you can't even see which code triggered the call to foldRight. I strongly believe we should either (1) preferably, fix this issue as Paul C. proposed; (2) deprecate the function and all other non-tail-recursive functions; (3) issue a clear warning at compile time about stack overflow problems when the function is encountered; (4) provide a "safeFoldRight" function that won't trigger stack overflows, and similarly for other dangerous functions. At the very least, clearly document functions that aren't stack-safe, and indicate how to avoid the issue (e.g. through reverse.foldLeft). In reality, although Martin may personally have a clear idea which functions are and aren't tail-recursively-safe, the average Scala programmer has little or no idea. As a simple example, I verified experimentally that appending to the end of a very large list does not cause a stack overflow – but how could I possibly know that? My intuition tells me that the most straightforward implementation will be recursive in a non tail-recursive way. In general, programmers should not have to be aware of implementation details like this, and on top of this, currently there's no documentation as to which functions are stack-safe and which ones aren't. BTW, I see that others have run into this same issue: http://oldfashionedsoftware.com/2009/07/10/scala-code-review-foldleft-and-foldright/ http://stackoverflow.com/questions/4085118/why-foldright-and-reduceright-are-not-tail-recursive http://www.scala-lang.org/node/5947
          Hide
          Paul Phillips added a comment -

          Given the status and comment history of this ticket, you probably need to express your view on one of the mailing lists to obtain any result.

          Show
          Paul Phillips added a comment - Given the status and comment history of this ticket, you probably need to express your view on one of the mailing lists to obtain any result.
          Hide
          Ben Wing added a comment -

          OK thanks, Paul.

          Show
          Ben Wing added a comment - OK thanks, Paul.
          Hide
          Paul Phillips added a comment -

          For the record, SI-6543 gives us an example of the scala compiler blowing the stack via foldRight.

          Show
          Paul Phillips added a comment - For the record, SI-6543 gives us an example of the scala compiler blowing the stack via foldRight.
          Hide
          Seth Tisue added a comment -

          duplicate of SI-2818 which was fixed in 2.10.1

          Show
          Seth Tisue added a comment - duplicate of SI-2818 which was fixed in 2.10.1

            People

            • Assignee:
              Unassigned
              Reporter:
              Paul Chiusano
              TracCC:
              Johannes Rudolph, Paul Phillips, Seth Tisue
            • Votes:
              0 Vote for this issue
              Watchers:
              8 Start watching this issue

              Dates

              • Created:
                Updated:
                Resolved:

                Development