0

While investigating a bug today, I noticed that calling sumr on a stream with 50 (Int, Int) tuples never completes, but it does on a smaller stream. Calling .toList on the larger stream first completes as well.

Is this the intended behavior when calling sumr on a large stream? Does it not evaluate the stream to completion, or is something else causing this?

scala> val strSmall = Stream((1,1),(2,4),(3,9),(4,16),(5,25))
strSmall: scala.collection.immutable.Stream[(Int, Int)] = Stream((1,1), ?)

scala> val strBig = Stream((1,0), (1,0), (1,0), (1,0), (1,0), (1,0), (1,0), (1,0), (1,0), (1,0), (1,0), (1,0), (1,0), (1,0), (1,0), (1,0), (1,0), (1,0), (1,0), (1,0), (0,1), (1,0), (1,0), (1,0), (1,0), (0,1), (1,0), (1,0), (1,0), (1,0), (1,0), (1,0), (1,0), (1,0), (1,0), (1,0), (1,0), (1,0), (1,0), (1,0), (1,0), (1,0), (1,0), (1,0), (0,1), (1,0), (1,0), (1,0), (1,0), (1,0))
strBig: scala.collection.immutable.Stream[(Int, Int)] = Stream((1,0), ?)

scala> strSmall.sumr
res3: (Int, Int) = (15,55)

scala> strBig.toList.sumr
res4: (Int, Int) = (47,3)

scala> strBig.sumr
<!-- never completes -->
Ayush
  • 41,754
  • 51
  • 164
  • 239

1 Answers1

2

sumr is implemented in terms of foldRight:

 final def sumr(implicit A: Monoid[A]): A = F.foldRight(self, A.zero)(A.append)

foldRight is not always tail recursive, so you can overflow the stack if the collection is too long. See Why foldRight and reduceRight are NOT tail recursive? for some more discussion of when this is or isn't true.

Community
  • 1
  • 1
Rob Napier
  • 286,113
  • 34
  • 456
  • 610
  • I did initially suspect something like that might be going on, and even wrapped the call in a try/catch hoping to catch a stack overflow exception, but no exception was thrown. It seems to just continue without completing. – Ayush Dec 31 '13 at 22:39
  • 50 items does seem a very small size to fail from recursion. Have you tried replacing the sumr with the foldRight directly to start pealing away layers? Also, do you see any problem with suml? – Rob Napier Jan 01 '14 at 22:20