9

関数型スタイルで再帰アルゴリズムを書くことについて質問があります。ここでは例として Scala を使用しますが、問題はどの関数型言語にも当てはまります。

各ノードにラベルと可変数の子があるn分木の深さ優先列挙を行っています。以下は、リーフ ノードのラベルを出力する簡単な実装です。

case class Node[T](label:T, ns:Node[T]*)
def dfs[T](r:Node[T]):Seq[T] = {
    if (r.ns.isEmpty) Seq(r.label) else for (n<-r.ns;c<-dfs(n)) yield c
}
val r = Node('a, Node('b, Node('d), Node('e, Node('f))), Node('c))
dfs(r) // returns Seq[Symbol] = ArrayBuffer('d, 'f, 'c)

ここで、例外をスローして、大きすぎるツリーの解析をあきらめたい場合があるとします。これは関数型言語で可能ですか? 具体的には、可変状態を使用せずにこれは可能ですか? それはあなたが「特大」の意味に依存しているようです。これは、深さ 3 以上のツリーを処理しようとすると例外をスローするアルゴリズムの純粋に機能的なバージョンです。

def dfs[T](r:Node[T], d:Int = 0):Seq[T] = {
    require(d < 3)
    if (r.ns.isEmpty) Seq(r.label) else for (n<-r.ns;c<-dfs(n, d+1)) yield c
}

しかし、深すぎるのではなく幅が広すぎるために木が大きすぎる場合はどうなるでしょうか。具体的には、再帰の深さに関係なく、関数が再帰的に呼び出されるn回目に例外をスローしたい場合はどうすればよいでしょうか? dfs()これを行う方法を確認できる唯一の方法は、呼び出しごとにインクリメントされる可変カウンターを用意することです。可変変数なしでそれを行う方法がわかりません。

私は関数型プログラミングが初めてで、変更可能な状態でできることは何でもできるという前提で作業してきましたが、ここで答えがわかりません。私が考えられる唯一のことはdfs()、ツリー内のすべてのノードのビューを深さ優先順で返すバージョンを作成することです。

dfs[T](r:Node[T]):TraversableView[T, Traversable[_]] = ...

次に、 と言って制限を課すことができますがdfs(r).take(n)、この関数の書き方がわかりません。Python では、ノードにアクセスしたときにノードを ing してジェネレーターを作成するだけですyieldが、Scala で同じ効果を実現する方法がわかりません。(Python スタイルのステートメントに相当する Scalayieldは、パラメーターとして渡されるビジター関数のように見えますが、シーケンス ビューを生成するこれらの 1 つを記述する方法がわかりません。)

EDIT答えに近づく。

Streamこれは、深さ優先順でノードの a を返す関数です。

def dfs[T](r: Node[T]): Stream[Node[T]] = {
    (r #:: Stream.empty /: r.ns)(_ ++ dfs(_))
}

それはほとんどそれです。唯一の問題は、Streamすべての結果をメモすることであり、これはメモリの無駄です。横断可能なビューが必要です。以下はアイデアですが、コンパイルされません。

def dfs[T](r: Node[T]): TraversableView[Node[T], Traversable[Node[T]]] = {
    (Traversable(r).view /: r.ns)(_ ++ dfs(_))
}

これは、オペレーターに「found TraversableView[Node[T], Traversable[Node[T]]], requiredTraversableView[Node[T], Traversable[_]]エラー」を++返します。戻り値の型を に変更するTraversableView[Node[T], Traversable[_]]と、「found」節と「required」節が入れ替わって同じ問題が発生します。まだですが、これは近いです。

4

3 に答える 3

7

それは可能です: 必要な方法で ( に依存するのではなくfor) 子を実際に反復処理するためのコードを記述するだけです。

より明示的には、コードを記述して、子のリストを反復処理し、「深さ」がしきい値を超えたかどうかを確認する必要があります。以下にいくつかのHaskellコードを示します (申し訳ありませんが、私は Scala に堪能ではありませんが、これはおそらく簡単に音訳できます):

http://ideone.com/O5gvhM

このコードでは、基本的にforループを明示的な再帰バージョンに置き換えました。これにより、訪問したノードの数がすでに深すぎる場合 (つまり、limit正でない場合) に再帰を停止できます。次の子を調べるために再帰するときdfsは、前の子がアクセスしたノードの数を差し引き、これを次の子の制限として設定します。

関数型言語は楽しいものですが、命令型プログラミングとは大きく異なります。stateの概念に本当に注意を払う必要があります。なぜなら、それはすべて、機能するときに引数で耐え難いほど明示されているからです。

編集：これをもう少し説明します。

「リーフノードのみを印刷する」（OPの元のアルゴリズム）から「すべてのノードを印刷する」に変換することになりました。これにより、結果のリストの長さを通じて、サブコールが訪問したノードの数にアクセスできるようになりました。リーフ ノードに固執したい場合は、既にアクセスしたノードの数を持ち歩く必要があります。

http://ideone.com/cIQrna

もう一度編集この回答を明確にするために、すべての Haskell コードを ideone に置き、Haskell コードを Scala に音訳したので、これは質問に対する明確な回答としてここにとどまることができます。

case class Node[T](label:T, children:Seq[Node[T]])

case class TraversalResult[T](num_visited:Int, labels:Seq[T])

def dfs[T](node:Node[T], limit:Int):TraversalResult[T] =
    limit match {
        case 0     => TraversalResult(0, Nil)
        case limit => 
            node.children match {
                case Nil => TraversalResult(1, List(node.label))
                case children => {
                    val result = traverse(node.children, limit - 1)
                    TraversalResult(result.num_visited + 1, result.labels)
                }
            }
    }

def traverse[T](children:Seq[Node[T]], limit:Int):TraversalResult[T] =
    limit match {
        case 0     => TraversalResult(0, Nil)
        case limit =>
            children match {
                case Nil => TraversalResult(0, Nil)
                case first :: rest => {
                    val trav_first = dfs(first, limit)
                    val trav_rest = 
                        traverse(rest, limit - trav_first.num_visited)
                    TraversalResult(
                        trav_first.num_visited + trav_rest.num_visited,
                        trav_first.labels ++ trav_rest.labels
                    )
                }
            }
    }

val n = Node(0, List(
    Node(1, List(Node(2, Nil), Node(3, Nil))),
    Node(4, List(Node(5, List(Node(6, Nil))))),
    Node(7, Nil)
))
for (i <- 1 to 8)
    println(dfs(n, i))

出力：

TraversalResult(1,List())
TraversalResult(2,List())
TraversalResult(3,List(2))
TraversalResult(4,List(2, 3))
TraversalResult(5,List(2, 3))
TraversalResult(6,List(2, 3))
TraversalResult(7,List(2, 3, 6))
TraversalResult(8,List(2, 3, 6, 7))

PS これは Scala での私の最初の試みであるため、上記にはおそらくいくつかの恐ろしい非慣用的なコードが含まれています。ごめんなさい。

于 2012-11-21T00:40:53.030 に答える
4

インデックスを渡すかテールを取得することで、幅を深さに変換できます。

def suml(xs: List[Int], total: Int = 0) = xs match {
  case Nil => total
  case x :: rest => suml(rest, total+x)
}

def suma(xs: Array[Int], from: Int = 0, total: Int = 0) = {
  if (from >= xs.length) total
  else suma(xs, from+1, total + xs(from))
}

後者の場合、必要に応じて幅を制限する何かが既にあります。width前者では、 aまたは somesuchを追加するだけです。

于 2012-11-21T00:16:41.610 に答える
2

以下は、ツリー内のノードに対するレイジー深さ優先探索を実装します。

import collection.TraversableView
case class Node[T](label: T, ns: Node[T]*)
def dfs[T](r: Node[T]): TraversableView[Node[T], Traversable[Node[T]]] =
  (Traversable[Node[T]](r).view /: r.ns) {
    (a, b) => (a ++ dfs(b)).asInstanceOf[TraversableView[Node[T], Traversable[Node[T]]]]
  }

これにより、すべてのノードのラベルが深さ優先で印刷されます。

val r = Node('a, Node('b, Node('d), Node('e, Node('f))), Node('c))
dfs(r).map(_.label).force
// returns Traversable[Symbol] = List('a, 'b, 'd, 'e, 'f, 'c)

これは同じことを行い、3つのノードにアクセスした後に終了します。

dfs(r).take(3).map(_.label).force
// returns Traversable[Symbol] = List('a, 'b, 'd)

リーフノードのみが必要な場合はfilter、などを使用できます。

関数のfold句にはdfs、明示的なasInstanceOfキャストが必要であることに注意してください。これを必要とするScalaのタイピングの問題の説明については、「TraversableビューでfoldLeftを実行するときのScalaのタイプ分散エラー」を参照してください。

于 2012-11-21T19:36:23.347 に答える