5

2 本の木を比較する質問がありました。以下のようなもの：

case class Node(elem:String, child:List[Node])

ツリーの各要素を比較するために、次の関数があります。

def compare(n1:Node, n2:Node): Boolean {
   if(n1.elem == n2.elem){
      return compare(n1.child, n2.child)
   }
}

def compare(c1:List[Node], c2:List[Node]): Boolean {
    while (c1.notEmpty) {
       //filter, map etc call function above to compare the element recursively
    }
}

基本的に、アルゴリズムは n1 の各要素に対して、n2 の一致をチェックしています。これは非常に必須の方法であり、機能的な方法ではないと言われました。この動作を達成するための機能的な方法は何でしょうか。つまり、子のリストを比較するときに while ループを削除するにはどうすればよいでしょうか。

4

2 に答える 2

4

両方のリストを圧縮し、処理するすべての述語が;に評価される場合にのみforall保持する whichを使用することを検討してください。たとえば、このように、truetrue

def compare(c1: List[Node], c2: List[Node]): Boolean = 
  (c1.sorted zip c2.sorted).forall(c => compare(c._1,c._2))

forall最初の に遭遇すると、評価が停止することに注意してくださいfalse。ノードのリストの長さが等しくない場合は、長さの違いをパディングするためのクラスをzipAll定義することで対処できます。EmptyNodeまた、両方のリストが空であると比較される場合がありますtrue。

@JohnB によるコメントに続いて、健全性のためにノードのソート済みリストを更新します。

于 2014-08-26T18:29:57.483 に答える
2

私があなたの質問を正しく理解していれば、最初のリストのすべての要素と 2 番目のリストのすべての要素を比較したいと思うでしょう。次のコードはこれを実現します。while末尾再帰を介してループを取り除きます。

import scala.annotation.tailrec

def cmp(a:Int, b:Int) = a > b

@tailrec
def compare(xs: List[Int], ys: List[Int]): Boolean = xs match {
    case Nil => true
    case head :: tail if ys.forall(x => cmp(head, x)) => compare(tail, ys)
    case _ => false
}
于 2014-08-26T21:08:13.690 に答える