Writing foldTerm from 'Data types ala Carte' in Scala

Question

I'm trying to write the foldTerm function from Data Types ala Carte in Scala. Here's what I've got so far

def foldTerm[F[+_], A, B](e: Free[F, A], pure: A ⇒ B, imp: F[B] ⇒ B)(implicit F: Functor[F]): B =
  e.resume match { 
    case Right(a) ⇒ pure(a)
    case Left(x)  ⇒ imp(F.map(x)(foldTerm(_, pure, imp)))
}

This works, but since Scala cannot properly optimize tail recursion, it causes a SOE. I've tried to fix it with Trampoline but have not had any luck so far. I feel like I should be able to do this with the existing methods on Free but all my attempts have ended in frustration.

What am I missing?

Answer 1

Scala can properly eliminate tail recursive calls. But your method is not tail recursive. You can check it with the @annotaion.tailrec annotation.

@annotation.tailrec
def foldTerm[F[+_], A, B](e: Free[F, A], pure: A ⇒ B, imp: F[B] ⇒ B)(implicit F: Functor[F]): B =
  e.resume match { 
    case Right(a) ⇒ pure(a)
    case Left(x)  ⇒ imp(F.map(x)(foldTerm(_, pure, imp)))
}

<console>:19: error: could not optimize @tailrec annotated method foldTerm: it contains a recursive call not in tail position
           case Left(x)  ⇒ imp(F.map(x)(foldTerm(_, pure, imp)))

Your last call here is imp and not foldTerm.