パターンマッチングと無限ストリーム

Question

私はScalaを教えるために働いています。私が使ってきたことの1つはStreamクラスです。私はハミング数の問題にclassic Haskell version of Dijkstra's solutionのナイーブ翻訳を使用しようとしました：通訳のスピンのためにこれを取る

object LazyHammingBad { 
    private def merge(a: Stream[BigInt], b: Stream[BigInt]): Stream[BigInt] = 
    (a, b) match { 
     case (x #:: xs, y #:: ys) => 
     if (x < y) x #:: merge(xs, b) 
     else if (y < x) y #:: merge(a, ys) 
     else x #:: merge(xs, ys) 
    } 

    val numbers: Stream[BigInt] = 
    1 #:: merge(numbers map { _ * 2 }, 
     merge(numbers map { _ * 3 }, numbers map { _ * 5 })) 
} 

は失望に迅速につながった：

scala> LazyHammingBad.numbers.take(10).toList 
java.lang.StackOverflowError 

場合、私が見て探すことにしました他の人は、Haskellのアプローチを使用してスカラ座での問題を解決し、そしてロゼッタコードからthis solutionを適応していた：

object LazyHammingGood { 
    private def merge(a: Stream[BigInt], b: Stream[BigInt]): Stream[BigInt] = 
    if (a.head < b.head) a.head #:: merge(a.tail, b) 
    else if (b.head < a.head) b.head #:: merge(a, b.tail) 
    else a.head #:: merge(a.tail, b.tail) 

    val numbers: Stream[BigInt] = 
    1 #:: merge(numbers map {_ * 2}, 
      merge(numbers map {_ * 3}, numbers map {_ * 5})) 
} 

この1うまくいきましたが、私はまだLazyHammingBadに間違っていたのでしょうか？何らかの理由でを使用してx #:: xsを強制的に使用してxsの評価を行っていますか？無限のストリームでパターンマッチングを安全に使用する方法はありますか？物事を爆破したくない場合は、headとtailを使用するだけですか？

Answer 1

a match {case x#::xs =>...は、val (x, xs) = (a.head, a.tail)とほぼ同じです。したがって、悪いバージョンと良いバージョンの違いは、悪いバージョンでは、最初にa.tailとb.tailを呼び出して、結果のストリームの末尾を作成するのではなく、すぐに呼び出していることです。さらに、#::の右側でそれらを使用すると（パターンマッチングではなく、結果を構築すると#:: merge(a.b.tail)のように実際にマージを呼び出すことはなく、返されたストリームの末尾にアクセスするときにのみ行われます）バージョン、マージするの呼び出しは全くtailを呼び出すことはありません。悪いバージョンでは、それは右の開始時に、それを呼び出します。

を今、あなたは数字を考える、あるいは簡易版、1 #:: merge(numbers, anotherStream)言うならば、あなたはtailを呼び出す呼び出すときその上mergeが評価されなければならず、（意志take(10)として）。あなたはにtailsを呼び出す、パラメータとしてnumbersとmergeを呼んで、numbersにtailを呼び出します0は、mergeを呼び出し、tailを呼び出します。

対照的に、スーパー・レイジー・ハスケルでは、パターン・マッチを行うとほとんどすべての作業を行います。 case l of x:xsを実行すると、空のリストであるか否かを知るのに十分なだけ、lが評価されます。 それが本当に短所であれば、xとxsは、最終的にはコンテンツにアクセスできるようになる機能で、2つのサンクとして利用できます。 Scalaで最も近いのは、emptyのテストだけです。

Scala Streamでは、tailが遅延しているが、headはそうではないことにも注意してください。あなたが（空ではない）ストリームを持っているとき、頭を知る必要があります。つまり、ストリームの尾部、つまりストリームが取得されると、元のストリームの2番目の要素である先頭が計算されます。これは時には問題がありますが、あなたの例では、そこに到達する前に失敗します。あなたはStreamのためのより良いパターンマッチを定義することによって、あなたがやりたいことができ

Answer 2

注：

ここで私はちょうどScala Worksheetで一緒に引っ張っビットです：

object HammingTest { 
    // A convenience object for stream pattern matching 
    object #:: { 
    class TailWrapper[+A](s: Stream[A]) { 
     def unwrap = s.tail 
    } 
    object TailWrapper { 
     implicit def unwrap[A](wrapped: TailWrapper[A]) = wrapped.unwrap 
    } 
    def unapply[A](s: Stream[A]): Option[(A, TailWrapper[A])] = { 
     if (s.isEmpty) None 
     else { 
     Some(s.head, new TailWrapper(s)) 
     } 
    } 
    } 

    def merge(a: Stream[BigInt], b: Stream[BigInt]): Stream[BigInt] = 
    (a, b) match { 
     case (x #:: xs, y #:: ys) => 
     if (x < y) x #:: merge(xs, b) 
     else if (y < x) y #:: merge(a, ys) 
     else x #:: merge(xs, ys) 
    }            //> merge: (a: Stream[BigInt], b: Stream[BigInt])Stream[BigInt] 

    lazy val numbers: Stream[BigInt] = 
    1 #:: merge(numbers map { _ * 2 }, merge(numbers map { _ * 3 }, numbers map { _ * 5 })) 
                //> numbers : Stream[BigInt] = <lazy> 
    numbers.take(10).toList       //> res0: List[BigInt] = List(1, 2, 3, 4, 5, 6, 8, 9, 10, 12) 
} 

今、あなたはちょうど確認する必要がありますパターンマッチングを行っているときはいつでも、ScalaはStream.classの代わりにobject #::を見つけます。そのためには、#>:や##::という別の名前を使用し、パターンマッチングの際に常にその名前を使用することを忘れないようにしてください。

空のストリームと一致する必要がある場合は、case Stream.Emptyを使用してください。 case Stream()を使用すると、パターンマッチでストリーム全体を評価しようとしますが、それは悲しみにつながります。