12

Scala の初心者として、私は書籍やドキュメントを読み、http://aperiodic.net/phil/scala/s-99/にある問題を解決しようとしています。正しい Scala コードは、ループや変数ではなく不変値 (val) と再帰に基づいており、並列処理をより安全にし、ロックを使用する必要がないように思われます。

たとえば、演習 P22 ( http://aperiodic.net/phil/scala/s-99/p22.scala ) の可能な解決策は次のとおりです。

// Recursive.
def rangeRecursive(start: Int, end: Int): List[Int] =
if (end < start) Nil
else start :: rangeRecursive(start + 1, end)

もちろん、このコードはコンパクトでスマートに見えますが、もちろん、再帰の数が多い場合は、StackOverflow エラーが発生します (たとえば、JVM チューニングなしで rangeRecussive(1,10000))。組み込みの List.range (https://github.com/scala/scala/blob/v2.9.2/src/library/scala/collection/immutable/List.scala#L1) のソースを見ると、ループと変数が使用されていることがわかります。

私の質問は、再帰の数が原因でそのようなコードが壊れる可能性があることを知って、val と再帰を促進している Scala 学習の影響をどのように管理するかということです。

4

4 に答える 4

16

Scala の良いところは、簡単に始められることです。最初はループを記述し、言語に慣れるにつれて再帰をより多く行うことができます。Clojure や Haskell などのより「純粋な」関数型言語では、これを行うことはできません。つまり、不変性とvalに慣れて、後で再帰に進むことができます。

再帰を開始する場合は、末尾呼び出し再帰を調べる必要があります。再帰呼び出しが関数の最後の呼び出しである場合、Scala コンパイラーはこれをバイトコードのループに最適化します。そうすれば、StackOverflowErrorsは得られません。また、@tailrec再帰関数に注釈を追加すると、コンパイラは、関数が末尾呼び出し再帰でない場合に警告を発します。

たとえば、質問の関数は末尾呼び出し再帰ではありません。rangeRecursiveへの呼び出しが関数の最後の呼び出しのように見えますが、この呼び出しが戻ったときstartに、呼び出しの結果に追加する必要があります。したがって、末尾の呼び出しを再帰的にすることはできません。呼び出しが戻ったときに、まだ作業を行う必要があります。

于 2012-07-27T10:51:23.117 に答える
4

そのメソッドを末尾再帰にする例を次に示します。@tailrec 注釈は必要ありません。コンパイラは注釈なしで最適化します。ただし、最適化を実行できない場合、コンパイラはエラーをフラグします。

scala> def rangeRecursive(start: Int, end: Int): List[Int] = {
    |   @scala.annotation.tailrec
    |   def inner(accum : List[Int], start : Int) : List[Int] = {
    |       if (end < start) accum.reverse
    |       else inner(start :: accum, start + 1)
    |   }
    |   
    |   inner(Nil, start)
    | }
rangeRecursive: (start: Int,end: Int)List[Int]

scala> rangeRecursive(1,10000)
res1: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11,...

中間結果が蓄積され、再帰の次のステップに渡される「アキュムレータ受け渡しスタイル」と呼ばれる一般的な手法を使用します。一番下のステップは、累積された結果を返す責任があります。この場合、アキュムレータはたまたまその結果を逆に構築するため、基本ケースはそれを逆にする必要があります。

于 2012-07-27T15:24:35.127 に答える
1

末尾再帰になるように上記を書き直すと、コンパイラはコードを while ループに最適化します。@tailrecさらに、アノテーションを付けているメソッドが末尾再帰的でない場合、アノテーションを使用してエラーを取得できます。これにより、「いつ正解したか」を知ることができます。

于 2012-07-27T10:53:40.667 に答える
1

同じ動作で、James Iry's answer の代替案を次に示します。

def rangeRecursive(start: Int, end: Int): List[Int] = {
  def inner(start : Int) : Stream[Int] = {
      if (end < start) Stream.empty
      else start #:: inner(start + 1)
  }

  inner(start).toList
}

scala> rangeRecursive(1,10000)
res1: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11,...

-operator ( ) は末尾を参照によって格納するStackOverflowErrorため、これは a をスローしません。つまり、 Stream 要素はが呼び出されるまで計算されません。Stream.cons#::stream.toList

私の意見では、これはアキュムレータ パターンよりも読みやすいと思います。これは、単純な初期アルゴリズムに最もよく似ているためです ( と を置き換えるだけです::) 。また、忘れがちな も必要ありません。#::NilStream.emptyaccum.reverse

于 2015-06-28T14:32:18.637 に答える