avoid foldRight stack over flow by using for loop

If you'd care to provide a suitable implementation, it is quite likely it would be accepted in place of the existing one.

On Mon, Apr 12, 2010 at 6:30 PM, calathus <calathus [at] gmail [dot] com> wrote:

Hi,
There is relatively small upper limit for foldRight to avoid stack over flow.
for instance,  following code will fail with stack over flow

(1 to 999999).toList.foldRight(0)(_ + _)

In particular, collection object will often contain much larger number
of elements, this problem will limit the usability of foldRight.
I decided not to use the method, and use for loop instead.
But if these library avoid recursion in the implementation of
foldRight, it would not have such problem and application will be more
declarative.

Are there any action for this?

nc

--
Daniel C. Sobral

I travel to the future all the time.

It is enough to make stack overflow to use just 3000 elements in my environment.

(1 to 3000).toList.foldRight(0)(_ + _)

this is practically very small limit.

nc

On Mon, Apr 12, 2010 at 2:30 PM, calathus wrote:
> Hi,
> There is relatively small upper limit for foldRight to avoid stack over flow.
> for instance,  following code will fail with stack over flow
>
> (1 to 999999).toList.foldRight(0)(_ + _)
>
> In particular, collection object will often contain much larger number
> of elements, this problem will limit the usability of foldRight.
> I decided not to use the method, and use for loop instead.
> But if these library avoid recursion in the implementation of
> foldRight, it would not have such problem and application will be more
> declarative.
>
> Are there any action for this?
>
> nc
>

On Mon, Apr 12, 2010 at 02:39:43PM -0700, calathus wrote:
> It is enough to make stack overflow to use just 3000 elements in my
> environment.
>
> (1 to 3000).toList.foldRight(0)(_ + _)

If you want you can use iterator's implementation, which memoizes and
reverses it so there's no issue.

scala> (1 to 1000000).iterator.foldRight(0)(_ + _)
res0: Int = 1784293664

It's not as simple as you think to do something about foldRight in
general.

On Mon, Apr 12, 2010 at 11:30 PM, calathus <calathus [at] gmail [dot] com> wrote:

Hi,
There is relatively small upper limit for foldRight to avoid stack over flow.
for instance,  following code will fail with stack over flow

(1 to 999999).toList.foldRight(0)(_ + _)

In particular, collection object will often contain much larger number
of elements, this problem will limit the usability of foldRight.
I decided not to use the method, and use for loop instead.

But a for loop corresponds to a foldLeft, not a foldRight. Why not use foldLeft?

-- Martin
 

But if these library avoid recursion in the implementation of
foldRight, it would not have such problem and application will be more
declarative.

Are there any action for this?

nc

On Mon, Apr 12, 2010 at 5:47 PM, Paul Phillips <paulp [at] improving [dot] org> wrote:

It's not as simple as you think to do something about foldRight in
general.

It looks pretty trivial to me, even if you want it to overflow the stack instead of the heap when the collection is infinte.  This should work in Iterator and Traversable and everything up to IndexedSeqOptimized or whatever it's called now (where it should do it with an accumulator).

def foldRight[B](z: B)(f: (a: A, b:B) => B) = {
  if (!hasDefiniteSize) ( if (hasNext) op(next(), foldRight(z)(op) else z )
  else {
    val memo = new ArrayBuffer[A]();
    memo ++= this
    memo.foldRight(z)(op)
  }
}

  --Rex