Kết hợp mẫu và các dòng vô hạn

Question

Vì vậy, tôi đang làm việc để tự dạy mình Scala, và một trong những thứ tôi đã chơi với là lớp Stream. Tôi cố gắng để sử dụng một dịch ngây thơ của classic Haskell version of Dijkstra's solution cho vấn đề số 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 })) 
} 

Lấy này cho một spin trong người phiên dịch đã dẫn một cách nhanh chóng để sự thất vọng:

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

tôi quyết định xem xét để xem nếu những người khác đã giải quyết vấn đề ở Scala bằng cách sử dụng phương pháp tiếp cận Haskell và điều chỉnh this solution từ Mã 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})) 
} 

Điều này làm việc độc đáo, nhưng tôi vẫn tự hỏi làm thế nào tôi đã đi sai trong LazyHammingBad. Việc sử dụng #:: để hủy cấu trúc x #:: xs có buộc phải đánh giá xs vì một số lý do không? Có cách nào để sử dụng mẫu phù hợp một cách an toàn với luồng không giới hạn hoặc bạn chỉ cần sử dụng head và tail nếu bạn không muốn mọi thứ phát nổ?

Answer 1

a match {case x#::xs =>... tương tự như val (x, xs) = (a.head, a.tail). Vì vậy, sự khác biệt giữa phiên bản xấu và phiên bản tốt, là trong phiên bản xấu, bạn đang gọi a.tail và b.tail ngay khi bắt đầu, thay vì chỉ sử dụng chúng để tạo đuôi của luồng kết quả. Hơn nữa khi bạn sử dụng chúng ở bên phải của #:: (không khớp mẫu, nhưng xây dựng kết quả, như trong #:: merge(a.b.tail) bạn không thực sự gọi hợp nhất, điều đó sẽ chỉ được thực hiện sau đó, khi truy cập vào đuôi của luồng trả về. Phiên bản, một cuộc gọi để hợp nhất không gọi là tail ở tất cả. Trong phiên bản xấu, nó gọi nó ngay lúc bắt đầu

Bây giờ nếu bạn xem xét số, hoặc thậm chí một phiên bản đơn giản, nói 1 #:: merge(numbers, anotherStream), khi bạn gọi bạn gọi tail trên đó (như take(10) sẽ), merge phải được đánh giá Bạn gọi số tail trên numbers, gọi số merge với numbers làm thông số, gọi tails trên numbers, gọi số merge, gọi tail ...

Ngược lại, trong siêu lười Haskell, khi bạn khớp mẫu, nó hầu như không có tác dụng. Khi bạn làm case l of x:xs, nó sẽ đánh giá l chỉ đủ để biết liệu đó là một danh sách trống hoặc một khuyết điểm. Nếu nó thực sự là một khuyết điểm, x và xs sẽ có sẵn dưới dạng hai khối, chức năng mà cuối cùng sẽ cung cấp quyền truy cập, sau đó, cho nội dung. Điểm tương đương gần nhất trong Scala sẽ là chỉ kiểm tra empty.

Cũng lưu ý rằng trong Scala Stream, trong khi tail là lười, head thì không. Khi bạn có một luồng (không trống), đầu phải được biết đến. Điều đó có nghĩa là khi bạn nhận được đuôi của luồng, chính nó là một dòng, đầu của nó, đó là phần tử thứ hai của luồng ban đầu, phải được tính toán. Điều này đôi khi có vấn đề, nhưng trong ví dụ của bạn, bạn thất bại trước khi đến đó.

Answer 2

Lưu ý rằng bạn có thể làm những gì bạn muốn bằng cách định nghĩa một mô hình khớp tốt hơn cho Stream:

Dưới đây là một chút tôi chỉ kéo lại với nhau trong một 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) 
} 

Bây giờ bạn chỉ cần phải chắc chắn Scala tìm thấy object #:: của bạn thay vì số trong Stream.class bất cứ khi nào nó thực hiện đối sánh mẫu. Để tạo thuận lợi cho điều đó, tốt nhất nên sử dụng một tên khác như #>: hoặc ##:: và sau đó chỉ cần nhớ luôn sử dụng tên đó khi đối sánh mẫu.

Nếu bạn cần khớp luồng trống, hãy sử dụng case Stream.Empty. Sử dụng case Stream() sẽ cố gắng đánh giá toàn bộ luồng của bạn ở đó trong kết hợp mẫu, điều này sẽ dẫn đến nỗi buồn.