模式匹配和无限流

Question

所以,我正在努力自学Scala,而我一直在玩的其中一件事就是Stream上课.我试图使用经典的Haskell版本的Dijkstra解决汉明数字问题的天真翻译:

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方法解决了Scala中的问题,并从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如果你不想让事情爆炸？

Answer 1

a match {case x#::xs =>...与...大致相同val (x, xs) = (a.head, a.tail).因此,坏版本和好版本之间的区别在于,在错误版本中,您在开始时调用a.tail并且b.tail正确,而不是仅使用它们来构建结果流的尾部.此外,当你在右边使用它们时#::(不是模式匹配,而是构建结果,就像#:: merge(a.b.tail)你实际上没有调用merge一样,只有在访问返回的Stream的尾部时才会这样做.所以在好的版本中,对合并的调用根本没有调用tail.在坏版本中,它在开始时调用它.

现在,如果您考虑数字,甚至简化版本,比如1 #:: merge(numbers, anotherStream),当您打电话给您时tail(如此take(10)),merge必须进行评估.你叫tail上numbers,它调用merge与numbers作为参数,这就要求tails对numbers,它调用merge,调用tail...

相比之下,在超级懒惰的Haskell中,当你模式匹配时,它几乎没有任何工作.当你这样做时case l of x:xs,它会评估l到足以知道它是空列表还是缺点.如果它确实是一个缺点,x并且xs将作为两个thunks提供,这些函数最终将提供对内容的访问.Scala中最接近的等价物就是测试empty.

另请注意,在Scala Stream中,虽然tail是懒惰,但事实head并非如此.当你有一个(非空)流时,必须知道头部.这意味着当你得到流的尾部时,它本身就是一个流,它的头部,即原始流的第二个元素,必须被计算出来.这有时会有问题,但在你的例子中,你甚至在到达那里之前就失败了.

Answer 2

请注意,您可以通过为以下内容定义更好的模式匹配器来执行您想要的操作Stream:

这里有一点我只是在Scala工作表中拉到一起:

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 在进行模式匹配时找到你object #::而不是那个Stream.class.为方便起见,最好使用不同的名称,#>:或者##::只是记住在模式匹配时始终使用该名称.

如果您需要匹配空流,请使用case Stream.Empty.使用case Stream()将尝试在模式匹配中评估整个流,这将导致悲伤.