Geek asks and answers

Record foldTerm from "Ala Carte Data Types" in Scala

I am trying to write a function foldTermfrom ala Carte Data Types in Scala. That's what i still have

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 invokes SOE. I tried to fix it with help Trampoline, but so far no luck. It seems to me that I can do this using existing methods on Free, but all my attempts ended in disappointment.

What am I missing?

+5
source share
2 answers

Scala can correctly resolve tail recursive calls. But your method is not tail recursive. You can check it using annotation @annotaion.tailrec.

@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)))

imp, foldTerm.

+2

, . ListT.fromList , , . StreamT .

+2

More articles:


All Articles