Сопоставление с образцом и бесконечные потоки - PullRequest
Новая
       28

Сопоставление с образцом и бесконечные потоки

20 голосов
/ 21 сентября 2011

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

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, и адаптировал это решение из кода Розетты: 

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

Ответы [ 2 ]

19 голосов
/ 21 сентября 2011

a match {case x#::xs =>... примерно равно val (x, xs) = (a.head, a.tail).Таким образом, разница между плохой версией и хорошей заключается в том, что в плохой версии вы вызываете a.tail и b.tail в самом начале, а не просто используете их для построения хвоста результирующего потока.,Более того, когда вы используете их справа от #:: (не сопоставление с образцом, а построение результата, как в #:: merge(a.b.tail), вы фактически не вызываете слияние, что будет сделано только позже, при доступе к хвосту возвращенного потока.Таким образом, в хорошей версии вызов слияния вообще не вызывает * 1007. * В плохой версии он вызывает его сразу при запуске.

Теперь, если вы рассматриваете числа или даже упрощенную версию, скажите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 нет.Когда у вас есть (не пустой) поток, голова должна быть известна.Это означает, что когда вы получаете хвост потока, должен быть вычислен сам поток, его заголовок, который является вторым элементом исходного потока.Это иногда проблематично, но в вашем примере вы терпите неудачу, даже не добравшись туда.

6 голосов
/ 04 ноября 2012

Обратите внимание, что вы можете делать то, что вы хотите, определив лучший шаблонный сопоставитель для Stream:

Вот небольшой фрагмент, который я только что собрал в 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 находит ваш object #:: вместо одного в Stream.class всякий раз, когда он выполняет сопоставление с образцом.Чтобы облегчить это, может быть лучше использовать другое имя, например #>: или ##::, а затем просто не забывать всегда использовать это имя при сопоставлении с образцом.

Если вам когда-либо понадобится сопоставить пустой поток,используйте case Stream.Empty.Использование case Stream() попытается оценить весь ваш поток в сопоставлении с образцом, что приведет к печали.

...