Implementing Stream.toList

Question

這是我在Functional Programming in Scala的練習中爲Stream類寫toList的嘗試。

def toList[A](stream: Stream[A]): List[A] = { 
    def go(s: Stream[A], acc: List[A]): List[A] = s match { 
     case x #:: xs => go(xs, acc :+ x) 
     case _ => acc 
    } 
    go(stream, Nil) 
} 

在此基礎上post閱讀（但不理解所有的），我不能肯定，如果我的模式匹配是正確的。特別是，我擔心我的第一個案例導致立即評估流的尾部。

從概念上講，我認爲我需要實現toList，其中每個遞歸步驟將流頭添加到列表中，而不是評估每個步驟的尾部。

我在這個理解和上面的實現中正確嗎？

Answer 1

Stream的文檔和來源解決了這個問題。

來源爲#::是：

object #:: { 
    def unapply[A](xs: Stream[A]): Option[(A, Stream[A])] = 
     if (xs.isEmpty) None 
     else Some((xs.head, xs.tail)) 
    } 

這樣做的相關部分是Some((xs.head, xs.tail))。該source爲tail指出：

注意，此方法不會強制Stream但 的評價僅僅返回懶惰的結果。

根據文檔xs未在案例聲明case x #:: xs中得到評估。如果這種情況匹配，則調用go(xs, acc :+ x)。 xs這裏基本上是s.tail，如上所述未對其進行評估。

在post您鏈接到的代碼是在尾部（一Stream）在遞歸調用用於merge不同，然後unapply被稱爲它解構它把它的頭部和尾部。由於head是一個Stream它被評估，並將在足夠大的輸入上堆棧溢出。 @Didier Dupont也表達了這一點：

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

的head和tail爲xs在你的代碼的提取將不會有這個問題，除非A是Stream。即流的流。另一篇文章中的代碼通過遞歸調用merge創建了這種情況。