Coincidencia de patrones y flujos infinitos

Question

Por lo tanto, estoy trabajando para enseñarme Scala, y una de las cosas con las que he estado jugando es la clase Stream. Traté de usar una traducción ingenua de la classic Haskell version of Dijkstra's solution 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 })) 
} 

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

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

que decidí mirar para ver si otras personas se habían resuelto el problema en Scala utilizando el enfoque de Haskell, y adaptado this solution del Código de 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})) 
} 

Ésta Funcionó muy bien, pero todavía me pregunto cómo me equivoqué en LazyHammingBad. ¿El uso de #:: para desestructurar x #:: xs fuerza la evaluación de xs por algún motivo? ¿Hay alguna forma de utilizar la coincidencia de patrones de forma segura con flujos infinitos, o simplemente tiene que usar head y tail si no desea que las cosas exploten?

Answer 1

a match {case x#::xs =>... es casi lo mismo 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, llama al a.tail y al b.tail desde el principio, en lugar de usarlas para compilar la cola resultante. Además, cuando los utiliza a la derecha de #:: (no coincidencia de patrones, pero construyendo el resultado, como en #:: merge(a.b.tail), en realidad no está convocando fusión, eso se hará más tarde, al acceder a la cola de la secuencia devuelta. versión, una llamada a fusionarse no llama tail en absoluto. en la versión mala, que llama las cosas bien en el arranque.

Ahora bien, si se tiene en cuenta los números, o incluso una versión simplificada, dice 1 #:: merge(numbers, anotherStream), cuando se llama se llama tail en la que (como take(10) voluntad), merge tiene que ser evaluado. se llama a tail en numbers, que llaman merge con numbers como parámetros, que llama tails en numbers, lo que llama merge, que llama tail ...

Por el contrario, en muy perezoso Haskell, cuando el ajuste de patrones, lo hace casi sin trabajo. Cuando lo haga case l of x:xs, evaluará l lo suficiente como para saber si se trata de una lista vacía o una desventaja. Si de hecho es un inconveniente, x y xs estarán disponibles como dos funciones, que eventualmente 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 el tail es flojo, el head no lo es. Cuando tienes un Stream (no vacío), el jefe debe ser conocido. Lo que significa que cuando obtiene la cola de la secuencia, ella misma una secuencia, su cabeza, que es el segundo elemento de la secuencia original, tiene que ser computada. Esto a veces es problemático, pero en tu ejemplo, fallas incluso antes de llegar allí.

Answer 2

Tenga en cuenta que usted puede hacer lo que quiere mediante la definición de una mejor comparador de patrón para Stream:

Aquí hay un poco Acabo de sacar juntos en un 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) 
} 

Ahora sólo tiene que asegurarse que Scala encuentre su object #:: en lugar del que está en Stream.class cada vez que haga una coincidencia de patrón. Para facilitar eso, podría ser mejor usar un nombre diferente como #>: o ##:: y luego recordar siempre usar ese nombre cuando coincidan los patrones.

Si alguna vez necesita hacer coincidir la secuencia vacía, use case Stream.Empty. El uso de case Stream() intentará evaluar toda la secuencia allí en la coincidencia de patrón, lo que provocará tristeza.