Согласование шаблонов и бесконечные потоки

Итак, я работаю, чтобы научить себя Scala, и одна из вещей, с которыми я играл, - это класс Stream. Я попытался использовать наивный перевод классической версии Dikkstra версии Haskell для проблемы номера Хэмминга:

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

Я решил посмотреть, решили ли другие люди проблему в Scala с использованием подхода Haskell и адаптировали это решение из кода Rosetta:

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, если вы не хотите, чтобы что-то взорвалось?

Ответ 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 на этом (как take(10)), merge должен быть оценен. Вы вызываете tail на numbers, который вызывает merge с numbers как параметры, который вызывает tails на numbers, который вызывает merge, который вызывает tail...

В отличие от этого, в супер ленивом Haskell, когда вы сравниваете шаблон, он практически не работает. Когда вы выполните case l of x:xs, он будет оценивать l достаточно, чтобы узнать, является ли это пустым списком или минусами. Если это действительно минус, x и xs будут доступны как два thunks, функции, которые в конечном итоге будут предоставлять доступ позже. Ближайшим эквивалентом в Scala было бы просто проверить empty.

Обратите внимание также, что в Scala Поток, а tail - ленивый, head - нет. Когда у вас есть (не пустой) поток, голова должна быть известна. Это означает, что, когда вы получаете хвост потока, нужно вычислить поток, его головку, которая является вторым элементом исходного потока. Это иногда проблематично, но в вашем примере вы терпите неудачу, прежде чем попасть туда.

Ответ 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() будет пытаться оценить весь ваш поток там в совпадении с шаблоном, что приведет к грусти.