scala - Coincidencia de patrones y flujos infinitos

pattern-matching lazy-evaluation

Question

Entonces, estoy trabajando para enseñarme a Scala, y una de las cosas con las que he estado jugando es la clase Stream . Intenté usar una traducción ingenua de la versión clásica de Haskell de la solución de Dijkstra al problema del número de Hamming:

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

Tomando esto para dar una vuelta en el intérprete condujo rápidamente a la decepción:

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

Decidí ver si otras personas habían resuelto el problema en Scala utilizando el enfoque de Haskell y adaptaron esta solución del Código 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}))
}

Este funcionó bien, pero todavía me pregunto cómo me equivoqué en LazyHammingBad . ¿Usar #:: para destruir x #:: xs obliga a la evaluación de xs por alguna razón? ¿Hay alguna forma de usar la coincidencia de patrones de forma segura con flujos infinitos, o solo tienes que usar la head y la tail si no quieres que las cosas exploten?

Answer 1

Tenga en cuenta que puede hacer lo que quiera definiendo un mejor emparejador de patrones para Stream :

Aquí hay un poco que acabo de reunir en una hoja de trabajo 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)
}

Ahora solo necesita asegurarse de que Scala encuentre su object #:: lugar del que está en Stream.class cuando hace una comparación de patrones. Para facilitar esto, podría ser mejor usar un nombre diferente como #>: o ##:: y luego, recuerde usar siempre ese nombre cuando coincida con el patrón.

Si alguna vez necesita hacer coincidir el flujo vacío, use el case Stream.Empty . Utilizando case Stream() intentará evaluar su flujo completo allí en la coincidencia del patrón, lo que llevará a la tristeza.

Answer 2

a match {case x#::xs =>... es casi igual que val (x, xs) = (a.head, a.tail) . Entonces, la diferencia entre la versión mala y la buena, es que en la versión mala, se llama a.tail y b.tail desde el principio, en lugar de solo usarlas para construir la cola del flujo resultante. . Además, cuando los usa a la derecha de #:: (no coincide con el patrón, pero #:: merge(abtail) el resultado, como en #:: merge(abtail) realidad no está llamando a fusionar, que se hará solo más tarde, cuando acceda a la cola de La secuencia devuelta. Por lo tanto, en la versión buena, una llamada a fusionar no llama en absoluto a la tail . En la versión incorrecta, la llama al principio.

Ahora, si considera los números, o incluso una versión simplificada, diga 1 #:: merge(numbers, anotherStream) , cuando llame a la tail de eso (como take(10) will), la merge debe ser evaluada. Llama a tail en numbers , que llaman a merge con numbers como parámetros, que llama a tails a numbers , a qué llamadas se merge , a lo que llama tail ...

Por el contrario, en Haskell súper perezoso, cuando se ajusta el patrón, apenas funciona. Cuando haga el case l of x:xs , evaluará l solo lo suficiente para saber si es una lista vacía o una contra. Si es de hecho una desventaja, x y xs estarán disponibles como dos funciones, funciones que finalmente darán acceso, más tarde, al contenido. El equivalente más cercano en Scala sería simplemente probar empty .

Tenga en cuenta también que en Scala Stream, mientras que la tail es perezosa, la head no lo es. Cuando tienes un flujo (no vacío), la cabeza debe ser conocida. Lo que significa que cuando se obtiene la cola de la secuencia, se debe calcular una secuencia, su cabeza, que es el segundo elemento de la secuencia original. Esto a veces es problemático, pero en tu ejemplo, fallas incluso antes de llegar allí.