Scala неизменяемый связанный список с циклами

Question

В Scala мне нужно создать неизменный связанный список с циклами. Что-то вроде:

case class Node(element: Int, next: Node) 
val linkedList = Node(1, Node(2, null)) 
val cycle = Node(3, cycle) 

cycle.next // this should go back to the same element 

Но это не работает. Как создать неизменяемый связанный список с циклами?

Answer 1

Ленивая конструкция:

scala> case class Node(element: Int)(next0: => Node) { def next = next0 } 
defined class Node 

scala> object X { val cycle: Node = Node(3)(cycle) } 
defined object X 

scala> X.cycle 
res0: Node = Node(3) 

scala> X.cycle.next 
res1: Node = Node(3) 

Answer 2

Неизменных связанные списки с циклами возможны, если они ленивы. Scala уже поддерживает ленивые списки. Они называются Stream S:

val stream: Stream[Int] = 1 #:: 2 #:: 3 #:: stream 
for { i <- stream.take(10) } { 
    println(i) 
} 

Это будет печатать:

1 
2 
3 
1 
2 
3 
1 
2 
3 
1 

Answer 3

Используйте ленивые значения и по имени параметров отложить инициализацию:

class Node(val element: Int, next_ : => Node) { 
    lazy val next = next_ 
} 

lazy val root: Node = 
    new Node(1, 
    new Node(2, 
     new Node(3, root) 
    ) 
) 

// tail-recursive print function as a bonus 
def printRec(node: Node, depth: Int): Unit = if (depth > 0) { 
    println(node.element) 
    printRec(node.next, depth - 1) 
} 

printRec(root, 10) 

Выход:

1 
2 
3 
1 
2 
3 
1 
2 
3 
1