由不可變類型構成的結構有可能有一個循環嗎？

Question

考慮以下幾點：

case class Node(var left: Option[Node], var right: Option[Node]) 

可以很容易地看到你怎麼可以遍歷此，搜索它，不管。但現在想象你做到了這一點：

val root = Node(None, None) 
root.left = root 

現在，這是糟糕的，災難性的。實際上，你將它輸入到REPL中，你將得到一個StackOverflow（嘿，這對於一個樂隊來說是個好名字！），並且一個堆棧跟蹤一千行。如果您想嘗試，請執行以下操作：

{ root.left = root }: Unit 

壓制REPL善意嘗試打印結果。

但是爲了構建這一點，我必須專門給予案例級的可變成員，這是我在現實生活中永遠不會做的事情。如果我使用普通的可變成員，我會遇到建設問題。我能來最接近的是

case class Node(left: Option[Node], right: Option[Node]) 
val root: Node = Node(Some(loop), None) 

然後root有相當醜陋值Node(Some(null),None)，但它仍然不是循環。所以我的問題是，如果一個數據結構是傳遞不變的（也就是說，它的所有成員都是不可變的值或對其本身是傳遞不變的其他數據結構的引用），它是否保證是非循環的？

它會很酷，如果它。

Answer 1

是的，即使純粹不變的數據結構以純粹的，引用透明的，無效的語言來創建循環數據結構也是可能的。

「顯而易見的」解決方案是將潛在的循環引用提取到單獨的數據結構中。例如，如果您將圖形表示爲鄰接矩陣，那麼您的數據結構中不需要循環來表示圖形中的循環。但是這就是作弊：通過增加一層間接尋址（除了間接層數太多的問題），每個問題都可以解決。

另一個作弊是從外部繞過斯卡拉的不變性保證，例如，在默認的Scala-JVM實現上使用Java反射方法。

它是可能創建實際循環引用。該技術被稱爲Tying the Knot，它依賴於懶惰：您可以實際設置對尚未創建的對象的引用，因爲該引用將被懶惰地評估，屆時該對象將被創建。 Scala支持各種形式的懶惰：lazy val，名稱參數和現在已棄用的DelayedInit。另外，你可以使用函數或方法來「僞裝」懶惰：將你想讓懶惰的東西包裝在產生該東西的函數或方法中，並且在你調用該函數或方法之前它不會被創建。

因此，在Scala中也應該可以使用相同的技術。

Answer 2

如何使用lazy與call by name？

scala> class Node(l: => Node, r: => Node, v: Int) 
// defined class Node 

scala> lazy val root: Node = new Node(root, root, 5) 
// root: Node = <lazy>