Как использовать TailCalls?

Если я правильно понимаю, scala.util.control.TailCalls можно использовать для предотвращения переполнения стека для нерекурсивных функций с помощью трамплина. Пример, приведенный в API, прост:

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 

Однако более интересный случай - если вы хотите выполнить некоторые операции после рекурсивного вызова. Я получил "наивную" факториальную реализацию, каким-то образом работающую на

def fac(n:Long): TailRec[Long] = 
    if (n == 0) done(1) else done(n * tailcall(fac(n - 1)).result)

, но это выглядит ужасно, и я сомневаюсь, что это предполагаемое использование. Итак, мой вопрос: как правильно написать факториал или функцию Фибоначчи, используя TailCalls (да, я знаю, как использовать аккумуляторы, чтобы получить их хвостовую рекурсию)? Или TailCalls не подходит для такого рода проблем?

19
задан Landei 13 December 2010 в 12:34
поделиться