Dopasowywanie wzorców i nieskończone strumienie

Question

Pracuję więc, aby nauczyć się Scala, a jedną z rzeczy, z którymi się bawiłem jest klasa Stream. Próbowałem użyć tłumaczenia naiwne z classic Haskell version of Dijkstra's solution problemu numer Hamminga:

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

Biorąc to dla korkociągu w tłumacza doprowadziły szybko do rozczarowania:

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

postanowiłem sprawdź, czy inni ludzie nie rozwiązało problemu w Scala stosując podejście Haskell i dostosowane this solution z kodeksem 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})) 
} 

ten jeden działało ładnie, ale wciąż zastanawiam się, jak poszło nie tak w LazyHammingBad. Czy użycie #:: do zniszczenia x #:: xs wymusza na sobie ocenę xs z jakiegoś powodu? Czy istnieje sposób na bezpieczne dopasowanie wzorca z nieskończonymi strumieniami, czy po prostu trzeba użyć head i tail, jeśli nie chcesz, aby coś się wysadziło?

Answer 1

a match {case x#::xs =>... jest mniej więcej taki sam jak val (x, xs) = (a.head, a.tail). Różnica między wersją złą i dobrą jest taka, że ​​w złej wersji na początku nazywasz się a.tail i b.tail, zamiast używać ich do budowania ogona strumienia wynikowego. Co więcej, gdy używasz ich po prawej stronie #:: (bez dopasowywania wzorca, ale budowanie wyniku, jak w #:: merge(a.b.tail), nie wywołujesz scalania, będzie to wykonywane dopiero później, podczas uzyskiwania dostępu do ogona zwróconego strumienia. wersja, wezwanie do scalenia nie wymaga tail w ogóle. W złej wersji, że nazywa to prawo na początku.

teraz, jeśli wziąć pod uwagę liczby, a nawet uproszczonej wersji, powiedzmy 1 #:: merge(numbers, anotherStream), kiedy zadzwonić zadzwonić tail na tym (jak take(10) będzie), merge musi być ocenione. Nazywasz tail na numbers, który nazywamy merge z numbers jako parametry, które nazywa tails na numbers, który wywołuje merge, który wywołuje tail ...

W przeciwieństwie do super leniwego Haskella, gdy dopasowujesz wzór, nie wykonuje on żadnej pracy. Gdy wykonasz case l of x:xs, oceni on tylko, czy jest to pusta lista, czy też minusy. Jeśli to rzeczywiście minusy, x i xs będą dostępne jako dwie dodatkowe funkcje, które w końcu pozwolą na dostęp do zawartości. Najbliższym odpowiednikiem w Scali byłoby właśnie przetestowanie empty.

Należy również zauważyć, że w strumieniu Scala, gdy tail jest leniwy, head nie jest. Kiedy masz strumień (nie pusty), głowa musi być znana. Co oznacza, że ​​kiedy dostaje się ogon strumienia, sam strumień, jego głowa, czyli drugi element pierwotnego strumienia, musi zostać obliczony. Czasami jest to problematyczne, ale w twoim przykładzie nie udaje ci się dotrzeć nawet przed dotarciem.

Answer 2

Pamiętaj, że możesz robić, co chcesz, definiując lepszego dopasowywania wzoru dla Stream:

Oto nieco po prostu wyciągnął razem w 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) 
} 

Teraz po prostu trzeba się upewnić, Scala znajduje Twoją object #:: zamiast jednej w Stream.class, gdy tylko dopasowuje wzorce. Aby to ułatwić, najlepiej użyć innej nazwy, takiej jak #>: lub ##::, a następnie pamiętaj, aby zawsze używać tej nazwy podczas dopasowywania wzorca.

Jeśli musisz dopasować pusty strumień, użyj case Stream.Empty. Korzystanie z case Stream() będzie próbowało ocenić cały twój strumień w dopasowaniu wzorca, co doprowadzi do smutku.