blob: ba3044c71871967d9a2675a0aa6105c64b340385 (
plain) (
blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
|
/* __ *\
** ________ ___ / / ___ Scala API **
** / __/ __// _ | / / / _ | (c) 2003-2013, LAMP/EPFL **
** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ **
** /____/\___/_/ |_/____/_/ | | **
** |/ **
\* */
package scala
package util.control
/** Methods exported by this object implement tail calls via trampolining.
* Tail calling methods have to return their result using `done` or call the
* next method using `tailcall`. Both return a `TailRec` object. The result
* of evaluating a tailcalling function can be retrieved from a `Tailrec`
* value using method `result`. Here's a usage example:
* {{{
* import scala.util.control.TailCalls._
*
* def isEven(xs: List[Int]): TailRec[Boolean] =
* if (xs.isEmpty) done(true) else tailcall(isOdd(xs.tail))
*
* def isOdd(xs: List[Int]): TailRec[Boolean] =
* if (xs.isEmpty) done(false) else tailcall(isEven(xs.tail))
*
* isEven((1 to 100000).toList).result
* }}}
*/
object TailCalls {
/** This class represents a tailcalling computation
*/
abstract class TailRec[+A] {
/** Returns the result of the tailcalling computation.
*/
def result: A = {
def loop(body: TailRec[A]): A = body match {
case Call(rest) => loop(rest())
case Done(result) => result
}
loop(this)
}
}
/** Internal class representing a tailcall */
protected case class Call[A](rest: () => TailRec[A]) extends TailRec[A]
/** Internal class representing the final result returned from a tailcalling
* computation */
protected case class Done[A](override val result: A) extends TailRec[A]
/** Performs a tailcall
* @param rest the expression to be evaluated in the tailcall
* @return a `TailRec` object representing the expression `rest`
*/
def tailcall[A](rest: => TailRec[A]): TailRec[A] = new Call(() => rest)
/** Used to return final result from tailcalling computation
* @param `result` the result value
* @return a `TailRec` object representing a computation which immediately
* returns `result`
*/
def done[A](result: A): TailRec[A] = new Done(result)
}
|