6

このコードを考えてみてください（Martin Oderskyによる「Scalaの関数型プログラミングの原則」コースから引用）：

def sieve(s: Stream[Int]): Stream[Int] = {
  s.head #:: sieve(s.tail.filter(_ % s.head != 0))
}

val primes = sieve(Stream.from(2))
primes.take(1000).toList

それはうまく機能します。末尾が怠惰sieveであっても、実際には末尾再帰ではないことに注意してください（またはそうですか？）。Stream

しかし、このコード：

def sieve(n: Int): Stream[Int] = {
  n #:: sieve(n + 1).filter(_ % n != 0)
}

val primes = sieve(2)
primes.take(1000).toList

スローしStackOverflowErrorます。

2番目の例の問題は何ですか？混乱していると思いfilterますが、理由がわかりません。それはを返すStreamので、それは評価を熱心にさせません（私は正しいですか？）

4

2 に答える 2

8

少しの追跡コードで問題を浮き彫りにすることができます：

var counter1, counter2 = 0

def sieve1(s: Stream[Int]): Stream[Int] = {
  counter1 += 1
  s.head #:: sieve1(s.tail.filter(_ % s.head != 0))
}

def sieve2(n: Int): Stream[Int] = {
  counter2 += 1
  n #:: sieve2(n + 1).filter(_ % n != 0)
}

sieve1(Stream.from(2)).take(100).toList
sieve2(2).take(100).toList

これを実行して、カウンターを確認できます。

scala> counter1
res2: Int = 100

scala> counter2
res3: Int = 540

したがって、最初のケースでは、コールスタックの深さは素数の数であり、2番目のケースでは、それ自体が最大の素数です（まあ、マイナス1）。

于 2012-11-11T18:31:18.820 に答える
1

これらのどちらも末尾再帰ではありません。

tailrecアノテーションを使用すると、関数が末尾再帰であるかどうかがわかります。

上記の2つの関数に@tailrecを追加すると、次のようになります。

import scala.annotation.tailrec

@tailrec
def sieve(s: Stream[Int]): Stream[Int] = {
  s.head #:: sieve(s.tail.filter(_ % s.head != 0))
}

@tailrec
def sieve(n: Int): Stream[Int] = {
  n #:: sieve(n + 1).filter(_ % n != 0)
}

これをロードすると、両方の定義が末尾再帰ではないことがわかります。

<console>:10: error: could not optimize @tailrec annotated method sieve: it contains a recursive call not in tail position
         s.head #:: sieve(s.tail.filter(_ % s.head != 0))
                ^
<console>:10: error: could not optimize @tailrec annotated method sieve: it contains a recursive call not in tail position
         n #:: sieve(n + 1).filter(_ % n != 0)
于 2012-11-11T18:29:47.597 に答える