scala – 模式匹配和无限流

发布时间：2020-12-16 09:35:10 所属栏目：安全来源：网络整理

导读：所以，我正在教自己的Scala，而我一直在玩的事情之一就是Stream类。我试图用 classic Haskell version of Dijkstra’s solution的朴实翻译汉明号码问题： object LazyHammingBad { private def merge(a: Stream[BigInt],b: Stream[BigInt]): Stream[BigInt]

所以，我正在教自己的Scala，而我一直在玩的事情之一就是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方法在Scala中解决了这个问题，并从Rosetta Code改编了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}))
}

这个工作很好，但我仍然想知道我在LazyHammingBad如何出错。使用#::来破坏x#:: xs的某些原因强制对xs进行评估？有没有什么办法可以安全地使用模式匹配无限流，或者你只需??要使用头和尾，如果你不想要的东西炸毁？

解决方法

匹配{case x#:: xs => …与val(x，xs)=(a.head，a.tail)大致相同。所以坏的版本和好的区别是，在那个坏的版本中，你在开始时调用a.tail和b.tail，而不是仅仅使用它们构建所生成的流的尾部。此外，当您在#::(而不是模式匹配)右侧使用它们时，但是构建结果，如#:: merge(abtail)所示，您实际上并不会调用merge，所以在稍后才能访问尾部的返回的流，所以在好的版本中，一个调用合并不会调用tail，在坏的版本，它在开始时调用它。

现在，如果您考虑数字，甚至是简化版本，请说1#:: merge(numbers，anotherStream)，当您调用它时调用尾部(如(10)))，必须对merge进行评估。你调用数字尾部，调用数字作为参数合并，它调用数字尾部，调用合并，调用尾部

相比之下，在超级懒惰的Haskell，当你模式匹配，它几乎没有任何工作。当您执行x：xs的情况下，它将评估l足够知道它是否为空列表或缺点。
如果确实是一个缺点，x和xs将可用作两个thunk，函数最终将允许访问内容。 Scala中最接近的等价物将是空的。

还要注意，在Scala Stream中，虽然尾巴是懒惰的，头不是。当你有(非空)流时，头必须知道。这意味着当你获得流的尾部时，它本身就是一个流，它的头是原始流的第二个元素，必须被计算出来。这有时是有问题的，但在你的例子中，你甚至在到达之前就失败了。

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!