Infinite streams in Scala

Question

Say I have a function, for example the old favourite

def factorial(n:Int) = (BigInt(1) /: (1 to n)) (_*_)

Now I want to find the biggest value of n for which factorial(n) fits in a Long. I could do

(1 to 100) takeWhile (factorial(_) <= Long.MaxValue) last

This works, but the 100 is an arbitrary large number; what I really want on the left hand side is an infinite stream that keeps generating higher numbers until the takeWhile condition is met.

I've come up with

val s = Stream.continually(1).zipWithIndex.map(p => p._1 + p._2)

but is there a better way?

(I'm also aware I could get a solution recursively but that's not what I'm looking for.)

Roxanneroxburgh

Answer 1

Stream.from(1)

creates a stream starting from 1 and incrementing by 1. It's all in the API docs.

Merimerida

Stream is deprecated since 2.13.0. Use LazyList instead. So this would be LazyList.from(1). – Insusceptible

Answer 2

A Solution Using Iterators

You can also use an Iterator instead of a Stream. The Stream keeps references of all computed values. So if you plan to visit each value only once, an iterator is a more efficient approach. The downside of the iterator is its mutability, though.

There are some nice convenience methods for creating Iterators defined on its companion object.

Edit

Unfortunately there's no short (library supported) way I know of to achieve something like

Stream.from(1) takeWhile (factorial(_) <= Long.MaxValue) last

The approach I take to advance an Iterator for a certain number of elements is drop(n: Int) or dropWhile:

Iterator.from(1).dropWhile( factorial(_) <= Long.MaxValue).next - 1

The - 1 works for this special purpose but is not a general solution. But it should be no problem to implement a last method on an Iterator using pimp my library. The problem is taking the last element of an infinite Iterator could be problematic. So it should be implemented as method like lastWith integrating the takeWhile.

An ugly workaround can be done using sliding, which is implemented for Iterator:

scala> Iterator.from(1).sliding(2).dropWhile(_.tail.head < 10).next.head
res12: Int = 9

Sparing

I'm wondering what the equivalent for Iterator would be of Stream.from(1) takeWhile (factorial(_) <= Long.MaxValue) last, to give the answer 20? – Roxanneroxburgh

Answer 3

as @ziggystar pointed out, Streams keeps the list of previously computed values in memory, so using Iterator is a great improvment.

to further improve the answer, I would argue that "infinite streams", are usually computed (or can be computed) based on pre-computed values. if this is the case (and in your factorial stream it definately is), I would suggest using Iterator.iterate instead.

would look roughly like this:

scala> val it = Iterator.iterate((1,BigInt(1))){case (i,f) => (i+1,f*(i+1))}
it: Iterator[(Int, scala.math.BigInt)] = non-empty iterator

then, you could do something like:

scala> it.find(_._2 >= Long.MaxValue).map(_._1).get - 1
res0: Int = 22

or use @ziggystar sliding solution...

another easy example that comes to mind, would be fibonacci numbers:

scala> val it = Iterator.iterate((1,1)){case (a,b) => (b,a+b)}.map(_._1)
it: Iterator[Int] = non-empty iterator

in these cases, your'e not computing your new element from scratch every time, but rather do an O(1) work for every new element, which would improve your running time even more.

Exclusive

Answer 4

The original "factorial" function is not optimal, since factorials are computed from scratch every time. The simplest/immutable implementation using memoization is like this:

val f : Stream[BigInt] = 1 #:: (Stream.from(1) zip f).map { case (x,y) => x * y }

And now, the answer can be computed like this:

println( "count: " + (f takeWhile (_<Long.MaxValue)).length )

Whatley

Answer 5

The following variant does not test the current, but the next integer, in order to find and return the last valid number:

Iterator.from(1).find(i => factorial(i+1) > Long.MaxValue).get

Using .get here is acceptable, since find on an infinite sequence will never return None.

Taurus