forループがスカラーの末尾の再帰的な状態に達するのを避ける

Question

次の方法で任意のアーリーツリー構造を出力しました。 （深い最初の検索）

def treeString[A](tree: Tree[A]): String = { 

    def DFS(t: Tree[A], acc: String = "", visited: List[String] = Nil, toClose: Int = 0): String = t match { 
    case Leaf(id, terminal) if !visited.contains(id) => { 
     acc + " " + terminal.name + "[" + id.toString + "] " + ")"*toClose 
    } 
    case Node(id, op, args @_*) if !visited.contains(id) => { 
     var state = acc + " " + op.name + "[" + id.toString + "] " + "(" 
     var args_visited: List[String] = List(id) 
     for (i <- args.tail) { 
     state = DFS(i, state , visited ::: args_visited) + " , " 
     args_visited = args_visited ++ List(i.id) 
     } 
     DFS(args.head, state , visited ++ args_visited, toClose + 1) 
    } 
    case _ => acc 
    } 
    DFS(tree) 
} 

Scalaのコンパイラは、この関数はtail recursiveではないと主張します。しかし、私は適切なDFS(..)呼び出しを持っている末尾の位置。ループ内で行われたすべてのDFS(..)コールは繰り返し実行され、スタックセーフになります。

ツリーが無限に深い場合は、スタックオーバーフローが発生することを理解しています。これらの事件に対処する技術はありますか？

Answer 1

@VictorMorozに同意する必要があります。問題は、あなたの声明されていること：

state = DFS(i, state , visited ::: args_visited) + " , "

は、尾の位置にありません。新しいスタックを作成するので、あなたのメソッドはもはやテール再帰的ではありません。

ここでは、データ構造に深入りすることなく、DFS方式でツリーをテール再帰的にトラバースする方法を説明します。

sealed trait Tree[+A] 
    case class Leaf[A](value: A) extends Tree[A] 
    case class Node[A](left: Tree[A], right: Tree[A]) extends Tree[A] 
    case class Element(id:Int, name:String) 


    def DFS[T](t:Tree[T]): List[Element] = { 
    @tailrec 
    def _dfs(rest:List[Tree[T]], visited:List[Element]):List[Element] = { 
     rest match { 
     case Leaf(v:Element) => v :: visited 

     case Node(l,r) :: rs => _dfs(l::r::rs,visited) 

     } 
    } 
    _dfs(List(t),Nil) 
    } 

キーは明示的なスタックを使用することです（ここではListの形式）。

ツリーが無限に深い場合は、スタックオーバーフローが発生することがわかります です。

これは正しいです。基本的には、ほとんどのプログラミング言語では、各メソッド呼び出しがスタックメモリの一部を予約しています。簡単な言葉では、末尾再帰を使用すると、コンパイラは前の状態を無視できます。前のスタックは必要ありません。

DFSはglobal optimaを確実に見つけることができないため、これを実行する必要がある場合は使用しないでください。

ポストスクリプト： @tailrecアノテーションは、コンパイル時にメソッドを最適化できるかどうかをチェックするヒントです（デフォルトでは、スカラでテールコールの最適化を行います）。

Answer 2

私は尾の再帰的な状態に達することができました。

コードの完全性にもかかわらず、私は本当に機能的アプローチのコスト/利益に疑問を抱いています。ほとんどの場合、スタックを手動でアルゴリズムに渡す方法はほとんど分かりません。

とにかく、ここで本当の問題は、Scalaのコンパイラの静止画が末尾再帰機能を使用して私たちの脱出を提供しようとしますが、それだしばしば

def treeString[A](tree: Tree[A]): String = { 

    def dropWhile[A](l: List[A], f: A => Boolean): List[A] = 
    l match { 
     case h :: t if f(h) => dropWhile(t, f) 
     case _ => l 
    } 

    @tailrec 
    def DFS(toVisit: List[Tree[A]], visited: List[String] = Nil, acc: String = "", n_args: List[Int] = Nil): String = toVisit match { 
    case Leaf(id, terminal) :: tail if !visited.contains(id) => { 
     val n_args_filtered = dropWhile[Int](n_args, x => x == 1) 
     val acc_to_pass = acc + " " + terminal.name + "[" + id.toString + "] " + ")" * (n_args.length - n_args_filtered.length) + "," * {if (n_args_filtered.length > 0) 1 else 0} 
     val n_args_to_pass = {if (n_args_filtered.length > 0)List(n_args_filtered.head - 1) ::: n_args_filtered.tail else Nil} 

     DFS(toVisit.tail, visited ::: List(id), acc_to_pass, n_args_to_pass) 
    } 
    case Node(id, op, args @_*) :: tail if !visited.contains(id) => { 
     DFS(args.toList ::: toVisit.tail, visited ::: List(id), acc + " " + op.name + " (", List(args.length) ::: n_args) 
    } 
    case Nil => acc 
    } 
    DFS(List(tree)) 
}