coursera scala チュートリアルでは、ほとんどの例でトップダウンの反復が使用されています。部分的には、繰り返しを使用して for/while ループを回避しています。私は C++ 出身で、これについて少し混乱しています。
for/while ループよりも反復が選択されていますか? 生産で実用的ですか？スタックオーバーフローのリスクはありますか? 効率はどうですか？ボトムアップの動的計画法はどうですか (特に末尾再帰ではない場合)?
また、「if」条件の使用を減らし、代わりに「case」とサブクラスを使用する必要がありますか?
真に高品質な Scala は、反復をほとんど使用せず、再帰をわずかに増やすだけです。低レベルの命令型言語でのループで行われることは、通常、高次のコンビネータ、特に map と flatmap で行うのが最適ですが、filter、zip、fold、foreach、reduce、collect、partition、scan、groupBy、および a良いいくつかの他の人。反復はパフォーマンスの重要なセクションでのみ行うのが最適であり、再帰は高次のコンビネータが完全に適合しないいくつかの深いエッジのケースでのみ行われます (通常、末尾再帰ではありません、fwiw)。実動システムで Scala のコーディングを 3 年間行ったとき、私は反復を 1 回、再帰を 2 回、マップを 1 日に約 5 回使用しました。
うーん、いくつかの質問が 1 つに。
古典的な例の 1 つは、 n 番目の フィボナッチ数を返す関数を作成することです。以下は単純な再帰的実装です。
def fib (n: Long): Long = n match {
case 0 | 1 => n
case _ => fib( n - 2) + fib( n - 1 )
}
さて、これは非効率的です (間違いなく末尾再帰ではありません) が、その構造がフィボナッチ数列にどのように関係しているかは非常に明白です。ただし、適切に末尾再帰にすることはできます。
def fib (n: Long): Long = {
def fibloop(current: Long, next: => Long, iteration: Long): Long = {
if (n == iteration)
current
else
fibloop(next, current + next, iteration + 1)
}
fibloop(0, 1, 0)
}
もっと簡潔に書くこともできたかもしれませんが、これは効率的な再帰的な実装です。とはいえ、最初のものほどきれいではなく、その構造は元の問題とあまり明確に関連していません。
最後に、このサイトの他の場所から恥知らずに盗まれたのは、Luigi Plinge のストリームベースの実装です。
val fibs: Stream[Int] = 0 #:: fibs.scanLeft(1)(_ + _)
非常に簡潔で、効率的で、エレガントで、(ストリームと遅延評価を理解していれば)非常に表現力豊かです。実際、これは再帰的でもあります。#::再帰関数ですが、遅延評価されたコンテキストで動作します。この種の解決策を考え出すには、確かに再帰的に考えることができなければなりません。
ここでは、 の従来の C スタイルを意味していると思います。
C/C++/Java スタイルの while ループは値を返さず、何かを達成するために副作用を必要とするため (これは C スタイルの forおよび Java スタイルのforeachにも当てはまります)、再帰的なソリューションはしばしばwhileループよりも望ましい場合があります。率直に言って、私はしばしば Scala がwhile を実装していなかったら(または、Scheme の名前付き let のようなもののシンタックス シュガーとして実装していたら) ほしかったと思います。副作用のあるループが発生する状況があります。は、何かを達成するためのより表現力豊かな方法ですが、Javaに固執する開発者は、それを実現するために少し難しくする必要がありました（たとえば、 a for comprehensionを悪用することにより）。
シンプルに、伝統的なwhileとfor は、ぎこちない命令型コーディングを非常に簡単にします。それが気にならないなら、なぜ Scala を使っているのですか?
テールの最適化により、スタックオーバーフローのリスクが排除されます。再帰的ソリューションを適切に末尾再帰的に書き直すと、非常に醜いものになる可能性があります (特に JVM で実行されている言語では)。
再帰的なソリューションは、命令型のソリューションよりも効率的である場合がありますが、驚くほど効率的です。理由の 1 つは、リストを操作することが多く、ヘッドとテールのアクセスのみが関係することです。リストの先頭と末尾の操作は、より構造化されたコレクションのランダム アクセス操作よりも実際には高速です。
優れた再帰アルゴリズムは通常、複雑な問題をより単純な問題の小さなセットに減らし、解決する問題を 1 つ選択し、残りを別の関数 (通常はそれ自体への再帰呼び出し) に委譲します。さて、私には、これは動的計画法に非常に適しているように思えます。確かに、問題に対して再帰的なアプローチを試みている場合、すべてのケースを解決できないことがわかっている単純なソリューションから始めることがよくあります。失敗した場所を確認し、そのパターンをソリューションに追加して、成功に向けて繰り返します。
Little Schemerには、再帰プログラミングに対するこの反復アプローチの例が多数あります。これは特に、以前のソリューションを後のより複雑なソリューションのサブコンポーネントとして再利用するためです。これは動的計画法アプローチの縮図と言えます。(これは、これまでに作成されたソフトウェアに関する最も優れた教育書の 1 つでもあります)。特にSchemeを同時に教えてくれるので、お勧めできます。あなたが本当にSchemeを学びたくないのなら(なぜ?どうしてしないの?)、それは他のいくつかの言語に適応されています.
Scala のif式は値を返します (これは非常に便利で、Scala が三項演算子を必要としない理由です)。シンプルを避ける理由はない
if (something)
// do something
else
// do something else
式。単純なif...elseの代わりに突き合わせを行う主な理由は、case ステートメントの力を利用して複雑なオブジェクトから情報を抽出するためです。 これが一例です。
一方、if...else if...else if...elseはひどいパターンです
else ifと書かれているところはどこでも、代替案を探してください。 試合は始めるのに適した場所です。
再帰の主な利点の 1 つは、ミューテーションなしでソリューションを作成できることです。次の例では、リストのすべての要素の合計を計算する必要があります。
この問題を解決する多くの方法の 1 つが以下のとおりです。この問題を解決するには、次のように for ループを使用します。
scala> var total = 0
scala> for(f <- List(1,2,3)) { total += f }
再帰ソリューションは次のようになります。
def total(xs: List[Int]): Int = xs match {
case Nil => 0
case x :: ys => x + total(ys)
}
違いは、再帰的なソリューションでは、問題をより小さな部分に分割できるようにすることで、変更可能な一時変数を使用しないことです。関数型プログラミングは、副作用のないプログラムを書くことがすべてであるため、再帰とループ (可変変数を使用する) を使用することを常にお勧めします。
ヘッド再帰は、最初に再帰呼び出しを実行し、次に再帰関数から戻り値を取得して結果を計算する、再帰を行う従来の方法です。
通常、関数を呼び出すと、現在実行中のスレッドのコール スタックにエントリが追加されます。欠点は、コール スタックのサイズが定義されているため、すぐに StackOverflowError 例外が発生する可能性があることです。これが、Java が再帰よりも反復を好む理由です。Scala は JVM 上で実行されるため、Scala もこの問題に悩まされます。しかし、Scala 2.8.1 から、Scala はテール コールの最適化を行うことでこの制限を取り除きます。Scala で末尾再帰を実行できます。
再帰を要約することは、突然変異の使用を避けるために関数型プログラミングで推奨される方法であり、2 つ目に末尾再帰が Scala でサポートされているため、Java で発生する StackOverFlow 例外に陥ることはありません。
お役に立てれば。