diff options
author | Iulian Dragos <jaguarul@gmail.com> | 2008-04-02 14:11:46 +0000 |
---|---|---|
committer | Iulian Dragos <jaguarul@gmail.com> | 2008-04-02 14:11:46 +0000 |
commit | 2facac90e8c3cae5cbe29a55835c69847d270a40 (patch) | |
tree | 37fd17257109a8fef3ece98f2fcb9d1e3bf8d78b | |
parent | 66515781fa9823e200779e5d53aa244e46e22f02 (diff) | |
download | scala-2facac90e8c3cae5cbe29a55835c69847d270a40.tar.gz scala-2facac90e8c3cae5cbe29a55835c69847d270a40.tar.bz2 scala-2facac90e8c3cae5cbe29a55835c69847d270a40.zip |
Changed Stream implementation to use tail recur...
Changed Stream implementation to use tail recursive calls directly,
instead of tail-recursive local functions. This has better GC behavior,
see ticket #692.
-rw-r--r-- | src/library/scala/Stream.scala | 100 | ||||
-rw-r--r-- | test/files/run/streams.check | 6 | ||||
-rw-r--r-- | test/files/run/streams.scala | 14 |
3 files changed, 57 insertions, 63 deletions
diff --git a/src/library/scala/Stream.scala b/src/library/scala/Stream.scala index 1f9b233e4a..3b7f7a4bd5 100644 --- a/src/library/scala/Stream.scala +++ b/src/library/scala/Stream.scala @@ -122,11 +122,11 @@ object Stream { * @param step the increment value of the stream * @return the stream starting at value <code>start</code>. */ - def range(start: Int, end: Int, step: Int): Stream[Int] = { - def loop(lo: Int): Stream[Int] = - if ((step <= 0 || lo < end) && (step >= 0 || lo > end)) cons(lo, loop(lo + step)) - else empty - loop(start) + final def range(start: Int, end: Int, step: Int): Stream[Int] = { + if ((step <= 0 || start < end) && (step >= 0 || start > end)) + cons(start, range(start + step, end, step)) + else + empty } /** @@ -276,15 +276,10 @@ trait Stream[+A] extends Seq.Projection[A] { * @return the last element of the stream. * @throws Predef.NoSuchElementException if the stream is empty. */ - override def last: A = + override final def last: A = if (isEmpty) throw new NoSuchElementException("Stream.empty.last") - else { - def loop(s: Stream[A]): A = { - if (s.tail.isEmpty) s.head - else loop(s.tail) - } - loop(this) - } + else + if (tail.isEmpty) head else tail.last /** Returns the <code>n</code>-th element of this stream. The first element * (head of the stream) is at position 0. @@ -303,7 +298,7 @@ trait Stream[+A] extends Seq.Projection[A] { */ override def take(n: Int): Stream[A] = if (isEmpty || n <= 0) Stream.empty - else Stream.cons(head, if (n == 1) Stream.empty else (tail take (n-1))) + else Stream.cons(head, if (n == 1) Stream.empty else (tail.take(n-1))) /** Returns the stream without its <code>n</code> first elements. * If the stream has less than <code>n</code> elements, the empty stream is returned. @@ -311,11 +306,9 @@ trait Stream[+A] extends Seq.Projection[A] { * @param n the number of elements to drop. * @return the stream without its <code>n</code> first elements. */ - override def drop(n: Int): Stream[A] = { - def loop(s: Stream[A], n: Int): Stream[A] = - if (s.isEmpty || n <= 0) s - else loop(s.tail, n-1) - loop(this, n) + override final def drop(n: Int): Stream[A] = { + if (isEmpty || n <= 0) this + else tail.drop(n - 1) } @@ -337,11 +330,9 @@ trait Stream[+A] extends Seq.Projection[A] { * @return the longest suffix of the stream whose first element * does not satisfy the predicate <code>p</code>. */ - override def dropWhile(p: A => Boolean): Stream[A] = { - def loop(s: Stream[A]): Stream[A] = - if (s.isEmpty || !p(s.head)) s - else loop(s.tail) - loop(this) + override final def dropWhile(p: A => Boolean): Stream[A] = { + if (isEmpty || !p(head)) this + else tail.dropWhile(p) } /** Returns the stream resulting from applying the given function <code>f</code> to each @@ -359,12 +350,9 @@ trait Stream[+A] extends Seq.Projection[A] { * * @param f the treatment to apply to each element. */ - override def foreach(f: A => Unit) { - def loop(s: Stream[A]) { - if (s.isEmpty) {} - else { f(s.head); loop(s.tail) } - } - loop(this) + override final def foreach(f: A => Unit) { + if (isEmpty) {} + else { f(head); tail.foreach(f) } } /** Returns all the elements of this stream that satisfy the @@ -373,12 +361,10 @@ trait Stream[+A] extends Seq.Projection[A] { * @param p the predicate used to filter the stream. * @return the elements of this stream satisfying <code>p</code>. */ - override def filter(p: A => Boolean): Stream[A] = { - def loop(s: Stream[A]): Stream[A] = - if (s.isEmpty) s - else if (p(s.head)) Stream.cons(s.head, loop(s.tail)) - else loop(s.tail) - loop(this) + override final def filter(p: A => Boolean): Stream[A] = { + if (isEmpty) this + else if (p(head)) Stream.cons(head, tail.filter(p)) + else tail.filter(p) } /** Tests if the predicate <code>p</code> is satisfied by all elements @@ -388,12 +374,10 @@ trait Stream[+A] extends Seq.Projection[A] { * @return <code>true</code> iff all elements of this stream satisfy the * predicate <code>p</code>. */ - override def forall(p: A => Boolean): Boolean = { - def loop(s: Stream[A]): Boolean = - if (s.isEmpty) true - else if (p(s.head)) loop(s.tail) - else false - loop(this) + override final def forall(p: A => Boolean): Boolean = { + if (isEmpty) true + else if (p(head)) tail.forall(p) + else false } /** Tests the existence in this stream of an element that satisfies the @@ -403,12 +387,10 @@ trait Stream[+A] extends Seq.Projection[A] { * @return <code>true</code> iff there exists an element in this stream that * satisfies the predicate <code>p</code>. */ - override def exists(p: A => Boolean): Boolean = { - def loop(s: Stream[A]): Boolean = - if (s.isEmpty) false - else if (p(s.head)) true - else loop(s.tail) - loop(this) + override final def exists(p: A => Boolean): Boolean = { + if (isEmpty) false + else if (p(head)) true + else tail.exists(p) } /** Combines the elements of this stream together using the binary @@ -419,11 +401,9 @@ trait Stream[+A] extends Seq.Projection[A] { * a<sub>n</sub>)</code> if the stream is * <code>[a<sub>0</sub>, a<sub>1</sub>, ..., a<sub>n</sub>]</code>. */ - override def foldLeft[B](z: B)(f: (B, A) => B): B = { - def loop(s: Stream[A], z: B): B = - if (s.isEmpty) z - else loop(s.tail, f(z, s.head)) - loop(this, z) + override final def foldLeft[B](z: B)(f: (B, A) => B): B = { + if (isEmpty) z + else tail.foldLeft(f(z, head))(f) } /** Combines the elements of this stream together using the binary @@ -469,11 +449,8 @@ trait Stream[+A] extends Seq.Projection[A] { * @param start starting index. * @pre the array must be large enough to hold all elements. */ - override def copyToArray[B >: A](xs: Array[B], start: Int) { - def loop(s: Stream[A], start: Int) { - if (!s.isEmpty) { xs(start) = s.head; loop(s.tail, start + 1) } - } - loop(this, start) + override final def copyToArray[B >: A](xs: Array[B], start: Int) { + if (!isEmpty) { xs(start) = head; tail.copyToArray(xs, start + 1) } } /** Returns a stream formed from this stream and the specified stream @@ -507,11 +484,8 @@ trait Stream[+A] extends Seq.Projection[A] { * @param sep The separator string printed between consecutive elements. */ def print(sep: String) { - def loop(s: Stream[A]) { - if (s.isEmpty) Console.println("Stream.empty") - else { Console.print(s.head); Console.print(sep); loop(s.tail) } - } - loop(this) + if (isEmpty) Console.println("Stream.empty") + else { Console.print(head); Console.print(sep); tail.print(sep) } } /** Converts stream to string */ diff --git a/test/files/run/streams.check b/test/files/run/streams.check index 5346c73d12..7f894052d9 100644 --- a/test/files/run/streams.check +++ b/test/files/run/streams.check @@ -17,3 +17,9 @@ Stream() 999 512 +100000 +Stream(100001, ?) +Stream(100001, ?) +true +true +705082704 diff --git a/test/files/run/streams.scala b/test/files/run/streams.scala index 1e781a6171..970f3cef16 100644 --- a/test/files/run/streams.scala +++ b/test/files/run/streams.scala @@ -29,4 +29,18 @@ object Test extends Application { def powers(x: Int) = if ((x&(x-1)) == 0) Some(x) else None println(s3.flatMap(powers).reverse.head) + // large enough to generate StackOverflows (on most systems) + // unless the following methods are tail call optimized. + val size = 100000 + + // test tail recursive methods + println(Stream.from(1).take(size).last) + println(Stream.from(1).drop(size)) + println(Stream.from(1).filter(_ > size).take(5)) + println(Stream.from(1).take(size).forall(_ >= 0)) + println(Stream.from(1).exists(_ > size)) + Stream.from(1).take(size).foreach( x => () ) + println(Stream.from(1).take(size).foldLeft(0)(_ + _)) + val arr = new Array[Int](size) + Stream.from(1).take(size).copyToArray(arr, 0) } |