3

私は Coursera の Scala コースに取り組んでいますが、再帰、特に機能的な方法でのツリー トラバーサルの処理に深刻な問題があることに気付きました。問題を一般化するために (より広い関連性のために)、バイナリ ツリーとして定義されたセットを用意しました。個々のノードは、カスタム バイナリ ツリー抽象クラスを拡張するか、Emptyまたはその両方です。Non-emptyノードがそのインスタンスである場合、Non-empty; 左の子、右の子、および class の要素MyObj。

findMax私が実装した関数を考えるとNon-empty：

def findMax: MyObj = {

  // traverse left, traverse right, check with the candidate 
  def treeAcc(tree:MyBTSet, cand: MyObj, f: (MyObj,MyObj) => MyObj): MyObj = {
    if (tree.isEmpty) cand
    else f(treeAcc(left,cand,f), treeAcc(right,cand,f))  
  }

  treeAcc(this,elem, (t1,t2) => if (t1.text > t2.text) t1 else t2)
}

  • コードで StackOverflow が発生するのはなぜですか?

  • 関数型プログラミングに関して何か基本的なことが欠けていますか? 私はそのようなセットのユニオンにもかなり深刻な問題を抱えていました（私の前の質問を参照）。これはおそらく些細なことであり、ユニオンのより良い実装は「単純なワンライナー」です。

    関数型プログラミングで成功するには考え方を変える必要があると聞いています。そして、物事がどのように機能するかを理解すると、人はおそらく涅槃に到達し、世界平和が達成され、世界は住むのに美しい場所になります...

    しかし、これまでのところ、純粋にフラストレーションが溜まっています...さらに悪いことに、他の学生はそれほど苦労しているようには見えず、フォーラムは最適化に関する議論であふれかえっていますが、私は何が起こっているのか明確に理解できずに立ち往生しています。 . これは、次の 3 つの選択肢のいずれかを意味すると考えています。

    a) 私は馬鹿すぎて理解できない

    b) 他の学生は、関数型プログラミングについてある程度の知識を持っている

    c) 私は何か間違ったことをしている

物事を把握するための助けは大歓迎です。PS:解決策については何も教えないようにしてください。コードが意図したとおりに機能しない理由と、どのように考えるべきかを理解したいだけです。

4

1 に答える 1

1

関数スタックは、常に同じ引数 ( leftand right、つまりthis.leftand this.right) で呼び出すため、オーバーフローします。treeAcc を再帰的に呼び出すときは、ルートのサブツリーではなく、現在のノードのサブツリーで呼び出す必要があります。

def treeAcc(tree:MyBTSet, cand: MyObj, f: (MyObj,MyObj) => MyObj): MyObj = {
  if (tree.isEmpty) cand
  else f(treeAcc(tree.left,cand,f), treeAcc(tree.right,cand,f))  
}
于 2013-04-26T10:20:19.787 に答える