How to make a tail-recursive method that can also refer to itself in a non-tail-recursive way

Question

Suppose I have a mechanism for long-running computations that can suspend themselves to be resumed later:

sealed trait LongRunning[+R]; case class Result[+R](result: R) extends LongRunning[R]; case class Suspend[+R](cont: () => LongRunning[R]) extends LongRunning[R];

The simplest way how to run them is

@annotation.tailrec def repeat[R](body: LongRunning[R]): R = body match { case Result(r) => r case Suspend(c) => { // perhaps do some other processing here println("Continuing suspended computation"); repeat(c()); } }

The problem is creating such computations. Let's say we want to implement tail-recursive factorial that suspends its computation every 10 cycles:

@annotation.tailrec def factorial(n: Int, acc: BigInt): LongRunning[BigInt] = { if (n <= 1) Result(acc); else if (n % 10 == 0) Suspend(() => factorial(n - 1, acc * n)) else factorial(n - 1, acc * n) }

But this does not compile:

error: could not optimize @tailrec annotated method factorial: it contains a recursive call not in tail position
Suspend(() => factorial(n - 1, acc * n)) 

How to retain tail recursion on the non-suspending calls?

@MyseriousDan Thanks, that's very interesting. Actually, LongRunning is a simplification of my original problem - I'm working on a conduit-like library for Scala scala-conduit where Pipe naturally forms a monad. — Petr
– Petr, Commented Mar 11, 2013 at 18:13
Yeah, that kind of thing is generally an instantiation of a free monad of some sort. The partiality one is a little odd because it's generally represented as a corecursive thunk, but whether you have Free[() => _, R] or Free[ChunkOfData => _, R] makes little fundamental difference. — Mysterious Dan
– Mysterious Dan, Commented Mar 11, 2013 at 18:16
Note also that this actually already exist in the standard library: scala-lang.org/api/current/… — Régis Jean-Gilles
– Régis Jean-Gilles, Commented Mar 11, 2013 at 19:15

Petr · Accepted Answer · 2013-03-11 09:04:45Z

4

I found one possible answer. We can move the tail-recursive part into an inner function, and refer to the outer one, non-tail-recursive, when we need:

def factorial(n: Int, acc: BigInt): LongRunning[BigInt] = { @annotation.tailrec def f(n: Int, acc: BigInt): LongRunning[BigInt] = if (n <= 1) Result(acc); else if (n % 10 == 0) Suspend(() => factorial(n - 1, acc * n)) else f(n - 1, acc * n) f(n, acc) }

answered Mar 11, 2013 at 9:04

Petr

63.6k13 gold badges162 silver badges333 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

om-nom-nom Over a year ago

Am I right saying that this going to re-create closure instance on every factorial call?

Petr Over a year ago

@om-nom-nom I'm not really sure how well Scala optimizes such closures. Anyway, they're created only for suspensions, which don't occur too often. (This example is a bit simplified.) But I can say from my observations that the memory footprint stays constant. I tested another similar computation that used 1000000 suspensions. It ran very fast, consuming only a very little memory.

Régis Jean-Gilles Over a year ago

"Am I right saying that this going to re-create closure instance on every factorial call": No, a closure is only created when suspending. When f calls itself, the call is indeed tail recursive and thus there is no further stack use (hence no stack overflow).

Collectives™ on Stack Overflow

How to make a tail-recursive method that can also refer to itself in a non-tail-recursive way

1 Answer 1

3 Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Linked

Related