Long Ranges in Scala

So, following on from yesterday’s prime-factoring annoyance; a more basic requirement: How to iterate from 1 to ~10^17? (i.e. close to the limit of Long)

A Range won’t cut it…

scala> val big_long=12345678901234567L
big_long: Long = 12345678901234567

scala> (1L to big_long)
java.lang.IllegalArgumentException: 1 to 12345678901234567 by 1: seqs cannot contain more than Int.MaxValue elements.

How about a BigIntRange?

scala> (BigInt(1) to BigInt(big_long))
java.lang.IllegalArgumentException: 1 to 12345678901234567 by 1: seqs cannot contain more than Int.MaxValue elements.
    at scala.collection.immutable.NumericRange$.count(NumericRange.scala:229)
    

OK, how about a stream?

scala>  lazy val naturals: Stream[Long] = Stream.cons(1, naturals.map(_ + 1))
naturals: Stream[Long] = <lazy>
scala>  naturals.takeWhile(_<big_long).find(_ == -1L)
Exception in thread "Poller SunPKCS11-Darwin" java.lang.OutOfMemoryError: Java heap space

hmm… running out of options a bit now. Maybe if I could construct a Stream without using the map() call (since I suspect that’s what’s eating up the heap), or use for-comprehension with an efficient generator?
Or…hang on…

scala> var i=0L
i: Long = 0
scala> while (i < big_long){i = i+1L}
{...time passes...exceptions are not thrown...}

So, it turns out that “the java way” works. Which, I guess, is the benefit of a mixed language; you can always fall back to the tried-and-tested solutions if the clever bits fail. And of course, you can hide the clunkiness pretty well:

 object LongIter extends Iterator[Long]{
    var l:Long = 0
    def hasNext:Boolean={true}
    def next:Long={
      l=l+1L
      l
    }
  }
  object LongIterable extends Iterable[Long]{
    val iter = LongIter
    def iterator = {iter}
  }

//ugliness ends, now we can pretend that LongIterable was there all along...

   LongIterable.find(_ == 12345678901234567L)

I suspect that this doesn’t really conform to the iterator/iterable contract (obviously, hasNext isn’t implemented), but it does appear to work tolerably well. Well enough, in fact, that I’m surprised I’ve not yet found a more idiomatic syntax for creating an iterator whose next() function is some arbitrary function on the previous value.

...reads source of Iterator ...

  Iterator.iterate(0L)(_+1L).find(_ == 123456701234567L)

phew. Finally.

Chris May : 09 Jun 2011 21:56 |  Comments (0) |  Report a problem