模式匹配和无限流 [英] Pattern matching and infinite streams

问题描述

所以，我正在努力自学Scala，而我一直在玩的事情之一是Stream类.我试图对汉明使用经典的Haskell版本的Dijkstra解决方案的简单翻译号码问题:

So, I'm working to teach myself Scala, and one of the things I've been playing with is the Stream class. I tried to use a naïve translation of the classic Haskell version of Dijkstra's solution to the Hamming number problem:

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 }))
}

在口译员那里试一试，很快导致失望:

Taking this for a spin in the interpreter led quickly to disappointment:

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

我决定看看其他人是否已使用Haskell方法解决了Scala中的问题，并采用了此解决方案来自Rosetta代码:

I decided to look to see if other people had solved the problem in Scala using the Haskell approach, and adapted this solution from Rosetta Code:

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}))
}

这个很好用，但是我仍然想知道我在LazyHammingBad中怎么做错了.使用#::解构x #:: xs是否由于某些原因而强制评估xs?有什么方法可以对无限流安全地使用模式匹配，或者如果不想让事情崩溃，是否只需要使用head和tail?

This one worked nicely, but I still wonder how I went wrong in LazyHammingBad. Does using #:: to destructure x #:: xs force the evaluation of xs for some reason? Is there any way to use pattern matching safely with infinite streams, or do you just have to use head and tail if you don't want things to blow up?

推荐答案

a match {case x#::xs =>...与val (x, xs) = (a.head, a.tail)大致相同.因此，不良版本和良好版本之间的区别在于，在不良版本中，您是在开始时调用a.tail和b.tail，而不是仅仅使用它们来构建结果流的尾部. .此外，当您在#::的右侧使用它们时(不是模式匹配，而是像#:: merge(a.b.tail)中那样构建结果，您实际上并没有调用merge，只有在访问返回的Stream的尾部时才进行合并.因此，在好的版本中，进行合并的调用根本不会调用tail；在坏的版本中，它将在开始时立即调用

a match {case x#::xs =>... is about the same as val (x, xs) = (a.head, a.tail). So the difference between the bad version and the good one, is that in that in the bad version, you're calling a.tail and b.tail right at the start, instead of just use them to build the tail of the resulting stream. Furthermore when you use them at the right of #:: (not pattern matching, but building the result, as in #:: merge(a.b.tail) you are not actually calling merge, that will be done only later, when accessing the tail of the returned Stream. So in the good version, a call to merge does not call tail at all. In the bad version, it calls it right at start.

现在，如果您考虑数字或什至是简化版本，例如1 #:: merge(numbers, anotherStream)，则在呼叫时按此调用tail(就像take(10)一样)，必须对merge进行求值.您在numbers上调用tail，该调用以numbers作为参数调用merge，在numbers上调用tails，该调用又调用merge，该调用又调用tail ...

Now if you consider numbers, or even a simplified version, say 1 #:: merge(numbers, anotherStream), when you call you call tail on that (as take(10) will), merge has to be evaluated. You call tail on numbers, which call merge with numbers as parameters, which calls tails on numbers, which calls merge, which calls tail...

相比之下，在超级懒惰的Haskell中，当您进行模式匹配时，它几乎没有任何作用.当您执行case l of x:xs时，它将评估l刚好足以知道它是空列表还是不利条件. 如果确实是一个缺点，则x和xs将作为两个重击提供，这些函数最终将在以后提供对内容的访问. Scala中最接近的等效项是仅测试empty.

By contrast, in super lazy Haskell, when you pattern match, it does barely any work. When you do case l of x:xs, it will evaluate l just enough to know whether it is an empty list or a cons. If it is indeed a cons, x and xs will be available as two thunks, functions that will eventually give access, later, to content. The closest equivalent in Scala would be to just test empty.

还请注意，在Scala Stream中，虽然tail是惰性的，但head不是.当您拥有(非空)流时，必须知道其头部.这意味着，当您获得流的尾部时，必须计算出流本身，其头部(即原始流的第二个元素)本身.有时这是有问题的，但是在您的示例中，您甚至没有到达就失败了.

Note also that in Scala Stream, while the tail is lazy, the head is not. When you have a (non empty) Stream, the head has to be known. Which means that when you get the tail of the stream, itself a stream, its head, that is the second element of the original stream, has to be computed. This is sometimes problematic, but in your example, you fail before even getting there.

这篇关于模式匹配和无限流的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！