2

私は再帰と TCO を調べてきました。TCO はコードを冗長にし、パフォーマンスにも影響を与える可能性があるようです。たとえば、7 桁の電話番号を取り、可能なすべての単語の順列を返すコードを実装しました。

/*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 を取得するために末尾呼び出しの再帰でそれを実行しようとすると。かなりの時間を費やす必要があり、コードが非常に冗長になります。スペースを節約するためにコード全体をポーズするつもりはありません。これは git repo link へのリンクです。多くの皆さんが、私よりも優れた簡潔な末尾再帰コードを作成できることは確かです。一般に、TCO はより冗長であると私は今でも信じています (たとえば、階乗およびフィボナッチの末尾呼び出し再帰には、アキュムレータという追加のパラメーターがあります)。しかし、TCO はスタック オーバーフローを防ぐために必要です。TCO と再帰にどのようにアプローチするかを知りたいです。このスレッドでの TCO を使用した Akermann の Scheme 実装は、私の問題点の典型です。

4

3 に答える 3

5

「テールコールの最適化」という用語を使用している可能性はありますか?

TCO の実装は言語実装者の仕事です。それを効率的に行う方法について説明している論文の 1 つは、古典的な Lambda: 究極の GOTO論文です。

末尾呼び出しの最適化は、言語の評価者が代わりに行うものです。一方、あなたの質問は、プログラムの形状によって評価者がテールコールの最適化を実行できるように、特定のスタイルで関数を表現する方法を尋ねているように聞こえます。

于 2011-12-01T02:55:58.803 に答える
4

コメントで sclv が言及されているように、Haskell のこの例では末尾再帰は無意味です。問題の単純な実装は、リスト モナドを使用して簡潔かつ効率的に記述できます。

import Data.Char
getChars n | n > 1     = [chr (ord 'a' + 3*(n-2)+i) | i <- [0..2]]
           | otherwise = ""
getTelNum = mapM getChars
于 2011-11-23T08:53:08.337 に答える
3

他の人が言ったように、この場合の末尾呼び出しは、出力のサイズに比べてあまり深く（入力の長さ）繰り返されないため、心配する必要はありません。スタックがなくなる前に、メモリ（または忍耐）が不足している必要があります

私はおそらく次のようなもので実装します

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

于 2011-11-23T09:11:29.567 に答える