2

継続渡しスタイルに関するいくつかのブログ記事/ウィキペディアを表面的に読んだことがあります。私の高レベルの目標は、再帰関数を末尾再帰にするための体系的な手法を見つけることです (または、制限がある場合は、それらを認識して)。しかし、私は自分の考えを明確にするのに苦労しており、私の試みが意味を成すかどうかはわかりません.

例として、簡単な問題を提案します。目標は、一意の文字の並べ替えられたリストを指定して、これらの文字から作成されたすべての可能な単語をアルファベット順に出力することです。たとえば、sol("op".toList, 3)を返す必要がありooo,oop,opo,opp,poo,pop,ppo,pppます。

私の再帰的な解決策は次のとおりです。

def sol(chars: List[Char], n: Int) = {
    def recSol(n: Int): List[List[Char]] = (chars, n) match {
        case (_  , 0) => List(Nil)
        case (Nil, _) => Nil
        case (_  , _) =>
            val tail = recSol(n - 1)
            chars.map(ch => tail.map(ch :: _)).fold(Nil)(_ ::: _)
    }
    recSol(n).map(_.mkString).mkString(",")
}

関数をパラメーターとして追加してこれを書き直そうとしましたが、末尾再帰であると確信できるものを作成することができませんでした。私は彼らの素朴さを恥じているので、私の試みを質問に含めたくないので、これを許してください.

したがって、質問は基本的に次のとおりです。上記の関数は CPS でどのように記述されますか?

4

2 に答える 2

2

それを試してください：

import scala.annotation.tailrec
def sol(chars: List[Char], n: Int) = {
  @tailrec
  def recSol(n: Int)(cont: (List[List[Char]]) => List[List[Char]]): List[List[Char]] = (chars, n) match {
    case (_  , 0) => cont(List(Nil))
    case (Nil, _) => cont(Nil)
    case (_  , _) =>
      recSol(n-1){ tail =>
        cont(chars.map(ch => tail.map(ch :: _)).fold(Nil)(_ ::: _))
      }
  }
  recSol(n)(identity).map(_.mkString).mkString(",")
}
于 2016-06-13T10:52:17.350 に答える