как подходить к реализации рекурсии TCO - PullRequest
Новая
       39

как подходить к реализации рекурсии TCO

2 голосов
/ 23 ноября 2011

Я изучал рекурсию и TCO. Кажется, что TCO может сделать код многословным, а также повлиять на производительность. например Я ввел код, который принимает 7-значный номер телефона и возвращает все возможные перестановки слов, например, 464-7328 может быть "GMGPDAS ... IMGREAT ... IOIRFCU" Вот код. 

/*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
      }
  }

Это коротко, и мне не нужно тратить на это слишком много времени. Однако, когда я пытаюсь сделать это в хвостовой рекурсии, чтобы получить TCO'ed. Я должен потратить значительное количество времени, и код становится очень многословным. Я не буду представлять весь код для экономии места. Вот ссылка на ссылку git repo . Наверняка многие из вас могут написать более качественный и лаконичный хвостовой рекурсивный код, чем мой. Я по-прежнему считаю, что в целом TCO является более многословным (например, рекурсия хвостового вызова Фибоначчи и Фибоначчи имеет дополнительный параметр, аккумулятор). Тем не менее, TCO необходим для предотвращения переполнения стека. Я хотел бы знать, как вы подходите к TCO и рекурсии. Реализация схемы Акерманна с TCO в этой теме олицетворяет мою постановку проблемы.

Ответы [ 3 ]

5 голосов
/ 01 декабря 2011

Возможно ли, что вы используете термин "оптимизация хвостового вызова", когда на самом деле вы действительно имеете в виду написание функции в итеративном рекурсивном стиле или в стиле передачи продолжения, так что все рекурсивные вызовы являются хвостовыми вызовами?

Внедрение TCO - это работа разработчика языка; одна статья, в которой говорится о том, как это можно сделать эффективно, - это классическая лямбда: предельная бумага GOTO .

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

4 голосов
/ 23 ноября 2011

Как упоминалось в комментариях sclv, хвостовая рекурсия для этого примера в Хаскеле не имеет смысла.Простая реализация вашей проблемы может быть написана кратко и эффективно с помощью монады списка. 

import Data.Char
getChars n | n > 1     = [chr (ord 'a' + 3*(n-2)+i) | i <- [0..2]]
           | otherwise = ""
getTelNum = mapM getChars
3 голосов
/ 23 ноября 2011

Как говорят другие, я не буду беспокоиться о хвостовом вызове в этом случае, так как он не повторяется очень глубоко (длина входных данных) по сравнению с размером выходных данных. У вас должно быть недостаточно памяти (или терпения), прежде чем вы выйдете из стека

Я бы, наверное, реализовал что-то вроде 

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
   }
}

Если вы настаиваете на хвостовой рекурсии, это может быть основано на 

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

(фактическая процедура должна вызывать helper(List(""), input))

...