模式匹配和無限流

所以，我正在教自己斯卡拉，我一直玩的東西之一是Stream類。我試圖用classic Haskell version of Dijkstra's solution的天真翻譯海明號問題：模式匹配和無限流

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

我決定去看看，看看其他人已經解決了使用Haskell的方法在Scala中的問題，從羅塞塔代碼改編this solution：

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？

來源

2011-09-20 Pillsy

a match {case x#::xs =>...與val (x, xs) = (a.head, a.tail)大致相同。所以壞版本和好版本之間的區別在於，在壞版本中，您在開始時調用了a.tail和b.tail，而不是使用它們來構建結果流的尾部。此外，當你在#::的右邊使用它們時（不是模式匹配，而是建立結果，如#:: merge(a.b.tail)那樣，你實際上並沒有調用合併，這隻會在訪問返回的Stream的尾部時纔會完成。版本，通話合併不叫tail可言。在惡劣的版本，它調用正確的開始。

現在，如果你考慮的數字，甚至一個簡化版本，說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將作爲兩個thunk來使用，這些thunks最終會在稍後訪問內容。在斯卡拉最接近的相當於只是測試empty。

請注意，在斯卡拉流，而tail是懶惰的，head不是。當你有一個（非空的）流時，必須知道頭。這意味着當你得到流的尾部時，它本身就是一個流，它的頭部，即原始流的第二個元素，必須被計算出來。這有時是有問題的，但在你的例子中，即使到達那裏，你也失敗了。

來源

2011-09-21 00:36:39

我使用'懶惰VAL溶液：列表[移動] = pathsToGoal匹配{ 情況下（_，moveHistory）＃:: _ => moveHistory.reverse 情況_ => List.empty [移動] }'和這不會評估尾巴。是因爲我在使用_嗎？在這種情況下，pathsToGoal是一個無限的Stream – himanshu219

注意，您可以爲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()將嘗試評估模式匹配中的整個流，這將導致悲傷。

來源

2012-11-04 12:00:31

模式匹配和無限流

回答

相關問題