how to approach implementing TCO'ed recursion

Question

I have been looking into recursion and TCO. It seems that TCO can make the code verbose and also impact the performance. e.g. I have implemented the code which takes in 7 digit phone number and gives back all possible permutation of words e.g. 464-7328 can be "GMGPDAS ... IMGREAT ... IOIRFCU" Here is the code.

/*Generate the alphabet table*/
  val alphabet = (for (ch <- 'a' to 'z') yield ch.toString).toList

/*Given the number, return the possible alphabet List of String(Instead of Char for convenience)*/
  def getChars(num : Int) : List[String] = {
      if (num > 1) return List[String](alphabet((num - 2) * 3), alphabet((num - 2) * 3 + 1), alphabet((num - 2) * 3 + 2))
      List[String](num.toString)
  }

/*Recursion without TCO*/
  def getTelWords(input : List[Int]) : List[String] = {
    if (input.length == 1) return getChars(input.head)
      getChars(input.head).foldLeft(List[String]()) {
        (l, ch) => getTelWords(input.tail).foldLeft(List[String]()) { (ll, x) => ch + x :: ll } ++ l
      }
  }

It is short and I don't have to spend too much time on this. However when I try to do that in tail call recursion to get it TCO'ed. I have to spend a considerable amount of time and The code become very verbose. I won't be posing the whole code to save space. Here is a link to git repo link. It is for sure that quite a lot of you can write better and concise tail recursive code than mine. I still believe that in general TCO is more verbose (e.g. Factorial and Fibonacci tail call recursion has extra parameter, accumulator.) Yet, TCO is needed to prevent the stack overflow. I would like to know how you would approach TCO and recursion. The Scheme implementation of Akermann with TCO in this thread epitomize my problem statement.

Answer 1

Is it possible that you're using the term "tail call optimization", when in fact you really either mean writing a function in iterative recursive style, or continuation passing style, so that all the recursive calls are tail calls?

Implementing TCO is the job of a language implementer; one paper that talks about how it can be done efficiently is the classic Lambda: the Ultimate GOTO paper.

Tail call optimization is something that your language's evaluator will do for you. Your question, on the other hand, sounds like you are asking how to express functions in a particular style so that the program's shape allows your evaluator to perform tail call optimization.

Answer 2

As sclv mentioned in the comments, tail recursion is pointless for this example in Haskell. A simple implementation of your problem can be written succinctly and efficiently using the list monad.

import Data.Char
getChars n | n > 1     = [chr (ord 'a' + 3*(n-2)+i) | i <- [0..2]]
           | otherwise = ""
getTelNum = mapM getChars

Answer 3

As said by others, I would not be worried about tail call for this case, as it does not recurse very deeply (length of the input) compared to the size of the output. You should be out of memory (or patience) before you are out of stack

I would implement probably implement with something like

def getTelWords(input: List[Int]): List[String]  = input match {
   case Nil => List("")
   case x :: xs => {
      val heads = getChars(x)
      val tails = getTelWords(xs)
      for(c <- heads; cs <- tails) yield c + cs
   }
}

If you insist on a tail recursive one, that might be based on

def helper(reversedPrefixes: List[String], input: List[Int]): List[String] 
  = input match {
    case  Nil => reversedPrefixes.map(_.reverse)
    case (x :: xs) =>  helper(
      for(c <- getChars(x); rp <- reversedPrefixes) yield c + rp,
      xs)
  }

(the actual routine should call helper(List(""), input))